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

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

Re: 507 - Jill Rides Again WA

Post by brianfry713 » Tue Oct 01, 2013 10:52 pm

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

Post by moxlotus » Tue Oct 22, 2013 3:22 pm

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

Post by d3nd0h » Thu Nov 21, 2013 5:30 am

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

Post by brianfry713 » Fri Nov 22, 2013 12:22 am

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

Post by d3nd0h » Sat Nov 23, 2013 3:04 pm

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

Post by brianfry713 » Tue Nov 26, 2013 12:36 am

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

Post by d3nd0h » Tue Nov 26, 2013 5:08 am

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

Post by Turbat » Fri Mar 14, 2014 11:56 pm

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

Post by brianfry713 » Tue Mar 18, 2014 12:37 am

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

Post by Titanswords » Thu Mar 20, 2014 4:42 am

can anyone could help me??? :cry:
#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

Post by brianfry713 » Thu Mar 20, 2014 8:21 pm

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

Post by richatibrewal » Fri Jan 02, 2015 1:37 pm

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

Post by lighted » Fri Jan 02, 2015 6:48 pm

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

Post by richatibrewal » Sat Jan 03, 2015 8:41 pm

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

Post by lighted » Mon Jan 05, 2015 9:29 am

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

Post Reply

Return to “Volume 5 (500-599)”