Please look into this doubt , one is already open
No one opened my previous doubts on this
package Arrays;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
public class PainterPartitionApproachNew {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int painters = scanner.nextInt();
int boards = scanner.nextInt();
int[] arr = new int[boards];
for (int i = 0; i < boards; i++) {
arr[i] = scanner.nextInt();
}
Arrays.sort(arr);
System.out.println(area(arr, painters));
}
public static int helper(int[] arr, int gap, int painters) {
int sum = 0;
int k = --painters;
int max = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (sum > gap && i != arr.length - 1) {
if (sum - arr[i] > max && i != arr.length - 1) {
max = sum - arr[i];
k--;
sum = arr[i];
}
}
if (i == arr.length - 1) {
if (sum > gap) {
if (sum - arr[i] > max) {
max = sum - arr[i];
if (arr[i] > max) {
max = arr[i];
}
}
k--;
}else{
if(sum>max){
max= sum;
}
}
}
}
if (k >= 0) {
return max;
} else {
return -1;
}
}
public static int area(int[] arr, int painters) {
int lo = arr[arr.length - 1];
int high = 0;
for (int i = 0; i < arr.length; i++) {
high += arr[i];
}
int ans = 0;
while (lo <= high) {
int mid = lo + (high - lo) / 2;
if (helper(arr, mid, painters) > 0) {
ans = helper(arr, mid, painters);
high = mid - 1;
} else {
lo = mid + 1;
}
}
return ans;
}
}
Hey this is my final code my test cases 0 2 4 are failing, please suggest changes in this code or send me the improved one , I am unable to make more changes in this one
Please tell me the error I havent been able to debug this for past 2-3 days.
Thanks
Sure. Just give me a few minutes, I will answer all your queries.
Great
Thanks a lot
approaching limit
You cannot sort the array initially. That condition will give you WA.
For example:
2
4
20 30 40 10
For this the correct answer is 50. But your code will give 60. Your code processes the array 10 20 30 40 but the actual array is 20 30 40 10.
This is because it is given in the question: Every painter can paint only contiguous segments of boards.
If you sort the array this condition is violated.
package Arrays;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
public class PainterPartitionApproachNew {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int painters = scanner.nextInt();
int boards = scanner.nextInt();
int[] arr = new int[boards];
for (int i = 0; i < boards; i++) {
arr[i] = scanner.nextInt();
}
System.out.println(area(arr, painters));
}
public static int helper(int[] arr, int gap, int painters) {
int sum = 0;
int k = --painters;
int max = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (sum > gap && i != arr.length - 1) {
if (sum - arr[i] > max && i != arr.length - 1) {
max = sum - arr[i];
k--;
sum = arr[i];
}
}
if (i == arr.length - 1) {
if (sum > gap) {
if (sum - arr[i] > max) {
max = sum - arr[i];
if (arr[i] > max) {
max = arr[i];
}
}
k--;
}else{
if(sum>max){
max= sum;
}
}
}
}
if (k >= 0) {
return max;
} else {
return -1;
}
}
public static int area(int[] arr, int painters) {
int lo = Integer.MIN_VALUE;
for(int i =0;i<arr.length;i++){
if(arr[i]>lo){
lo = arr[i];
}
}
int high = 0;
for (int i = 0; i < arr.length; i++) {
high += arr[i];
}
int ans = 0;
while (lo <= high) {
int mid = lo + (high - lo) / 2;
if (helper(arr, mid, painters) > 0) {
ans = helper(arr, mid, painters);
high = mid - 1;
} else {
lo = mid + 1;
}
}
return ans;
}
}
Hey I changed my code as you suggested
But it is still failing test case 0 and 3
Please have a look at this too
@bhavik911,
Wrong answer for testcase:
3
9
640 435 647 352 8 90 960 329 859
Correct output:
1722
Your output:
1739
352 8 90 960 329 their sum is equal to 1739 when mid is 1799,
640 435 647 their sum is equal to 1722
So shouldn’t the answer be 1739??
@bhavik911,
No buddy. Debug your code.
Suggested approach:\
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 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.
I get the suggested approach , I think I may used the same one as this was also suggested in the prev doubts , I also debugged It , it is showing 1739 but I don’t understand why it shouldnt be 1739 if we take the case as prev one
352 8 90 960 329 their sum is equal to 1739 when mid is 1799, 640 435 647 their sum is equal to 1722 So shouldn’t the answer be 1739??
In this how would 1722 would be possible as 1739 is max?
I dont get it ://