Page 3 of 16
prob 108 - WA
Posted: Fri Sep 27, 2002 8:15 pm
by new_tim
I always got the wrong answer...
why??
[c]
#include <stdio.h>
void main()
{
int size;
int sum;
int max;
int A[101][101];
int B[101][101];
while(scanf("%d\n", &size) == 1)
{
sum = 0;
for(int i = 0; i <= 100; i++)
{
for(int j = 0; j <= 100; j++)
{
A[j] = 0;
B[j] = 0;
}
}
if(size == 0)
max = 0;
else {
for(int m = 1; m <= size; m++)
{
for(int n = 1; n <= size; n++)
{
scanf("%d", &A[m][n]);
if(m == 1 && n == 1)
max = A[m][n];
// set the initial max to the first number in the array
else if(max < A[m][n])
max = A[m][n];
// otherwise, check if each number in 1X1 square
}
}
for(int t1 = 1; t1 <= size; t1++)
{
for(int t2 = 1; t2 <= size; t2++)
{
for(int t3 = 1; t3 <= t1; t3++)
{
for(int t4 = 1; t4 <= t2; t4++)
{
B[t1][t2] = B[t1][t2]+A[t3][t4];
}
}
}
}
for(int a1 = 1; a1 <= size; a1++)
{
for(int a2 = 1; a2 <= size; a2++)
{
for(int a3 = a1; a3 <= size; a3++)
{
for(int a4 = a2; a4 <= size; a4++)
{
sum = B[a3][a4] - B[a3][a2-1] - B[a1-1][a4] + B[a1-1][a2-1];
if(max < sum)
max = sum;
}
}
}
}
printf("%d\n", max);
}
}
}
[/c]
108 -- algorithm faster than O(N^3)???
Posted: Thu Oct 24, 2002 9:29 am
by Ilham Kurnia
Hi,
I'm wondering is there any algorithm faster than O(N^3) to solve 108??
I've heard rumours that O(N^2) exists, but I can't confirm it.
Cheers,
Ilham
Posted: Thu Oct 24, 2002 11:18 am
by Dominik Michniewski
I don't think , that exists algorithm which solve this question in O(N^2) time ... this is opinion my and people from my university ...
but maybe we missed something
Cheers
Dominik
Posted: Thu Oct 24, 2002 11:18 am
by Dominik Michniewski
I don't think , that exists algorithm which solve this question in O(N^2) time ... this is opinion my and people from my university ...
but maybe we missed something
Cheers
Dominik
108 - multiple input???
Posted: Wed Nov 13, 2002 4:55 pm
by mag
Is there multiple input in 108?
I've seen some solutions on this board using multiple input and some solutions that doesn't use multiple input....
108 Compile Error
Posted: Thu Nov 14, 2002 12:06 pm
by eric30
Hello,
I'm so confused with that I have got so many times "Compile Error".
I hope that someone could help me find where's my problem.
Followings are my Error Message(problem 108):
/usr/lib/crt1.o: In function `_start':
/usr/lib/crt1.o(.text+0x18): undefined reference to `main'
collect2: ld returned 1 exit status
Posted: Wed Nov 27, 2002 3:00 pm
by Balon
The input consists of an NxN array of integers
so, there is only one case in one input, not multiple.
108. Presentation Error
Posted: Tue Dec 03, 2002 5:28 am
by Boffin
Hello, All.
I posted problem 108 and it was accepted.
But I got a letter with:
"Warning: Your program would get a Presentation Error in a true contest.
The 24-hours judge interpretes it as an "Accepted" problem."
I print my answer:
[c]printf("%d",maxSum);[/c]
What's wrong?
Should I print
[c]printf("%d\n",maxSum);[/c]
and why?
What "Presentation Error" means?
P 108 - Time Limit Exceeded
Posted: Thu Dec 05, 2002 11:35 pm
by passwd
hi,
I'm getting Time Limit Exceeded, and I don't know why ...
If someone knows, please, advice !
Code: Select all
[c]
#include <stdio.h>
/*#define DEBUG*/
int main() {
int n;
int i,j;
scanf("%d", &n);
{
int v[n][n];
int k=0,m=0,maxsum=-1,aux=0,p,q;
if(n==0) { printf("0\n"); exit(0); };
for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&v[i][j]);
if(n==1) {
printf("%d\n",v[0][0]);
return 0;
}
#ifdef DEBUG
printf("\n");
for(i=0;i<n;i++) {
for(j=0;j<n;j++) printf("%d ",v[i][j]);
printf("\n");
}
printf("\n");
#endif
for(i=0;i<n-1;i++) {
for(j=i+1;j<n;j++) {
for(k=0;k<n-1;k++) {
for(m=k+1;m<n;m++) {
/*calcula a soma do retangulo*/
for(p=i;p<=j;p++) {
for(q=k;q<=m;q++) aux+=v[p][q];
}
if(aux>maxsum) maxsum=aux;
aux=0;
}
}
}
}
printf("%d\n",maxsum);
}
return 0;
}
[/c]
thanks !!
Posted: Fri Dec 06, 2002 12:45 am
by Larry
Use Dynamic Programming
Posted: Fri Dec 06, 2002 10:01 am
by nghiank
test
Posted: Fri Dec 06, 2002 11:22 am
by JTK1996
Hi,
The innermost for-loop is run 10^6 times, I think that is too much. Dynamic Programming, as mentioned before, sounds like a good
way to reduce time consumption.
Posted: Fri Dec 06, 2002 12:06 pm
by junjieliang
If you know how to solve the 1-d problem in O(n) time, without DP you can get O(n^4) algorithm, which (although not the best) will pass the time limit.
Posted: Wed Dec 18, 2002 4:55 pm
by peterlin
Excuse me,
May I ask what's the algo is O(n^3) for this problem ?
Best wishes,
Peter
Posted: Wed Dec 18, 2002 4:58 pm
by peterlin
Excuse me,
May I ask what's the algo is O(n^3) for this problem ?
Best wishes,
Peter