# Orchard Partitioning in to close-to-equal sectors

The task (from this site) is to create a program that will solve a problem where a matrix (size n * n), which contains integers, is to be divided into four parts, the sums of which are as close to each other as possible. They have to be divided left to right all the way and those parts (top/bottom), can be divided without the imaginary line touching. The output is the difference between the part with the largerst sum and the one with the smallest.

public class Main {
Scanner scan = new Scanner(System.in);
int [][] area_values;
int size;
int max_co;
int y_divide;
int x_divide_top;
int x_divide_bottom;
int left_top;
int right_top;
int left_bottom;
int right_bottom;
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Main main = new Main();
main.read();
main.division();
main.result();
}

void read() {
size = scan.nextInt();
arrayLoad();
max_co = size - 1;
}

void arrayLoad() {
area_values = new int [size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
add(scan.nextInt(),i,j);
}
}
}

void add(int num, int x, int y) {
for (int i = x; i < size; i++) {
for (int j = y; j < size; j++) {
area_values[i][j] += num;
}
}
}

int block_value(int by, int bx, int ey, int ex) {
int value = area_values[ex][ey];
if (bx == 0 && by ==0) {}
else if (bx != 0 && by !=0) {
value -= area_values[bx-1][ey];
value -= area_values[ex][by-1];
value += area_values[bx-1][by-1];
}
else if (bx == 0) {
value -= area_values[ex][by-1];
}
else if (by == 0) {
value -= area_values[bx-1][ey];
}
return value;
}

void division() {
east_to_west();
top_division();
bottom_division();
}

void top_division() {
int left;
int right;
int min_Dif = Integer.MAX_VALUE;
int dif;
for (int i = 0; i < max_co; i++) {
left = block_value(0,0,i,y_divide);
right = block_value(i+1,0,max_co,y_divide);
dif = Math.abs(left-right);
if (dif < min_Dif) {
min_Dif = dif;
left_top = left;
right_top = right;
}
}
}

void bottom_division() {
int left;
int right;
int min_Dif = Integer.MAX_VALUE;
int dif;
for (int i = 0; i < max_co; i++) {
left = block_value(0,y_divide+1,i,max_co);
right = block_value(i+1,y_divide+1,max_co,max_co);
dif = Math.abs(left-right);
if (dif < min_Dif) {
min_Dif = dif;
left_bottom = left;
right_bottom = right;
}
}
}

void east_to_west() {
int top;
int bottom;
int min_Dif = Integer.MAX_VALUE;
int dif;
int y_div = 1;
for (int i = 0; i < max_co; i++) {
top = block_value(0,0,max_co,i);
bottom = block_value(0,i+1,max_co,max_co);
dif = Math.abs(top-bottom);
if (dif < min_Dif) {
min_Dif = dif;
y_div = i;
}
}
y_divide = y_div;
}

void result() {
int min_top = Math.min(left_top, right_top);
int min_bottom = Math.min(left_bottom, right_bottom);
int min = Math.min(min_top, min_bottom);
int max_top = Math.max(left_top, right_top);
int max_bottom = Math.max(left_bottom, right_bottom);
int max = Math.max(max_top, max_bottom);
int result = Math.abs(max-min);
System.out.println(result);
}
}


It works just fine, but I always exceed the time limit by fractions of a second. Is there any way of speeding this up? I was told about using bufferedReader, instead of Scanner, but how would I do that? Some of the input comes from a keyboard, number by number, and some from a file.

## 1 Answer

You definitely should use a BufferedReader. Take a look at the class I use when I am solving problems of this kind.

Besides, your reading subroutine works in O(n4), which, for n about 103, is a bit too much. I think your program just gets killed after it exceeds the time limit, leaving you thinking that you are very close.

You seem to want to construct a matrix of patrial sums. Can you think of a way to construct in it O(n2)?

Also, your solution is not correct. Consider a test

4
0 4 0 0
2 0 0 0
2 0 0 0
0 2 0 0


Your solution outputs 4, when the correct answer is obviously 2.

• Thanks, I will try to come up with an edit for the reading routine. I will also look into my solution, but I believe it is correct, since all of the sets of data it works thorugh in time (up to around 400x400) come up with the correct output number. – Simon Feb 26 '14 at 21:50
• Yes, your test makes it fail and I now see why. It does not see the benefit of splitting it after the second line, because it sees no difference between 6,4 and 4,6, therefore making the wrong decision. The fact that if given enough time it comes to the correct conclusion in all of the test data is probably due to the fact that the school chooses data, where the first step does not have more than one solution. But I will definetly try to do it anyways. – Simon Feb 26 '14 at 22:08
• That's kinda sad. You should approach your professor and ask him to strengthen the tests. – abra Feb 26 '14 at 22:15
• Or they just missed it. Also, most of the people at our school are just being introduced to programming. – Simon Feb 26 '14 at 22:18