You have to paint N boards of length {A₀, A₁, A₂ … A_N-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:

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 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(N²) 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²). Since there are a total of kN entries in the table, the overall run time complexity has to be O(kN³).

It is easy to further reduce the complexity down to O(kN²). 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²) 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.