Table of Contents
Problem Statement
The Painter’s Partition problem states that we have some fences and we have some painters. We want to minimize the time of painting all the fences by painters. There is a bound on the order of painting the fences by painters. Consider we have n painters, then painter 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.
Example
Size of fence : 10 40 40 10 Time of painting a unit length of fence : 1 Number of Painters : 2
50
Explanation: We will assign fence 1 and 2 to the first painter and 3, 4 to the second painter. If we would have assigned 1 fence to the first painter and 2, 3, and 4 to the second painter. Then the first painter takes time = 10, and the second takes time = 90. The maximum time taken by all the painters is the total time taken to paint the fence. This is because all of the painters start painting at the same time t = 0. Thus, any other way than this will result in worse results.
Size of fence : 1 100 Time of painting a unit length of fence : 1 Number of Painters : 2
100
Explanation: We will assign fence 1 to the first painter and 2 to the second painter. Since the total time is equal to the maximum time taken by any of the painters. Thus, the output is 100.
Approach for painter’s partition problem
We will use Dynamic Programming for solving this problem. Here, we will also use a very well defined dynamic programming technique (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) is 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 (the painter’s partition problem).
Code
C++ Code for painter’s partition problem
#include <bits/stdc++.h>
using namespace std;
long long int solvePaintersPartitionProblem(long long int numberOfPainters, long long int timePerUnit, vector<long long int>& fenceSize){
int numberOfFences = fenceSize.size();
if(numberOfFences == 0)return 0;
vector<long long int> pref(numberOfFences); // stores the prefix sum for faster sum calculation over the range
pref[0] = (fenceSize[0] * timePerUnit);
for(int i=1;i<numberOfFences;i++) {
pref[i] = (fenceSize[i] * timePerUnit);
pref[i] = (pref[i] + pref[i-1]);
}
long long int dp[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
for(int i=0;i<numberOfPainters;i++){
for(int j=0;j<numberOfFences;j++)
dp[i][j] = LONG_MAX;
}
// Filling the values for first painter
for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];
// Now solving for painters 2, 3, 4......n
for(int i=1;i<numberOfPainters;i++){
for(int j=i;j<numberOfFences;j++){
for(int k=i;k<=j;k++){
long long int timeTakenForithPainter = pref[j] - pref[k-1];
dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], timeTakenForithPainter));
}
}
}
if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
return dp[numberOfPainters-1][numberOfFences-1];
}
int main(){
int t;cin>>t;
while(t--){
long long int numberOfPainters, numberOfFences, timePerUnit;
cin>>numberOfPainters>>timePerUnit>>numberOfFences;
vector<long long int> fenceSize(numberOfFences);
for(int i=0;i<numberOfFences;i++) cin>>fenceSize[i];
long long int ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, fenceSize);
cout<<ans<<endl;
}
}2 2 5 2 // number of painters, time taken paint a unit length of fence and number of fences 1 10 // fences size 10 1 4 1 8 11 3
50 11
Java Code for painter’s partition problem
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static long solvePaintersPartitionProblem(int numberOfPainters, long timePerUnit, int numberOfFences, long fenceSize[]){
if(numberOfFences == 0)return 0;
long pref[] = new long[numberOfFences]; // stores the prefix sum for faster sum calculation over the range
pref[0] = (fenceSize[0] * timePerUnit);
for(int i=1;i<numberOfFences;i++) {
pref[i] = (fenceSize[i] * timePerUnit);
pref[i] = (pref[i] + pref[i-1]);
}
long dp[][] = new long[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
for(int i=0;i<numberOfPainters;i++){
for(int j=0;j<numberOfFences;j++)
dp[i][j] = Long.MAX_VALUE;
}
// Filling the values for first painter
for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];
// Now solving for painters 2, 3, 4......n
for(int i=1;i<numberOfPainters;i++){
for(int j=i;j<numberOfFences;j++){
for(int k=i;k<=j;k++){
long timeTakenForithPainter = pref[j] - pref[k-1];
dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][k-1], timeTakenForithPainter));
}
}
}
if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
return dp[numberOfPainters-1][numberOfFences-1];
}
public static void main (String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int numberOfPainters = sc.nextInt();
long timePerUnit = sc.nextLong();
int numberOfFences = sc.nextInt();
long fenceSize[] = new long[numberOfFences];
for(int i=0;i<numberOfFences;i++) fenceSize[i] = sc.nextLong();
long ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, numberOfFences, fenceSize);
System.out.println(ans);
}
}
}2 2 5 2// number of painters, time taken paint a unit length of fence and number of fences 1 10 // fences size 10 1 4 1 8 11 3
50 11
Complexity Analysis
Time Complexity: O(N*M^2)
where N = number of painters
M = number of fences, since we are here using prefix sum for finding the time spent by ith painter we have reduced time complexity.
The first loop runs over number of painters, and nested loops run over the number of fences. If N = M, time complexity: O(N^3) for painter’s partition problem.
Space Complexity: O(N*M)
Where N = number of painters
M = number of fences, because we have a 2D DP array of dimensions N*M. Thus we have a polynomial space complexity solution for the painter’s partition problem.