108  Maximum Sum
Moderator: Board moderators
Problem 108 Why Time limit exceeded?
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]
[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~~^^
[Problem 108] Maximum sum  Compile error...
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!
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~~^^

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
try putting:
At beginning of the block..
Code: Select all
int tmp = 0;
[108] WA
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!
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!
omg, i think i've found it.
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...
aaahhh! i thought all the elements on the rectangle and not the ones within.The sum of a rectangle is the sum of all the elements in that rectangle.
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...
108 maximum sum
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
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
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.
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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. Tomasso Toffoli
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
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