# 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.division();
main.result();
}

size = scan.nextInt();
max_co = size - 1;
}

area_values = new int [size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; 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.

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