507 - Jill Rides Again

[mak(cse_DU)]

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

[shahriar717]

will anyone tell me the algo for this problem??
i am distressed about this........

[mak(cse_DU)]

will anyone tell me the algo for this problem??
i am distressed about this........

Maximum sum of a consecutive sequence.

[bishop]

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]

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]

ACed

[shankhs]

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

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

[shankhs]

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

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.

[sazzadcsedu]

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

[4ndypanda]

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]

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

[ask_1171]

getting correct answer for alla the test case but gettin WA can any one help..

Code: Select all

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

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