The Painter’s Partition Problem Part I

April 5, 2011 in dynamic programming

You have to paint N boards of length {A0, A1, A2 … AN-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.


This is a problem which is fairly difficult. Try your very best to really think through it. You will improve your problem solving technique by struggling through it!

It turns out that this problem is the same as “FairWorkload” from TopCoder’s division 1 level 2 problem in SRM 169. If you find the problem statement above is difficult to understand, head over to TopCoder’s FairWorkload problem statement for a clearer description with examples. This problem is an interesting problem because it has several approaches, which I will outline them one by one here.

For most people, the first natural approach is to brute force. Let’s look at an example where you have nine boards, each of length 100, and you have three painters. How would you divide the boards?

Very easy, just divide it into three equal-sized partitions!

100 100 100 | 100 100 100 | 100 100 100

But what if the boards are of different lengths? If we just divide the boards into three equal-sized partitions, the below configuration would be divided as:

100 200 300 | 400 500 600 | 700 800 900

The above allocation is clearly not appropriate, as it is extremely unfair to the third painter. The third painter has to paint 2400 units while the first painter paints only 600 units! The fairest possible way to divide the boards among the three painters should be:

100 200 300 400 500 | 600 700 | 800 900

In this way, the largest board to paint is 1700 units whilst the smallest board to paint is 1300 units. Compared to the previous allocation, this allocation allows painting to finish faster because the maximum over the partitions has decreased from 2400 to 1700 units.

Now that we understand the problem better, we can re-state the above problem as follow:

Given an array of non-negative integers A and a positive integer k, we want to:
Divide A into k or fewer partitions,
such that the maximum sum over all the partitions is minimized.

By now, I am sure a handful of people would start thinking a heuristic approach to solve this problem. How about just computing the average size of a partition (ie, ∑{i=0..n-1} Ai / k) and try to match each partition as closely to the average as possible? Although this seemed to work for the above examples, there is no way you could evaluate all possibilities systematically and thus do not always produce the correct solution.

A more systematic way is to use the brute force approach to evaluate all possibilities. However, brute force in this case is not as straight forward as it used to be. Stop for awhile and think how you would do an exhaustive search for all possibilities. (Hint: Try to think recursively)

Recursion can be utilized to solve this problem easily. Imagine that we already have (k-1) partitions in place (the left partition) and we are trying to put the last separator (the (k-1)th separator). What are the possible locations to put the last separator? It must lie somewhere between the (j-1)th and jth element, where 1 = j = n. Once we have the last separator in place, we have completed all k partitions. The cost of this partition arrangement can be readily calculated as the larger of the two quantities below:

    i) The cost of the last partition, {i=j..n-1} Ai
   ii) The cost of the largest partition formed to the left of j
       (ie, the left partition = { A0, A1, ..., Aj-1 } ).

Now, how do we find ii)? It turns out that we want to place the remaining (k-2) separators such that the left partition is divided as fairly as possible, which leads to another valid sub-problem itself. Therefore, we can solve it recursively!

By defining M[n, k] as the optimum cost of a partition arrangement with n total blocks from the first block and k partitions, the recurrence relation can be stated as follow:

                 n                n-1
M[n, k] = min { max { M[j, k-1],  Ai } }
                j=1               i=j

The base cases are:

M[1, k] = A0
          n-1
M[n, 1] =  Ai
          i=0

Therefore, the brute force solution can then be coded directly from the recurrence relation above:

As you already knew, the brute force solution is definitely not very efficient. It is exponential in run time complexity due to re-computation of the same values over and over again. We can do much better by caching our results in a kxN table utilizing Dynamic programming (DP). The table has to be constructed in a way such that the sub-problems are calculated first in a bottom-up fashion.

Each entry in the table needs O(N2) time to calculate. This is due to the summation term ({i=j..n-1} Ai) needs O(N) time, and on top of that you need to find the minimum across all partitions which increases the complexity by an order to O(N2). Since there are a total of kN entries in the table, the overall run time complexity has to be O(kN3).

It is easy to further reduce the complexity down to O(kN2). The extra calculation of the summation term ({i=j..n-1} Ai) can be easily avoided by caching the results using an array that stores cumulative sums.

Below is the DP solution with O(kN2) run time and using O(kN) space complexity.

Follow up:
Could you think of another non DP algorithm which doesn’t requires any extra space?

» Continue reading Part II: The Painter’s Partition Problem.

VN:F [1.9.22_1171]
Rating: 4.4/5 (10 votes cast)
The Painter's Partition Problem Part I, 4.4 out of 5 based on 10 ratings

31 responses to The Painter’s Partition Problem Part I

  1. Hi, I like your posts very much, here just a simple question:

    For this:

    for (int j = 1; j <= n; j++)
    best = min(best, max(partition(A, j, k-1), sum(A, j, n-1)));

    Should it be fine if j start from k-1 rather than 1?

    VA:F [1.9.22_1171]
    0
    • Hey Vanessa,
      Yes this is fine, and a sharp observation from you :)

      I chose to start j from 1 instead of k-1, since this solves the more general case. Note that the original problem states that a painter can choose to do nothing, which translates to the following equivalent problem:
      Given an array of non-negative integers A and a positive integer k, we want to:
      Divide A into k or fewer partitions.
      such that the maximum sum over all the partitions is minimized.

      It is true that in the optimal case, we always divide A into exactly k partitions, not fewer.
      This is because fewer partitions (less painter) will always lead to a direct increase in the cost of time to finish painting (which is not optimal).

      VN:F [1.9.22_1171]
      +1
  2. How are you compensating for each painter’s speed?

    VA:F [1.9.22_1171]
    +1
    • Assume each painter’s speed is the same. If not then it’s a much harder problem.

      VN:F [1.9.22_1171]
      +1
  3. Just one observation. In the DP method, since the M[i,k-1] for i=n:1, and the cumulative sum are both monotonic, one should be able to use the binary search to further speed up the minimum search.

    VA:F [1.9.22_1171]
    -1
  4. “There are K painters available and you are also given how much time a painter takes to paint 1 unit of board.”
    Doesn’t that imply that each painter has a different speed?

    VA:F [1.9.22_1171]
    +1
  5. K said on April 18, 2011

    I don’t understand how the following constraint was dealt with in the solution:

    “…under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}”

    VA:F [1.9.22_1171]
    0
  6. Ur explaination is awesome..:) :) . and the kind of challeneg to pose to the visitor, they are jus facinating..:)
    Thanks a lot..:) and keep posting..:)

    VA:F [1.9.22_1171]
    0
  7. lets say if you have two boards with lengths 100 and 100 and two painters with speeds 1 and 100.
    If you give to each of them one board then the total time will be 100 while if you give both of the boards to the second painter the total time will be 2.

    VA:F [1.9.22_1171]
    +1
  8. best = min(best, max(partition(A, j, k-1), sum(A, j, n-1)));

    should be

    best = min(best, max(partition(A, j-1, k-1), sum(A, j, n-1)));

    VA:F [1.9.22_1171]
    +1
  9. Seems like you get ‘index out of bound’ in the first code example.
    Observe that when j reaches n in the loop, you are going to call

    .

    VA:F [1.9.22_1171]
    0
  10. I don’t understand the problem itself. If I interpret the statement as it is, why can’t we just ask the fastest painter to paint all the boards?

    VA:F [1.9.22_1171]
    0
  11. Im not sure but your recursivly defined Algorithm didnt give me the perfect solution for n=[4000-400], k=2 and elements from 0 to 10000. Maybe i did sth wrong converting ur code into php…
    here a simple example given a couple of pictures:
    A := {95, 31, 13, 87, 71, 48, 37, 73, 64, 93}
    Sum of this is 612 best will be 306

    My Result was not perfect but
    M := {31, 93, 37, 87, 64}
    Sum of this is 300 so difference is 12

    The result with my implementation of ur code is 226 wich is far off in fact by 160

    VA:F [1.9.22_1171]
    0
  12. What about solution by binary searching + greedy?
    by binary search we choose time, then in greedy way we assign boards to painters.

    int l = 0, r= INT_INF ;
    while (l > 1;
    for (int i = 0, kk = k, mm = m ; i mm)
    {
    mm = m;
    kk–;
    i–;
    }else mm -= A[i];
    }
    if (!k) l = m + 1;
    else r = m;
    }

    l == r – answer

    VA:F [1.9.22_1171]
    0
    • Problem with code displaying

      VA:F [1.9.22_1171]
      0
  13. For this:

    for (int j = 1; j <= n; j++)
    best = min(best, max(partition(A, j, k-1), sum(A, j, n-1)));

    Should it be j<n rather than j<=n?

    VA:F [1.9.22_1171]
    0
  14. The code can be reduced one step further in the inner loop.

    VN:F [1.9.22_1171]
    0
  15. Recursive solution with Dynamic Programming in C++:

    Output: 1700
    Time complexity: O(kN^3)

    VA:F [1.9.22_1171]
    0
    • SORRY for the wrong code above:

      F: Painter’s Partition

      Driver:

      Output: 1700
      Time complexity: O(kN^3)

      VA:F [1.9.22_1171]
      +2
      • above code can be used with different values for Time taken by the different painters.

        VA:F [1.9.22_1171]
        +1
  16. I spent about three hours, and still not got through it :(

    VN:F [1.9.22_1171]
    0
  17. My bad, I didn’t follow ur recursive relation’s justification:

    I’m wondering, if it isn’t simply splitting the entire set of N{A0, A1, …, An-1} boards into k groups, such that each group’s sum has least possible abs difference from the avg.(i.e.- {A0 + A1+…+An-1}/k).

    Let’s say, the k groups are:
    G1 = {A0,…,Ai}, G2= {Ai+1, …, Aj} …, Gk = {Ak, … An-1}

    The answer being the sum of the set (with maximum total board length), say some Gr has max sum.

    VN:F [1.9.22_1171]
    0
    • Code got truncated eariler, reposting.

      VN:F [1.9.22_1171]
      0
      • something’s wrong with this editor, snippet’s getting truncated.

        VN:F [1.9.22_1171]
        0
  18. I think your problem description was *very* unclear. I’m familiar with the partitioning problem (it’s in Skiena’s Algorithm Design Manual) and when I saw you write out the recurrence I laughed because I thought you were stating a much hard problem, where each painter paints “units” of boards individually. Anyways, please work on your clarity. A very simple way to do this is to provide simple and discriminating examples to the reader, they will usually clear up any uncertainties.

    VA:F [1.9.22_1171]
    +2
  19. VA:F [1.9.22_1171]
    0
  20. There’re a lot to consider.

    The question does not indicate:

    (1) Is the painting speed the same across all painters?
    (2) If not, are we forced to use all painters?

    This is critical because if speed is not the same, the optimal solution may not assign all painters to work.

    VA:F [1.9.22_1171]
    0
  21. The DP solution is hard to understand…

    VN:F [1.9.22_1171]
    0
  22. The painter’s partition problem with varying painter speed is not so hard if we make the assumption that painter 1 will be assigned to the leftmost part of the fence, painter 2 will be assigned to the right of painter 1 but left of all other painters, etc. Otherwise, the painter’s partition can be proven to be in 2-exptime through reduction to subset sum.

    We can begin by trying to find a recurrence for N painters and K boards. Either the current painter can be used again for the kth board, resulting in a recurrence relation with the N, K – 1 case or alternatively, a new painter can be used, resulting in a recurrence relation with the N – 1, K – J where 0 < J <= K case. We take the minimum of these two cases to find the solution.

    Java implementation (Still O(n^2K) time):

    public static int painterPartition(int[] boards, int[] painters){

    Point[][] dp = new Point[boards.length][painters.length];

    for (int i = 0; i < painters.length; i++){

    dp[0][i] = new Point(boards[0] * painters[i], boards[0] * painters[i]);

    }

    int sum = 0;

    for (int i = 0; i < boards.length; i++){

    sum += boards[i];
    dp[i][0] = new Point(sum * painters[0], sum * painters[0]);

    }

    for (int i = 1; i < painters.length; i++){

    for (int j = 1; j < boards.length; j++){

    int min = 2147483647;
    sum = 0;

    for (int k = 0; k min){

    dp[j][i] = new Point(min, sum);

    }else{

    dp[j][i] = new Point(Math.max(dp[j - 1][i].x, dp[j - 1][i].y + painters[i] * boards[j]), dp[j - 1][i].y + painters[i] * boards[j]);

    }

    }

    }

    return dp[boards.length - 1][painters.length - 1].x;

    }

    VA:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.