Painters Partition Problem

Example

Input 1: M = 5, N = 3, Arr = {5, 25, 30, 20, 15}

Output 1: 35

Input 2: M = 4, N = 2, Arr = {5, 6, 5, 6}

Output 2: 11

Input 3: M = 4, N = 2, Arr = {10, 15, 20, 25}

Output 3: 45

Example Explanation

Explanation for Input 1: Allocation for Painter 1: {5,25} Allocation for Painter 2: {30} Allocation for Painter 3: {20,15} When all of the painters have completed their work, the job will be completed, i.e., at time = $max (5+10, 30, 20+15) = 35$.

Explanation for Input 2: Here, we’ll divide our array into two parts and assign the first two values to the first painter, i.e., 11, and the last two values, i.e., 11, to the second painter.

Explanation for Input 3: Similarly, here also, we’ll divide our array into two parts and assign the first two values to the first painter, i.e., 25, and the last two values, i.e., 45, to the second painter. So the answer would be 45.

Constraints

1 <= T <= 4 1 <= M <= 10^4 1 <= N <= M 1 <= Arr [i] <= 10^5

Where ‘T’ is the number of test cases, "M" is the length of the given array (boards). "N" is the number of painters available. Arr[i] denotes the i-th element in the array.

Approach 1: Brute-Force Solution

The brute force approach could be that we consider all possible sets of contiguous partitions and we will calculate the maximum sum partition in each case and return the minimum of all these cases. Let’s see properly how it could be done.

Algorithm:

We can assume that we already have (N-1) partitions using (N-2) dividers. Now we have to make the (N-1)th divider to get N partitions. So simply, we can put in the (N-1)th divider to get N partitions. We will put the (N-1)th divider between the ith and (i+1)th elements, where i = 1 to n.

We can calculate the total cost for the above arrangement as the maximum of the following:

• The final partition's cost would be sum(Ai..An), where the (N-1)th divider comes before element i.
• The maximum cost of any partition formed to the left of the (N-1)th divider.

See the below recurrence relation:

Coding Implementation:

C++

Output:

Java

Output:

Python

Output:

Time Complexity

Time complexity would be exponential for the above algorithm. $M*M*M*M$ ......... $N$ times = $O(M^N)$ where, 'N' is the number of painters. 'M' is the length of the given array (boards).

Space Complexity

Each function call of a recursive algorithm will take $O(N)$ space, and if the maximum depth of the recursion tree is 'M' then the recursive algorithm's space complexity will be $O(NM)$.

Approach 2: Using Binary Search

In the previous algorithm, we discussed how we could solve this problem recursively by breaking it into subproblems, but that algorithm was taking more time and space. Now we will discuss a more efficient approach using binary search.

Algorithm

Here, our target value (that would always be in the searching range) is the maximum sum of a contiguous section in the allocation of boards. The highest value would always be the sum of all the elements in the array, and this will happen only when we allot 1 painter to all the sections of the board, and the lowest value could be the maximum value of the array.

Let's see how it works:

1. We can allocate the maximum to one painter and divide the remaining sections so that their costs are minimized.
2. One interesting thing is that if we have p painters, the values in the range increase, and the value of p decreases, and vice-versa.
3. From this, we can find the target value when p=N.
4. Now, we can easily find the target values when p=N and use our helper functions to find p and the minimum number of painters required when there is a maximum length of section a painter can paint.

Code Implementation

C++

Output:

Java

Output:

Python

Output:

Time Complexity

$O(MlogM)$, where M is the length of the input array. Here we are traversing an array of size M and the partition function is taking the time $logM$, so the total complexity would be $O(MlogM)$.

Space Complexity

O(1), as no extra space is used.