## 507 - Jill Rides Again

Moderator: Board moderators

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 507 - Jill rides again

Try this case also:
Input:::

Code: Select all

``````
1
5
3
-3
4
1``````
output:::

Code: Select all

``The nicest part of route 1 is between stops 1 and 5``
Mak
Help me PLZ!!

shahriar717
New poster
Posts: 1
Joined: Tue Dec 16, 2008 8:14 am

### Re: 507 - Jill rides again

will anyone tell me the algo for this problem??
i am distressed about this........ mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 507 - Jill rides again

shahriar717 wrote:will anyone tell me the algo for this problem??
i am distressed about this........ Maximum sum of a consecutive sequence.
Mak
Help me PLZ!!

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

### Re: 507 - Jill rides again

my code shows everything right
but judge shows me WA

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<stdlib.h>
using namespace std;
#define S 99999
struct lar
{
int lar;
int a,b;
}st;
int main()
{
int num[S], sum[S];
int i,j,k;
int n;
int t;
cin >> t;
for(k=1; k<=t; k++)
{
cin >> n;
if(n==0)
{cout <<"Route "<<k<<" has no nice parts\n";continue;}

n--;
int m;
for(i=0; i<n; i++)
cin >>  num[i];

m=sum=num;
int x,y;
int largest=0;
int l=0;
x=y=0;
for(i=1; i<n; i++)
{
sum[i]=num[i]+sum[i-1];

if(sum[i]<num[i])
{
st[l].lar=y-x;
st[l].a=x;
st[l].b=y; l++;
x=y=i;
sum[i]=max(sum[i],num[i]);
}
if(sum[i]>=m)
{
y=i;
}

m=max(m,sum[i]);
}
for(i=0; i<l; i++)
{
if(st[i].lar>largest)
{
x=st[i].a;
y=st[i].b;
}
}

if(m>0)
cout << "The nicest part of route "<<k<<" is between stops "<< x+1 <<" and " <<y+1+1 <<endl;
else
cout <<"Route "<<k<<" has no nice parts\n";

}
return 0;
}

``````
WHY........................

New poster
Posts: 2
Joined: Tue Feb 10, 2009 8:34 pm

### 507

can any1 tell me the prob with this code...i m getting wrong answer..its working for the test cases . given below..in the forum . u can check . it ..if u wanna check

#include<iostream>
#define max(a,b) a>b?a:b
long long int arr,sum;
using namespace std;
int main()
{
long long int temp,i,j,t,n,max,test,k,s;
cin>>test;
for(j=0;j<test;j++)
{
k=0;
cin>>n;
s=0;
for(i=0;i<n-1;i++) cin>>arr;
max=sum=arr;
for(i=1;i<n-1;i++) sum=max(arr,arr+sum[i-1]);
for(i=0;i<n-1;i++)
if(sum>=max)
{
max=sum;
t=i;
}
for(i=0;i<=t;i++) s+=arr;
if(s==max) k=0;
else k=1;
for(i=t;i>=k;i--) if(sum==arr) temp=i;
if(max<=0) cout<<"Route "<<j+1<<" has no nice parts";
else cout<<"The nicest part of route "<<j+1<<" is between stops "<<temp+1<<" and "<<t+2;
if(j!=(test-1)) cout<<"\n";
}
return 0;
}

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

### Re: 507 - Jill rides again

ACed

shankhs
New poster
Posts: 3
Joined: Tue May 20, 2008 4:10 am

### Re: 507 - Jill rides again

The problem is making me crazy.The following code passes all the test cases given in this thread but still the OJ is giving WA!

Code: Select all

``````#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>

using namespace std;
struct route
{
int start;
int last;
};
int main()
{
int n;
scanf("%d",&n);
int m,l;

int sum=0;
int max_sum=0;
for(int loop=1;loop<=n;loop++)
{
struct route temp;
scanf("%d",&m);
temp.start=m-2;
max_sum=0;
sum=0;

int a[m-1];

for(int i=0;i<m-1;i++)
scanf("%d",&a[i]);
for(int i=m-2;i>=0;i--)
{
//scanf("%d",&l);
l=a[i];
sum+=l;
if(sum<0)
{
sum=0;
temp.start=i-1;
}
else if(sum>=0&&max_sum<=sum)
{
max_sum=sum;
//printf("ksdj");
temp.last=i;
//cout<<sum<<" "<<max_sum<<" "<<temp.start<<" "<<temp.last<<endl;
}
//cout<<sum<<" "<<max_sum<<" "<<temp.start<<" "<<temp.last<<endl;
}
if(max_sum==0)
{
//cout<<max_sum<<endl;
cout<<"Route "<<loop<<" has no nice parts"<<endl;
}
else
{
cout<<"The nicest part of route "<<loop<<" is between stops "<<temp.last+1<<" and "<<temp.start+2<<endl;
}
}
return 0;
}
``````

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 507 - Jill rides again

shankhs wrote:Help
check the below input:

Code: Select all

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

Code: Select all

``    The nicest part of route 1 is between stops 5 and 7``
Your's giving:

Code: Select all

``    The nicest part of route 1 is between stops 5 and 4``
Mak
Help me PLZ!!

shankhs
New poster
Posts: 3
Joined: Tue May 20, 2008 4:10 am

### Re: 507 - Jill rides again

Thanx Mak
I got AC in 0.124 secs but I see many people getting AC in 0.000 sec!
What optimization could be done here?

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 507 - Jill rides again

shankhs wrote:Thanx Mak
I got AC in 0.124 secs but I see many people getting AC in 0.000 sec!
What optimization could be done here?

No Need to optimize it farther. You time is Ok enough.
If you still interested then:

2. reduce branch instruction if possible.
3. Reduce extra memory allocation and computation.
Mak
Help me PLZ!!

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### 507 - Jill rides again

Can someone post me some I/O of this problem?? My program passed all the test case from the previous post. But still
WA. Plz someone help. Is int data type is enough for this problem???
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

4ndypanda
New poster
Posts: 2
Joined: Wed May 26, 2010 4:25 am

### Re: 507 - Jill rides again

sazzadcsedu wrote:Can someone post me some I/O of this problem?? My program passed all the test case from the previous post. But still
WA. Plz someone help. Is int data type is enough for this problem???
It definitely fits in an int.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: 507 - Jill rides again

Same problem like 10684

I was failed for a chili mistake like

if(n==2)
if(d<0)
printf "NO route"
else printf "root between 1 and 2"

but i wrote if(d>0) for above cases..

Critical input:

3

2
-2

2
2

10
1
2
5
3
-13
6
4
3
-2

Output:
Route 1 has no nice parts
The nicest part of route 2 is between stops 1 and 2
The nicest part of route 3 is between stops 6 and 9
Try to catch fish rather than asking for some fishes.

New poster
Posts: 3
Joined: Wed Aug 04, 2010 1:17 pm

### Re: 507 - Jill rides again

getting correct answer for alla the test case but gettin WA can any one help.. #include<iostream>
using namespace std;

#define LL long long int

LL arr;

int main()
{
LL t,i,j,k,s,f,m,n;
LL maxsum,suffixmax;
freopen("1.txt","r",stdin);
cin>>t;

for(k=1;k<=t;k++)
{
scanf("%lld",&n);

for(j=1;j<n;j++)
scanf("%lld",&arr[j]);

maxsum=-1;
suffixmax=0;
s=0;
m=0;
for(i=1;i<n;i++)
{
if(arr+suffixmax>=maxsum )
{
maxsum=arr+suffixmax;
suffixmax=maxsum;

if(arr+suffixmax==maxsum)
{ if(f-s<i-m)
{
s=m;
f=i;
}
else
continue;
}
else
{
s=m;
f=i;
}

}

else if(suffixmax+arr>=0)
suffixmax=suffixmax+arr;

else
{
suffixmax=0;
m=i;
}

}

if(maxsum==-1)
printf("Route %lld has no nice parts\n",k);
else
printf("The nicest part of route %lld is between stops %lld and %lld\n",k,s+1,f+1);
}
return 0;
}

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 507 - Jill rides again

Try this-

Code: Select all

``````1
7
1
2
3
-34
3
3
``````