## The Painter’s Partition Problem Part I

April 5, 2011 in dynamic programming

You have to paint N boards of length {A

_{0}, A_{1}, A_{2}… A_{N-1}}. There areKpainters 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:

*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} A_{i} / *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 *j*th 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} A_{i}ii) The cost of the largest partition formed to the left ofj(ie, the left partition = { A_{0}, A_{1}, ..., A_{j-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],∑A_{i}} } j=1 i=j

The base cases are:

M[1, k] = A_{0}n-1 M[n, 1] =∑A_{i }i=0

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | int sum(int A[], int from, int to) { int total = 0; for (int i = from; i <= to; i++) total += A[i]; return total; } int partition(int A[], int n, int k) { if (k == 1) return sum(A, 0, n-1); if (n == 1) return A[0]; int best = INT_MAX; for (int j = 1; j <= n; j++) best = min(best, max(partition(A, j, k-1), sum(A, j, n-1))); return best; } |

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 *k*x*N* 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*(*N*^{2}) time to calculate. This is due to the summation term (**∑**{i=j..n-1} A_{i}) 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(*N*^{2}). Since there are a total of *kN* entries in the table, the overall run time complexity has to be *O*(*k**N*^{3}).

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

Below is the DP solution with *O*(*kN*^{2}) run time and using *O*(*kN*) space complexity.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | const int MAX_N = 100; int findMax(int A[], int n, int k) { int M[MAX_N+1][MAX_N+1] = {0}; int cum[MAX_N+1] = {0}; for (int i = 1; i <= n; i++) cum[i] = cum[i-1] + A[i-1]; for (int i = 1; i <= n; i++) M[i][1] = cum[i]; for (int i = 1; i <= k; i++) M[1][i] = A[0]; for (int i = 2; i <= k; i++) { for (int j = 2; j <= n; j++) { int best = INT_MAX; for (int p = 1; p <= j; p++) { best = min(best, max(M[p][i-1], cum[j]-cum[p])); } M[j][i] = best; } } return M[n][k]; } |

**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.**

Vanessa said on April 7, 2011

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?

01337c0d3r said on April 7, 2011

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 fewerpartitions.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).

+1coder said on April 7, 2011

How are you compensating for each painter’s speed?

+11337c0d3r said on April 7, 2011

Assume each painter’s speed is the same. If not then it’s a much harder problem.

+1Sparsebase said on April 10, 2011

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.

-1Eric said on April 16, 2011

“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?

+1K 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}”

0Ajit said on April 19, 2011

Ur explaination is awesome..:) . and the kind of challeneg to pose to the visitor, they are jus facinating..:)

Thanks a lot..:) and keep posting..:)

0lopp said on May 12, 2011

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.

+1Ming said on July 21, 2011

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)));

+1anatoliy said on August 11, 2011

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

.

0Machine Learning said on August 21, 2011

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?

0mjb4 said on January 15, 2012

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

0upi said on March 26, 2012

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

0upi said on March 26, 2012

Problem with code displaying

0upi said on March 26, 2012

Again Code is on http://codepaste.ru/9865/

0Moussa said on May 5, 2012

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?

0Venki said on June 3, 2012

The code can be reduced one step further in the inner loop.

0Akshay said on June 29, 2013

Recursive solution with Dynamic Programming in C++:

Output: 1700

Time complexity: O(kN^3)

0Akshay said on June 29, 2013

SORRY for the wrong code above:

F: Painter’s Partition

Driver:

Output: 1700

Time complexity: O(kN^3)

+2Akshay said on June 29, 2013

above code can be used with different values for Time taken by the different painters.

+1robotony said on September 8, 2013

I spent about three hours, and still not got through it

0theGhost said on September 25, 2013

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.

0theGhost said on September 25, 2013

Code got truncated eariler, reposting.

0theGhost said on September 25, 2013

something’s wrong with this editor, snippet’s getting truncated.

0matt said on November 9, 2013

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.

+2Zheng Xu said on January 17, 2014

0theOtherWC said on January 30, 2014

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.

0theOtherWC said on January 30, 2014

Ignore this. No matter what we need these k painters to achieve maximum.

0Yunsong Wu said on May 28, 2014

The DP solution is hard to understand…

0William Li said on August 3, 2014

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;

}

0Jedizorro said on November 1, 2014

There is one natural recursion solution to this problem. Although it sucks in time complexity, i.e. O((N-K)!), the pseudocode can be pretty neat with a 2-liner recursion.

BASE CASE:

If N == K (# of boards equals to # of painters), then the ShortestPaintingTime(A[N]) must be max(A1, A2, …, AN), because you can’t beat the time spent on the longest board.

If N > K, then according to Pigeonhole Principle, a.k.a. Drawer Principle, Shelf Principle, etc.

http://en.wikipedia.org/wiki/Pigeonhole_principle

That at least one painter will have to paint at least 2 boards, and according to the original statement of this problem, the 2 boards must be adjacent. Therefore:

ShortestPaintingTime(A[N]) = min(

ShortestPaintingTime((A1+A2), A3, A4, …, AN),

ShortestPaintingTime(A1, (A2+A3), A4, …, AN),

…

ShortestPaintingTime(A1, A2, A3, …, (A(N-1)+AN))

)

0