Can't find whats wrong in my code

#1

it gives the right answer for my test cases
2 painter 10,50
2 painter 10,20,30,40
3 painter 10,20,60,40,50,30
but fails when submiting in 3 test cases

#2

Hi @10vaibhavsinghnegi,
Can you please share your code as well?

#3

package Arrays;

import java.util.Scanner;

public class q20 {

//partition painter problem

public static void Insertion_sort(int[] arr) {
	for (int count = 1; count < arr.length; count++) {
		int j = count - 1;
		int val = arr[count];
		while (j >= 0 && val < arr[j]) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = val;
	}
}

public static int check(int[] arr, int time, int pc) {
	int val = 0, painter = 1;
	for (int i = 0; i < arr.length; i++) {
		val = val + arr[i];		
		if (val > time) {
			painter++;
			val = 0;
			i--;
			if (painter > pc) {
				return 0;
			}
		}
	}
	return 1;
}

public static int sum(int[] arr) {
	int val = 0;
	for (int i = 0; i < arr.length; i++) {
		val += arr[i];
	}
	return val;
}

public static int BinarySearch(int[] arr, int p) {
	int low = arr[arr.length - 1];
	int high = sum(arr);

	int ans = high;
	while (low <= high) {
		int mid = (low + high) / 2;			
		if (check(arr, mid, p) == 1) {
			if (mid < ans) {
				ans = mid;
			}
			high = mid - 1;

		} else {
			low = mid + 1;
		}
	}
	return ans;
}

public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);
	int K = sc.nextInt();
	int N = sc.nextInt();
	int[] arr = new int[N];

	for (int i = 0; i < arr.length; i++) {
		arr[i] = sc.nextInt();
	}
	Insertion_sort(arr);
	System.out.println(BinarySearch(arr, K));
}

}

#4

hi @10vaibhavsinghnegi,
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.

#5

okay got it…thank you it is working now