108 - Maximum Sum

[peterlin]

Excuse me,
May I ask what's the algo is O(n^3) for this problem ?

Best wishes,
Peter

[Ozton]

WhyWhyWhy???

[c]
#include <stdio.h>

int N, matrix[100][100], max_value;

void nbyn_sum(int);
int sum_matrix(int, int, int, int);

int main()
{

int i, j;

while (scanf("%d", &N) == 1) {

max_value = 0;

for (i = 0; i < N; i++)
for (j = 0; j < N; j++) {
scanf("%d", &matrix[j]);
max_value += matrix[j];
}

for (i = N - 1; i > 1; i--)
nbyn_sum(i);

printf("%d\n", max_value);

}

return 0;

}

void nbyn_sum(int nbyn) {

int i, j, k, l, rectangle_sum;

for (i = 0; i <= N - nbyn; i++)
for (j = 0; j <= N - nbyn; j++) {

for (k = i + nbyn - 1; k < N; k++)
for (l = j + nbyn - 1; l < N; l++) {

rectangle_sum = sum_matrix(i, k, j, l);

if (rectangle_sum > max_value)
max_value = rectangle_sum;

}

}

}

int sum_matrix(int start_row, int end_row, int start_col, int end_col) {

int i, j, sum = 0;

for (i = start_row; i <= end_row; i++)
for (j = start_col; j <= end_col; j++)
sum += matrix[j];

return sum;

}
[/c]

[Ozton]

My FreeBSD gcc or g++ compile no error.
but Online judge compile error.
[c]
#include <stdio.h>

int N, matrix[100][100], max_value;

void nbyn_sum(int);
int sum_matrix(int, int, int);

int main()
{

int i, j;

while (scanf("%d", &N) == 1) {

max_value = 0;

for (i = 0; i < N; i++)
for (j = 0; j < N; j++) {
scanf("%d", &matrix[j]);
max_value += matrix[j];
}

for (i = N - 1; i > 1; i--)
nbyn_sum(i);

printf("%d\n", max_value);

}

return 0;

}

void nbyn_sum(int nbyn) {

int i, j, k, l, rectangle_sum;

for (i = 0; i <= N - nbyn; i++)
for (j = 0; j <= N - nbyn; j++) {

rectangle_sum = sum_matrix(i, j, nbyn);

if (rectangle_sum > max_value)
max_value = rectangle_sum;

int tmp = 0;

for (k = j + nbyn; k < N; k++) {

for (l = i; l < nbyn; l++)
tmp += matrix[l][k];

if (rectangle_sum + tmp > max_value)
max_value = rectangle_sum + tmp;

}

tmp = 0;

for (k = i + nbyn; k < N; k++) {

for (l = j; l < nbyn; l++)
tmp += matrix[k][l];

if (rectangle_sum + tmp > max_value)
max_value = rectangle_sum + tmp;

}

}

}

int sum_matrix(int row, int col, int nbyn) {

int i, j, sum = 0;

for (i = row; i < row + nbyn; i++)
for (j = col; j < col + nbyn; j++)
sum += matrix[j];

return sum;

}
[/c]

Please test!

[Larry]

try putting:

Code: Select all

        int tmp = 0; 

At beginning of the block..

[Ozton]

Thanks.
but, Time Limit Exceeded...T.T

[R]

well, i think you got it. closing your output with a friendly '\n' is always a good idea.

[R]

ola,

i think i have solved 108 - but i still get WA.

can someone provide me with additional input/output data to help me track the bug(s) down? or some ideas of extreme cases?

i does 1x1 up to 100x100 tables in a reasonable time (and in fact, i get no timeout ) and it also handles negative values correctly.

i'm stuck

thx!

[R]

maybe it's a problem of understanding:

"sub-array of size 1x1" means a single element, doesn't it?

[R]

what does your accepted solutions print, when N=0?

*edit*
nah. that shouldn't be a problem, since the problem states

a single positive interger N

[R]

omg, i think i've found it.

The sum of a rectangle is the sum of all the elements in that rectangle.

aaahhh! i thought all the elements on the rectangle and not the ones within.

so
1 1 1
1 1 1
1 1 1
should give 9 and i thought it should be 8.

well, let's see, i will try to rewrite the program and maybe i get an accept then...

[R]

accepted!

if i just had one example with a maximal sub-rectangle of size 3x3 or greater, that would have saved me 2 hours debugging with one sheet of paper and 30 lines of source-code.



we really need a website with more input-data!

[epsilon0]

this problem drove me mad for 24 hours.



i don't see the O(n^3) solution...

i'll try to code a naive algorithm but i'm sure it will be too slow.

please explain me how it can be solved faster.

the same problem in one dimension (ie a matrix 1xN) has an O(n^2) solution? or better?

HELP

[epsilon0]

ok i solved it in O(n^3) (or so i think)

i found the 0(n) solution for the 1 dim problem and then worked from there.

it ran in 0.031 second on judge's PC.

it would be more like O(n^3 + n) actually (which is about the same anyway)

my concern is about the O(n^3) part, i'm not totally convinced of it's cubicness.

[Larry]

Well, the point of the big Oh is that O( n^3 + n ) is O( n^3 ).

It's a nice problem. I got it AC.. though it took me too long.

[epsilon0]

actually my solution goes like:

loop i from 1 to n
+ loop ii from i to n
+ + loop k from 1 to n
+ + + solve an O(1) problem
+ + solve an O(n) problem

so the complexity would be n(n+1)/2 * (n * 1 + n)
so n^3 + n^2