Painter's Partition Problem

#1

For this problem I thought of using Binary Search, and create a search space to find the minimum time. And choose sum of the array as the highest value in the search space. But I am not able decide the lowest value and don’t no how to proceed further. Can you pls help?

#2

Hey @anugrahrastogi
sum of the array as the highest value in the search space and lowest value is 0

#3

why the lowest value should be 0? And how should I proceed further?

#4

@anugrahrastog its my assumption lowest is 0 . painter can paint Zero length of board …
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (isitpossible(arr, mid, nop)) {
ans = mid;
hi= mid - 1;
} else {
lo = mid + 1;
}
}
System.out.println(ans);
write isitpossible logic

#5

can you pls explain me what does isitpossible function do and what is the parameter nop? (how would i know how this function works without any explanation)
I did not ask you for the code (and that to the code is without explanation, how am i able to understand how this code works), I want explanation and how to approach the problem.

#6

@anugrahrastogi
what is the parameter nop // Number of Painter ( K )
We know that the invariant of binary search has two main parts:

  • the target value would always be in the searching range.
  • the searching range will decrease in each loop so that the termination can be reached.

We also know that the values in this range must be in sorted order. Here our target value is the maximum sum of a contiguous section in the optimal allocation of boards. Now how can we apply binary search for this? We can fix the possible low to high range for the target value and narrow down our search to get the optimal allocation.

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 all the sections of the board. The lowest possible value 0. Now 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 vice-versa. 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.

#7

I solved this problem, here is the code: https://ide.codingblocks.com/s/279438
But i am not able to pass some test cases and i am not able to identify what I am missing. Can you pls tell?

#8

@anugrahrastogi
code is almost correct
I commented in your code
correct code

#9

I am not able to understand what is wrong in my logic and what test cases am i missing?

#10

@anugrahrastogi
In isitpossible fun
for(int i = 0; i < arr.length; ) {

		//total += arr[i];

// total me arr [i] tabhi add hoga jb total + arr[i]<=min_time
try for this input
2
2
1 10
Debug your code