Painter's Partition Problem
Given an array/list of length ‘N’, where the array/list represents the boards and each element of the given array/list represents the length of each board. Some ‘K’ numbers of painters are available to paint these boards. Consider that each unit of a board takes 1 unit of time to paint.
You are supposed to return the area of the minimum time to get this job done of painting all the ‘N’ boards under a constraint that any painter will only paint the continuous sections of boards.
For example :
In the below figure where array/list elements are {2, 1, 5, 6, 2, 3}.
A painter can paint blocks {5,6} or {1,5,6,2} together but not {2,5,6} or {5,6,3}.
Input format :
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of each test case contains two integers ‘N’ and ‘K’ denoting the number of elements in the array/list and number of painters available.
The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output format :
For each test case, print the minimum time required to get the job done.
Note :
You do not need to print anything; it has already been taken care of.
Constraints :
1 <= T <= 5
1 <= N <= 10^4
1 <= K <= N
1 <= ARR[i] <= 10^5
Where ‘T’ is the number of test cases.
'N' is the length of the given array/list (boards).
‘K’ is the number of painters available.
And, ARR[i] denotes the i-th element in the array/list.
Time Limit: 1 sec.
All we need to do is to Divide the boards into k of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized.
We can put the (k - 1)th divider between the ith and (i + 1)th element where i is between 1 and N.
Now the recursive function will just require two conditions that can lead to the result and that will be out the maximum total cost:
- The time is taken in the last partition where the (k - 1)th divider is before element i.
- The maximum cost of any partition already formed to the left of the (k - 1)th divider.
Now to avoid the exponential time complexity we can use Dynamic Programming since it already keeps a track of pre-calculated data and will lead to better results if we can take the data from the dp table.
Consider we have N painters, then painters with index ‘i’ can paint fences only in continuous order. So, this means the first painter will paint some of the fences. Then the second painter paints some of the fences. The same goes for all the painters. This may happen that some painter does not even get a fence to paint.
- We will use Dynamic Programming for solving this problem. Here, we will also use a very well-defined dynamic programming technique which is a prefix sum for taking the sum of time in O(1) time complexity.
- First, we will solve the problem for a single painter. Then we will solve in a bottom-up manner for the number of painters = 2, 3, 4,… n.
- For solving the problem for an ith painter, we will find the time taken by the ith painter to paint fence k to j. Here, we have considered ith painter will paint fence k to j, and fences from 1 to (k - 1) are painted by (i - 1) painters.
- The answer for this subproblem should be the maximum time taken by either of (i - 1) painters or the ith painter.
- In this manner, we keep on solving smaller subproblems.
- Then, combining the result of these smaller subproblems we solve our initial problem.
How can we improvise our solution, we can use binary search for that.
- We can see that the highest possible value in this range is the sum of all the elements in the array and this happens when we allot 1 painter to all the sections of the board.
- The lowest possible value of this range is the maximum value of the array/list maximum, as in this allocation, we can allot maximum to one painter and divide the other sections such that the cost of them is less than or equal to the max and as close as possible to the max.
- If we consider we use x painters in the above scenarios, it is obvious that as the value in the range increases, the value of x decreases, and if the value in the range decreases then the value of x increases.
- From this, we can find the target value when x = k and use a helper function to find x, the minimum number of painters required when the maximum length of section a painter can paint is given.
