Painter problme 2

#1

import java.util.*;
public class Main {
public static boolean isValid(int [] a, int pt, int ans ){
int p = 1, current_no_of_boards = 0;
for(int i = 0;i<a.length;i++){
if(current_no_of_boards<=ans){
current_no_of_boards = current_no_of_boards + a[i];
}else{
current_no_of_boards = a[i];
p++;
if(p>pt){
return false;
}
}
}
return true;
}
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int p = cin.nextInt(), b= cin.nextInt(), sum = 0,arr[] = new int[b];
for(int i = 0;i<arr.length;i++){
arr[i] = cin.nextInt();
sum = sum + arr[i];
}
int l = arr[arr.length-1], h = sum,ans=l;
while(l<=h){
int mid = (l+h)/2;
if(isValid(arr, p, mid)){
ans = mid;
h = mid - 1;
}else{
l = mid + 1;
}
}
System.out.println(sum-ans);
}
}==== what’s the error in the code

#2

hi @AbhishekAhlawat1102
We 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 elementsin the array and this happens when we allot 1 painter all the sections of the board. The lowest possible value of this range is the maximum value of the array max, as in this allocation we can allot max to one painter and divide the other sections such that the cost of them is less than or equal to max and as close as possible to max. 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.

#3

hi @AbhishekAhlawat1102
i have made few changes in your code if you have any doubt you can inbox me.

import java.util.*;

public class temp {
public static boolean isValid(int[] a, int pt, int ans) {
int p = 1, current_no_of_boards = 0;
for (int i = 0; i < a.length; i++) {
if (current_no_of_boards + a[i] <= ans) {
current_no_of_boards = current_no_of_boards + a[i];
} else {
current_no_of_boards = a[i];
p++;
if (p > pt) {
return false;
}
}
}

	return true;
}

public static void main(String args[]) {
	Scanner cin = new Scanner(System.in);
	int p = cin.nextInt(), b = cin.nextInt(), sum = 0, arr[] = new int[b];
	for (int i = 0; i < arr.length; i++) {
		arr[i] = cin.nextInt();
		sum = sum + arr[i];
	}
	int l = 0;
	for (int v : arr) {
		l = Math.max(l, v);
	}
	int h = sum, ans = l;
	while (l <= h) {
		int mid = (l + h) / 2;
		if (isValid(arr, p, mid)) {
			ans = mid;
			h = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	System.out.println(ans);
}

}

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.