507 - Jill Rides Again

[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]

[Revenger]

Sorry for this post.
I misunderstood the problem

[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]

[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

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

[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.

[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

[Guest]

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

Anyway, thank you.

Regards,

[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?

Code: Select all

Accepted Now

[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",&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!

[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",&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++;
}
}

Code: Select all

[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.

[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",&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++;
}
}

Code: Select all

[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

[Eduard]

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