507 - Jill Rides Again

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

Moderator: Board moderators

Post Reply
Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

507 - Jill Rides Again

Post by Revenger » Fri Jul 26, 2002 6:28 pm

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]

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Fri Jul 26, 2002 6:33 pm

Sorry for this post.
I misunderstood the problem :oops:

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

507

Post by ec3_limz » Mon Jan 27, 2003 3:09 pm

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]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Jan 28, 2003 9:08 am

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

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

DP linear time

Post by jackie » Fri Jul 16, 2004 4:18 am

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:

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

WA

Post by Guest » Thu Aug 05, 2004 2:35 pm

Hello,
I'm getting WA for this problem and unable to find my mistake. :cry:
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.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Wed Aug 18, 2004 5:39 pm

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

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by Guest » Wed Aug 18, 2004 7:23 pm

Hi Raiyan,
I got AC on this problem some days ago, thanks to NASA bhai. :D

Anyway, thank you. :D

Regards,

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

WA in 507(Jill Rides Again)

Post by CodeMaker » Thu Nov 11, 2004 12:47 pm

Hi, my solution is not working, but i m not getting the point. Can anyone give me some hint or critical input to test?

Code: Select all

Accepted Now
Jalal : AIUB SPARKS

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

507

Post by PerHagen » Thu Feb 03, 2005 8:47 pm

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",&paradas);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!
hello !

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

507

Post by PerHagen » Tue Feb 08, 2005 1:03 am

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",&paradas);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++;
}
}
hello !

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

507 Jill Rides Again WA WA WA WA

Post by Eduard » Wed Feb 09, 2005 4:56 pm

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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

507

Post by PerHagen » Thu Feb 10, 2005 7:39 pm

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",&paradas);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++;
}
}
hello !

User avatar
GVahe
New poster
Posts: 17
Joined: Thu Aug 05, 2004 6:04 pm
Location: Armenia
Contact:

Post by GVahe » Sat Feb 12, 2005 11:23 am

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
Last edited by GVahe on Mon Feb 14, 2005 7:24 pm, edited 3 times in total.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sat Feb 12, 2005 12:31 pm

Hello GVahe.
I think your test must be

Code: Select all

1 
7 
1 
-1 
1 
-100 
1 
-1
And for this test my program gives the same answer.I need more tests.
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Post Reply

Return to “Volume 5 (500-599)”