Page 1 of 7
507 - Jill Rides Again
Posted: Fri Jul 26, 2002 6:28 pm
by Revenger
Why I get WA?
I use a standart DP algorithm ...
[pascal]Program p507;
Var T,N : Integer;
tt,i : Integer;
Max,Sum,j : Integer;
b,e,bm,em : Integer;
begin
Read(T);
for tt:=1 to T do begin
Read(N);
Max:=0;
Sum:=0;
b:=1;
for i:=2 to N do begin
Read(j);
if Sum+j>0 then begin
Sum:=Sum+j;
e:=i;
end else begin
b:=i;
e:=i;
Sum:=0;
end;
if Sum>Max then begin
Max:=Sum;
bm:=b;
em:=e;
end else
if (Sum=Max)and(e-b>em-bm) then begin
bm:=b;
em:=e;
end;
end;
if Max=0 then Writeln('Route ',tt,' has no nice parts') else begin
Write('The nicest part of route ',tt);
Write(' is between stops ');
Writeln(bm,' and ',em);
end;
end;
end.[/pascal]
Posted: Fri Jul 26, 2002 6:33 pm
by Revenger
Sorry for this post.
I misunderstood the problem
507
Posted: Mon Jan 27, 2003 3:09 pm
by ec3_limz
Hi.
I got TLE for this problem. Apparently an O(N^2) algorithm is far too slow. Can anyone suggest a linear-time algorithm? Thanks.
[cpp]#include <stdio.h>
int main() {
int nroute, route[20001], sum[20001], max, start, end;
int cases, tt, i, j;
scanf("%d", &cases);
for (tt = 1; tt <= cases; tt++) {
scanf("%d", &nroute);
nroute--;
for (i = 1; i <= nroute; i++)
scanf("%d", &route);
sum[0] = 0;
for (i = 1; i <= nroute; i++)
sum = sum + route;
max = 0;
for (i = 1; i <= nroute; i++)
for (j = 0; j < i; j++) {
if (sum - sum[j] > max) {
max = sum - sum[j];
start = j + 1, end = i + 1;
}
else if (sum - sum[j] == max && i - j > end - start)
start = j + 1, end = i + 1;
}
if (max == 0)
printf("Route %d has no nice parts\n", tt);
else
printf("The nicest part of route %d is between stops %d and %d\n", tt, start, end);
}
return 0;
}[/cpp]
Posted: Tue Jan 28, 2003 9:08 am
by Dominik Michniewski
Exist simple linear solution for this problem ... think about that
Hint:
When is possible to include negative part of route (means route has negative value) to current route ?
Regards
Dominik
DP linear time
Posted: Fri Jul 16, 2004 4:18 am
by jackie
Traditional DP problem
maximum interval sum
pay attention to the equal cases and the ouput format
To break ties in longest maximal segments, choose the segment that begins with the earliest stop (lowest i). For each route r in the input file, print a line in the form:
WA
Posted: Thu Aug 05, 2004 2:35 pm
by Guest
Hello,
I'm getting WA for this problem and unable to find my mistake.
Can anyone provide me with some sample i/o so that I can check my program a bit deeper?
Please help me find my mistake.
Thank you.
Posted: Wed Aug 18, 2004 5:39 pm
by Raiyan Kamal
Dear Turjo,
I don't know if you are still watching this topic or not. Hope these inputs will help you in case you are still looking for help on this problem.
INPUT:
9
6
1
0
0
0
1
6
1
0
0
1
-1
6
0
0
0
0
0
10
4
-5
4
-3
4
4
-4
4
-5
10
4
-5
4
-3
4
4
-4
4
5
6
-1
1
-1
1
-1
6
1
-1
1
-1
1
11
1
-1
1
-1
1
-1
1
-1
1
-1
12
1
-1
1
-1
1
-1
1
-1
1
-1
1
OUTPUT:
The nicest part of route 1 is between stops 1 and 6
The nicest part of route 2 is between stops 1 and 5
Route 3 has no nice parts
The nicest part of route 4 is between stops 3 and 9
The nicest part of route 5 is between stops 3 and 10
The nicest part of route 6 is between stops 2 and 5
The nicest part of route 7 is between stops 1 and 6
The nicest part of route 8 is between stops 1 and 10
The nicest part of route 9 is between stops 1 and 12
Posted: Wed Aug 18, 2004 7:23 pm
by Guest
Hi Raiyan,
I got AC on this problem some days ago, thanks to NASA bhai.
Anyway, thank you.
Regards,
WA in 507(Jill Rides Again)
Posted: Thu Nov 11, 2004 12:47 pm
by CodeMaker
Hi, my solution is not working, but i m not getting the point. Can anyone give me some hint or critical input to test?
507
Posted: Thu Feb 03, 2005 8:47 pm
by PerHagen
hello
any have I/O ...my code is
#include <stdio.h>
#include <iostream.h>
#include <string.h>
int arreglo[20005];
void main (void)
{int digito,suma,casos,i,l,paradas,final,max;
while(scanf("%d",&casos)==1)
{memset(arreglo,0,sizeof(arreglo)); int nruta=1;
for(l=1;l<=casos;l++){
scanf("%d",¶das);suma=0;
for (i=0;i<paradas-1;i++)
{scanf("%d",&digito);
suma+=digito;
arreglo
=suma;
if (suma<0)suma=0;
}
max=0;final=0;
for(i=0;i<paradas-1;i++)
{if (arreglo>=max)
if (i>final)
{ final=i;max=arreglo;}
}
for (i=final;i>=0;i--)
{
if (arreglo<0)break;
}
if (max!=0)cout<<"The nicest part of route "<< nruta <<" is between stops "<< (i+2)<< " and "<<(final+2);
else cout<<"Route "<<nruta<<" has no nice parts";
cout<<endl;
nruta++;
}
}
}
but is wrong answer
bytes!
507
Posted: Tue Feb 08, 2005 1:03 am
by PerHagen
my code is now ...but is wrong answer ... any I/O please
#include <stdio.h>
#include <iostream.h>
#include <string.h>
int arreglo[20005];
void main (void)
{int digito,suma,casos,i,k,l,paradas,inicio,final,max,tmax,tam;
scanf("%d",&casos)==1;
memset(arreglo,0,sizeof(arreglo)); int nruta=1;
for(l=1;l<=casos;l++){
scanf("%d",¶das);suma=0;
for (i=0;i<paradas-1;i++)
{scanf("%d",&digito);
suma+=digito;
arreglo
=suma;
if (suma<0)suma=0;
}
max=0;final=0;tmax=0;
if(paradas>2){
for(i=0;i<paradas-1;i++)
{tam=0;
if (arreglo>=max)
{for(k=i;k>=0;k--)
{ if(arreglo[k]>=0)tam++;
else break;
}
if (tam>tmax )
{ final=i;inicio=k;max=arreglo;tmax=tam;}
}
}
}
if (paradas==2) {max=arreglo[0];inicio=-1;final=0;}
if (max>0)cout<<"The nicest part of route "<< nruta <<" is between stops "<< (inicio+2)<< " and "<<(final+2);
else cout<<"Route "<<nruta<<" has no nice parts";
cout<<endl;
nruta++;
}
}
507 Jill Rides Again WA WA WA WA
Posted: Wed Feb 09, 2005 4:56 pm
by Eduard
I'm getting crazy with this problem.My DP program is giving right answer to all tests that I find in forum and to all what I can think.Please somebody give some tests,critical if there are.
Thanks.
507
Posted: Thu Feb 10, 2005 7:39 pm
by PerHagen
the 507 my also returns to me crazy... code is
#include <stdio.h>
#include <iostream.h>
#include <string.h>
int arreglo[20005];
void main (void)
{int digito,suma,casos,i,l,paradas,inicio,final,max,tmax,tam;
scanf("%d",&casos)==1;
memset(arreglo,0,sizeof(arreglo)); int nruta=1;
for(l=1;l<=casos;l++){
scanf("%d",¶das);suma=0;
for (i=0;i<paradas-1;i++)
{scanf("%d",&digito);
suma+=digito;
arreglo
=suma;
if (suma<0)suma=0;
}
final=0;max=0;tmax=0;tam=0;
if(paradas>2){
for(i=0;i<paradas-1;i++)
{
if (arreglo>=0) tam++;
else tam=0;
if(arreglo>=max){
if(i==0){
max=arreglo;
final=i;
}
if(i>0 && (tam>tmax || arreglo>max)){
max=arreglo;
final=i;
tmax=tam;
}
}
}
for(i=final;i>=0;i--){if(arreglo>=0) inicio=i;
else break;}
}
if (paradas==2) {max=arreglo[0];inicio=0;final=0;}
if (max>0)cout<<"The nicest part of route "<< nruta <<" is between stops "<< (inicio+1)<< " and "<<(final+2);
else cout<<"Route "<<nruta<<" has no nice parts";
cout<<endl;
nruta++;
}
}
Posted: Sat Feb 12, 2005 11:23 am
by GVahe
Here is a test case
input
1
7
1
-1
1
-100
1
-1
1
output
The nicest part of route 1 is between stops 1 and 4
Posted: Sat Feb 12, 2005 12:31 pm
by Eduard
Hello GVahe.
I think your test must be
And for this test my program gives the same answer.I need more tests.
Eduard