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

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

Re: 507 - Jill rides again

Post by mak(cse_DU) » Tue Oct 14, 2008 1:42 pm

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

Post by shahriar717 » Tue Dec 16, 2008 8:28 am

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
Location: bangladesh

Re: 507 - Jill rides again

Post by mak(cse_DU) » Tue Dec 16, 2008 10:37 am

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

Post by bishop » Sun Dec 28, 2008 8:44 pm

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[99999];
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[0]=num[0];
		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........................

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

507

Post by aadarsh1093 » Sun Feb 15, 2009 12:27 am

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[20001],sum[20001];
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[0]=arr[0];
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

Post by qwerty » Sun Oct 25, 2009 1:29 pm

ACed

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

Re: 507 - Jill rides again

Post by shankhs » Thu Dec 24, 2009 3:37 pm

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;
}
Please help me to identify the wrong part.Thanx.

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

Re: 507 - Jill rides again

Post by mak(cse_DU) » Thu Dec 24, 2009 7:16 pm

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

Post by shankhs » Fri Jan 01, 2010 4:21 pm

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
Location: bangladesh

Re: 507 - Jill rides again

Post by mak(cse_DU) » Fri Jan 01, 2010 6:07 pm

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:

1. scanf() instead of cin and printf instead of cout.
2. reduce branch instruction if possible.
3. Reduce extra memory allocation and computation.
Mak
Help me PLZ!!

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

507 - Jill rides again

Post by sazzadcsedu » Tue May 04, 2010 8:54 pm

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
For Hints: http://salimsazzad.wordpress.com

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

Re: 507 - Jill rides again

Post by 4ndypanda » Wed May 26, 2010 4:32 am

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

Post by arifcsecu » Tue Aug 31, 2010 11:51 pm

Same problem like 10684

I was failed for a chili mistake like

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

but i wrote if(d[1]>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.

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

Re: 507 - Jill rides again

Post by ask_1171 » Sun Nov 21, 2010 10:35 pm

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

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;
}

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 507 - Jill rides again

Post by sazzadcsedu » Wed Dec 22, 2010 4:12 pm

Try this-

Code: Select all

1
7
1
2
3
-34
3
3
your code output-
The nicest part of route 1 is between stops 5 and 7

Answer-
The nicest part of route 1 is between stops 1 and 4
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Post Reply

Return to “Volume 5 (500-599)”