108 - Maximum Sum

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

peterlin
New poster
Posts: 5
Joined: Wed Dec 18, 2002 4:46 pm

Post by peterlin »

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

Best wishes,
Peter

Ozton
New poster
Posts: 5
Joined: Sun Jan 05, 2003 10:27 am

Problem 108 Why Time limit exceeded?

Post by 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]
Hi~~^^

Ozton
New poster
Posts: 5
Joined: Sun Jan 05, 2003 10:27 am

[Problem 108] Maximum sum - Compile error...

Post by 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!
Hi~~^^

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

try putting:

Code: Select all

        int tmp = 0; 
At beginning of the block..

Ozton
New poster
Posts: 5
Joined: Sun Jan 05, 2003 10:27 am

^^

Post by Ozton »

Thanks.
but, Time Limit Exceeded...T.T
Hi~~^^

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm

Post by R »

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

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm

[108] WA

Post by 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! :roll:

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm

Post by R »

maybe it's a problem of understanding:

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

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm

Post by 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
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm

Post by 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...

Image

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm

Post by R »

accepted! :D

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.

:x

we really need a website with more input-data!

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

108 maximum sum

Post by epsilon0 »

this problem drove me mad for 24 hours.

:cry:

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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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. :P
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by 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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Post Reply

Return to “Volume 1 (100-199)”