## 507 - Jill Rides Again

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 507 - Jill Rides Again WA

Input:

Code: Select all

``````1
11
1
1
1
-100
2
2
-100
1
1
1
``````
AC output:

Code: Select all

``````The nicest part of route 1 is between stops 5 and 7
``````
Check input and AC output for thousands of problems on uDebug!

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

### Re: 507 - Jill rides again

10

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

7
1
-1
1
-100
1
-1
1

AC 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
The nicest part of route 3 is between stops 1 and 6
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
The nicest part of route 10 is between stops 1 and 4

d3nd0h
New poster
Posts: 8
Joined: Sun Nov 03, 2013 3:39 am

### 507 TLE

hi, I am getting TLE within this code for Jill rides again, anyone could help me?

Code: Select all

``````#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<string>
#include<utility>
#include<algorithm>
using namespace std;

int main(){
int tc,stop,nice[20000],maxi,maxj,max;
scanf("%d",&tc);
for(int x=0;x<tc;x++){
nice[0]=0;max=-10000000;
scanf("%d",&stop);
for(int i=1;i<stop;i++){
int dum;
scanf("%d",&dum);
nice[i]=nice[i-1]+dum;
}
for(int i=1;i<stop;i++){
for(int j=i-1;j>=0;j--){
if(max<nice[i]-nice[j] || (max==nice[i]-nice[j]&&maxi-maxj<i-j)){
maxi=i+1;
maxj=j+1;
max=nice[i]-nice[j];
}
}
}
if(max<0)printf("Route %d has no nice parts\n",x+1);
else printf("The nicest part of route %d is between stops %d and %d\n",x+1,maxj,maxi);
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 507 TLE

You can solve each route in O(s) using DP.
Check input and AC output for thousands of problems on uDebug!

d3nd0h
New poster
Posts: 8
Joined: Sun Nov 03, 2013 3:39 am

### Re: 507 TLE

I though that I've used DP, so I am not?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 507 TLE

Your code takes O(s * s) and s can be as large as 20,000.
Check input and AC output for thousands of problems on uDebug!

d3nd0h
New poster
Posts: 8
Joined: Sun Nov 03, 2013 3:39 am

### Re: 507 TLE

Well thanks, I just realized that, I guess I still need more practice for DP, thx:)

Turbat
New poster
Posts: 1
Joined: Fri Mar 14, 2014 11:50 pm

### 507-Jill Rides Again, WA

Can anyone help me to find test case on which following code fails?

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int a[30200],s[30200]={0};

int main(){

int t,r,maxx,minn,maxind,minind1,minind2,i,l=0,nice,k=1;
cin>>t;
while(t--){
scanf("%d", &r);
for(i=1;i<r;i++){
scanf("%d", &a);
s=a+s[i-1];
}
nice=0;
if(s[1]>=s[0]){
minn=s[0];
minind1=minind2=0;
maxind=1;
nice=s[1]-s[0];
l=1;
}
else{
minn=s[1];
minind1=minind2=1;
maxind=1;
}
for(i=2;i<r;i++){
if(s<minn){
minn=s;
minind2=i;
continue;
}
if(s-minn==nice && i-minind2>l){
maxind=i;
l=i-minind2;
minind1=minind2;
continue;
}
if(s-minn>nice ){
nice=s-minn;
maxind=i;
l=i-minind2;
minind1=minind2;
}
}
if(nice<=0) printf("Route %d has no nice parts\n", k);
else printf("The nicest part of route %d is between stops %d and %d\n", k, minind1+1, maxind+1);
k++;
l=0;
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 507-Jill Rides Again, WA

That is AC code.
Check input and AC output for thousands of problems on uDebug!

Titanswords
New poster
Posts: 1
Joined: Thu Mar 20, 2014 4:38 am

### Re: 507-Jill Rides Again, WA

can anyone could help me???
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
/////////
const int MAXN=80010;
int a[MAXN];
int dp[MAXN];//dp???i???????
int m,sum,ans;
int cases;
int main(){
cases=0;
while(scanf("%d",&m)&&m!=0){

while(m--){
cases++;
int n;
cin>>n;
for(int i=0;i<n-1;i++){
scanf("%d",&a);//????
}
ans=0;
int min[MAXN],max[MAXN];
memset(min,0,sizeof(min));
memset(max,0,sizeof(max));
dp[0]=a[0];
max[0]=2;
min[0]=1;
int minn;
for(int i=1;i<n-1;i++){//????dp??
max=i+2;
if(dp[i-1]>0){
dp=dp[i-1]+a;
}
else{
dp=a;
minn=i+1;
}
min=minn;
}
int large=dp[0];
int temp;
for(int i=1;i<n-1;i++){
if(dp>=dp[i-1]){
large=dp;
temp=i;
}
}
//cout<<temp;
if(large<0){
printf("Route %d has no nice parts\n",cases);
}
else{
//cout<<large<<endl;
printf("The nicest part of route %d is between stops %d and %d\n",cases,min[temp],max[temp]);
}
}
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 507-Jill Rides Again, WA

The first line of the file is a single integer b representing the number of route descriptions in the file.
You should only read b once.
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### 507 - Jill Rides Again Run Time Error

I am getting run time error for this problem . Plz help. Here is my code

Code: Select all

``````#include<cstdio>
using namespace std;
void find_sum(int n,long long int arr[],int c)
{
int i,j,k,len,a,b;
long long int sum[n+1][n+1],maxlen;
maxlen=-1;
for(i=1;i<n;i++)
{
sum[i][i+1]=arr[i];
if(arr[i]>maxlen)
{
maxlen=arr[i];
a=i;
b=i+1;
}
// printf("%d %d %d\n",i,i+1,sum[i][i+1]);
}
for(len=2;len<n;len++)
{
for(i=1;i<n-len+1;i++)
{
j=i+len;
k=len/2;
sum[i][j]=sum[i][j-k]+sum[j-k][j];
//printf("%d %d %d\n",i,j,sum[i][j]);
if(sum[i][j]>maxlen)
{
maxlen=sum[i][j];
a=i;
b=j;
}
else if(sum[i][j]==maxlen)
{
if((b-a)<(j-i))
{
b=j;
a=i;
}
}
}
}
if(maxlen>=0)
printf("The nicest part of route %d is between stops %d and %d\n",c,a,b);
else
printf("Route %d has no nice parts\n",c);
}
int main()
{
int r,s,i,j;
long long arr[21000];
scanf("%d",&r);
for(i=1;i<=r;i++)
{
scanf("%d",&s);
for(j=1;j<s;j++)
scanf("%d",&arr[j]);
find_sum(s,arr,i);
}
return 0;
}
``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 507 - Jill Rides Again

Yes judge gives RE for your code, but it doesn't match sample I/O so try to fix bugs first.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 507 - Jill Rides Again

I have tried the output for all the sample input i could get and it is giving me the reqired output. If not , plz give me the input for which the output is wrong

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 507 - Jill Rides Again

Your code posted above doesn't match sample I/O. http://ideone.com/FZxOoP
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman