## 507 - Jill Rides Again

Moderator: Board moderators

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

### 507 - Jill Rides Again

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
for tt:=1 to T do begin
Max:=0;
Sum:=0;
b:=1;
for i:=2 to N do begin
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
Sorry for this post.
I misunderstood the problem ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### 507

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, sum, 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;
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:
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

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
Contact:

### WA

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?
Thank you.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
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
Contact:
Hi Raiyan,
I got AC on this problem some days ago, thanks to NASA bhai. Anyway, thank you. Regards,

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm

### WA in 507(Jill Rides Again)

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

hello
any have I/O ...my code is

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

int arreglo;

void main (void)

while(scanf("%d",&casos)==1)
{memset(arreglo,0,sizeof(arreglo)); int nruta=1;
for(l=1;l<=casos;l++){
{scanf("%d",&digito);
suma+=digito;
arreglo=suma;
if (suma<0)suma=0;
}
max=0;final=0;
{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++;
}
}
}

bytes!
hello !

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

### 507

my code is now ...but is wrong answer ... any I/O please
#include <stdio.h>
#include <iostream.h>
#include <string.h>

int arreglo;

void main (void)

scanf("%d",&casos)==1;
memset(arreglo,0,sizeof(arreglo)); int nruta=1;
for(l=1;l<=casos;l++){
{scanf("%d",&digito);
suma+=digito;
arreglo=suma;
if (suma<0)suma=0;
}
max=0;final=0;tmax=0;
{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 (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

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

the 507 my also returns to me crazy... code is

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

int arreglo;

void main (void)

scanf("%d",&casos)==1;
memset(arreglo,0,sizeof(arreglo)); int nruta=1;
for(l=1;l<=casos;l++){
{scanf("%d",&digito);
suma+=digito;
arreglo=suma;
if (suma<0)suma=0;
}
final=0;max=0;tmax=0;tam=0;
{
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 (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 !

GVahe
New poster
Posts: 17
Joined: Thu Aug 05, 2004 6:04 pm
Location: Armenia
Contact:
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
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