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

ahmad_h
New poster
Posts: 5
Joined: Wed Mar 23, 2005 1:27 pm

108 - what happens to a input of zeros

Post by ahmad_h » Fri Sep 29, 2006 3:57 pm

What should be the output to this:
3
0 0 0
0 0 0
0 0 0

Any ideas?

mahan
New poster
Posts: 4
Joined: Fri Sep 22, 2006 10:20 am

Post by mahan » Fri Sep 29, 2006 8:19 pm

it should be 0..

pankaj trivedi
New poster
Posts: 11
Joined: Wed Jun 21, 2006 5:11 pm
Contact:

Post by pankaj trivedi » Tue Oct 03, 2006 9:56 pm

Yeah It is 0
Anything other than Accepted is irritating,even Presentation Error

http://acm.uva.es/problemset/usersjudge.php?user=40301

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

108 faster than O(N^4) but got WA

Post by rickyliu » Tue Oct 24, 2006 9:29 am

I have tried all the test inputs in this board and got the correct answers
but I got WA from the judge. Would anyone please provide more testing
cases or tell me what's wrong in my code:

Code: Select all

* code removed *
Last edited by rickyliu on Fri Nov 10, 2006 9:51 am, edited 1 time in total.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Sat Oct 28, 2006 10:48 am

Try these test cases :)

Code: Select all

4
0  0  0  0
1  1 -4  3
1  2 -5  4
1  3 -6  5

Code: Select all

4
0  1  1  1
0  1  2  3
0 -4 -5 -6
0  3  4  5
Both of thier answers are 12.

Best regards.

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu » Sat Oct 28, 2006 3:19 pm

Thank you for the test cases. I found my bugs. Now, my code shows 12 correctly for these cases. However, I still got WA. I am stuck. Any help, please. Here is my new code:

Code: Select all

* code removed *
Last edited by rickyliu on Fri Nov 10, 2006 9:52 am, edited 1 time in total.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Sun Oct 29, 2006 2:37 am

I think the cause of WA is the little bugs in your code, but I can't analyze because I'm not good at C++.
I'll only give you critical test case. :)

Code: Select all

5
-3 -2 -1  0  1
-2 -1  0  1  2
-1  0  1  2  3
 0  1  2  3 -4
 1  2  3 -4 -5
The answer is 10, but your output is 11.

Best regards.

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu » Sun Oct 29, 2006 11:52 am

Thank you! You are very helpful. I finally got AC. :D

It runs (0.752) only slightly faster than the O(N^4) algorithm (0.891) previously accpeted. My ranking is 3,000+. I am wondering how those people ran so fast.

yoshiro aoki
New poster
Posts: 21
Joined: Sat Oct 21, 2006 11:50 pm
Contact:

Post by yoshiro aoki » Thu Nov 02, 2006 5:23 am

-1, as no larger is possible from the matrix.

maybe coffee will help? :wink:
yoshiro (mark) aoki

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Tue Nov 28, 2006 9:22 am

thnkx for ur algorithm but one thing i did not under how it is ossible to solve this problem in 000 sec .explain me...i m giving my code here plz tell how it can be improved further to get time limit 0 sec....
#include<stdio.h>
#define INFINITY -99999
int sum[110];
void initial()
{
int i;
for(i=0;i<110;i++)
sum[i]=0;
}

int kadan(int* arr,int n)
{
int i,a,b,aa,bb,curr,max;
//scanf("%d",&n);
//for(i=0;i<n;i++)
//scanf("%d",&arr[i]);
max=INFINITY;
a=0;
b=0;
curr=0;
aa=0;
for(bb=0;bb<n;bb++)
{
curr=curr+arr[bb];
if(curr>max)
{
max=curr;
a=aa;
b=bb;
}
if(curr<0)
{
curr=0;
aa=bb+1;
}
}
//printf("max in function call %d\n",max);

return(max);

}
main()
{

int n,i,j,a[110][110],k,v,max;

scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);


for(k=0;k<n;k++)
{
initial();
{
for(i=k;i<n;i++)
{
for(j=0;j<n;j++)
{
sum[j]=sum[j]+a[i][j];
}

v=kadan(sum,n);
if(k==0)
max=v;
else if(v>max)
max=v;
//printf("max in main %d\n",max);
}
}
}

printf("%d\n",max);
}

[b][/b][code][/code][color=red][/color][color=red][/color]

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Nov 28, 2006 11:02 pm

There is only one input, so if you somehow find the output, then just 'printf', or 'cout' would be the solution. If your timing is .02 - .05 sec, then its good.
Ami ekhono shopno dekhi...
HomePage

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

108 help meeeee

Post by rezaee » Mon Dec 11, 2006 4:53 pm

#include <iostream.h>
#include <stdio.h>

int main(void)
{int n,p,sum,max=-127;
int m[100][100];
cin>>n;
{{for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{cin>>p;m[j]=p;}

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
for(int z=0;z<n;z++)

{sum=0;
for(int y=i;y<=j;y++)
for(int x=k;x<=z;x++)
sum+=m[y][x];
if(sum>max)max=sum;}

cout<<max;
}
return 0;}

time limited;what do i?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon Dec 11, 2006 5:10 pm

there are a lot of threads on this problem..
so.. please search..!
and don't make a new thread if one already exists

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

108 help meeeee

Post by rezaee » Tue Dec 19, 2006 11:22 pm

it is my code.

but i get a WA.

#include <iostream.h>

int n;
int b[101][101];

int main()
{
int a[101][101];
int i,j,k;
int max;
int s;
while(cin>>n)
{max=-127;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a[j];
if(a[j]>max)
{
max=a[j];
}
b[j]=b[i-1][j]+b[j-1]-b[i-1][j-1]+a[j];
if(b[j]>max)
{
max=b[j];
}
}
}

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(k<j)
{
temp=b[j]-b[k];
if(s>max) max=s;
}
if(k<i)
{
s=b[i][j]-b[k][j];
if(s>max) max=s;
}
if(k<i && k<j)
{
s=b[i][j]-b[k][j]-b[i][k]+b[k][k];
if(s>max) max=s;
}
}
}
}
cout<<max<<endl;}
return 0;
}

huan086
New poster
Posts: 5
Joined: Tue Dec 19, 2006 5:01 pm

Post by huan086 » Wed Dec 20, 2006 6:18 am

I believe this line is wrong

temp=b[j]-b[k];
if(s>max) max=s;

i think you mean s=b...

Post Reply

Return to “Volume 1 (100-199)”