Page 5 of 7

Re: 507 - Jill rides again

Posted: Sun Dec 26, 2010 10:52 am
by sir. manuel
I need help,,,my problem is that i don't know how to carry the index!!!
In the case:
4
1
-1
1


my program return "from 3 to 4 "...and the solution is "from 1 to 4"...my problem is "If more than one segment is maximally nice, choose the one with the longest cycle ride (largest j-i)."

Code: Select all

#include<stdio.h>
#include<math.h>
using namespace std;
int main()
{
int n,casos,i; scanf("%d",&casos); int test=1; 
while(casos--){  
  scanf("%d",&n);   int suma=0,dp=-20001,var,ini,fin,inif,finf; ini=fin=0; inif=finf=-1;
   for(i=0;i<n-1;i++){
        scanf("%d",&var);
     if(suma>0){ suma+=var; fin=i; }
     else{ suma=var; ini=i; }
     if(suma==dp){ if( fabs(fin-ini)>(finf-inif) ){ inif=ini;  finf=i;  }  
                        }
     if(suma>dp){  dp=suma;  
                    inif=ini;  
                    finf=i;  
     }
}
     if(dp<0) printf("Route %d has no nice parts\n",test);
        else
         printf("The nicest part of route %d is between stops %d and %d\n",test,inif+1,finf+2);
        test++;
    }
return 0;
}

Re: 507 - Jill rides again

Posted: Wed Jan 05, 2011 11:44 pm
by avdtech
what should be the output for this?

Code: Select all

2

7
1
2
3
-34
3
3

7
3
3
-34
1
2
3
The problem says -
If more than one segment is maximally nice, choose the one with the longest cycle ride (largest j-i).
according to that, shouldn't be the output be
The nicest part of route 1 is between stops 1 and 4
The nicest part of route 2 is between stops 4 and 7
instead of
The nicest part of route 1 is between stops 1 and 4
The nicest part of route 2 is between stops 1 and 3

Re: 507 - Jill rides again

Posted: Sat Jan 08, 2011 9:33 pm
by sazzadcsedu
Your ans is right.
Correct output-

Code: Select all

The nicest part of route 1 is between stops 1 and 4
The nicest part of route 2 is between stops 4 and 7

Re: 507 - Jill rides again

Posted: Fri Apr 29, 2011 10:00 am
by valkov
Hi all,
just got AC on this problem.
For those of you who are wondering about solution to this problem, search for the Kadane's Algorithm which solves this problem in O(n) time. Some modifications are needed since the problem have some specific constraints about route length and order. These all can be handled within

Code: Select all

currentMaxSum == maxSum

case :)
Use the IO provided within this thread :)
Have fun

Re: 507 - Jill rides again

Posted: Sat Apr 21, 2012 6:59 pm
by vpanait
I got accepted, there are 2 tricky parts:
1. read carefully the statement "If more than one segment is maximally nice, choose the one with the longest cycle ride (largest j-i)."
2. pay attention that http://www.uvatoolkit.com wrongly solves the cases suggested by "avdtech", so you can compare most of your solutions to the reference, however not those involving statement (1).

This should save you some debugging time.
Have fun.

Re: 507 - Jill rides again

Posted: Thu Jun 14, 2012 11:02 pm
by @ce
Getting WA...can someone plzz tell the error or give test case showing my error

Code: Select all

Code removed after AC

Re: 507 - Jill rides again

Posted: Fri Jun 15, 2012 11:03 pm
by brianfry713
Input:

Code: Select all

1
2
1
AC output:

Code: Select all

The nicest part of route 1 is between stops 1 and 2

Re: 507 - Jill rides again

Posted: Sat Jun 16, 2012 8:56 am
by @ce
I had intialised si and ei wrong...thanks brianfry...you r a savior...i got AC :)

Re: 507 - Jill rides again

Posted: Sun Jun 17, 2012 10:48 pm
by Achilies_Saiful_Buet
WA!!!!!!!!!getting continuous WA...i've checked all the inputs posted in the forum..plz help me out

Code: Select all

ACCEPTED

Re: 507 - Jill rides again

Posted: Tue Jun 19, 2012 1:51 am
by brianfry713
Input:

Code: Select all

1
10
1
1
1
1
-100
4
-100
2
2
AC Output:

Code: Select all

The nicest part of route 1 is between stops 1 and 5

Re: 507 - Jill rides again

Posted: Tue Jun 19, 2012 1:37 pm
by Achilies_Saiful_Buet
Thnx brian guru !!!!!!!!!!!got accepted :D

Re: 507 - Jill rides again

Posted: Sun Nov 11, 2012 10:50 pm
by ahmed_jolani
My code passes every test case that was posted here and the sample i/o but I keep getting WA, please advise! :(

Code: Select all

#include <iostream>
#include <string>
#include <string.h>
#include <sstream>
#include <fstream>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdlib.h>
#include <stdio.h>
#define oo 1e9
#define EPS 1e-9
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

long long stops[20012], cpy[20012], start[20012];

int main()
{
	//freopen("transform.txt", "r", stdin);
	//freopen("t1.txt", "w", stdout);
	long long T, s, routes=0;
	cin >> T;
	while (T--)
	{
		cin >> s;
		long long mi, mj, m, tm, subMax, var=2;
		tm = mj = mi = 0;
		m = -oo;
		stops[0] = stops[1] = 0;
		for (int i=2; i<=s; ++i)
		{
			cin >> stops[i];
			cpy[i] = stops[i];
			stops[i] += stops[i-1];
			if (cpy[i] > 0 && stops[i] < 0)
			{
				stops[i-1] = 0;
				var = i;
				stops[i] = cpy[i];
			}
			start[i] = var;
			if (stops[i] > tm) tm = stops[i];
		}
		for (int i=2; i<=s; ++i)
		{
			if (stops[i] != tm) continue;
			for (int j=start[i]; j<=i; ++j)
			{
				subMax = stops[i] - stops[j-1];
				if (subMax > m)
				{
					m = subMax;
					mj = i;
					mi = j - 1;
				}
				else if (subMax == m && ((i-j+1 > mj-mi)))
				{
					mj = i;
					mi = j - 1;
				}
			}
		}
		subMax = 0;
		for (int i=mj+1; i<=s; ++i)
		{
			subMax += cpy[i];
			if (subMax+m > m)
			{
				mj = i;
				m += subMax;
				subMax = 0;
			}
		}
		if (s==2 && stops[2]>0) cout << "The nicest part of route " << ++routes << " is between stops 1 and 2";
		else if (m>0) cout << "The nicest part of route " << ++routes << " is between stops " << mi << " and " << mj;
		else cout << "Route " << ++routes << " has no nice parts";
		cout << endl;
	}
	return 0;
}

Re: 507 - Jill rides again

Posted: Tue Nov 13, 2012 2:56 am
by brianfry713
You can solve this in linear time. Keep a cumulative sum for each stop. Initialize a max variable and a start pointer to 0. At each stop, check if the current sum minus the sum at the start pointer is greater than the max or equal to the max with a longer ride. If the current sum minus the sum at the start pointer is less than zero then update the start pointer to one more than the current position.

Re: 507 - Jill rides again

Posted: Fri Nov 16, 2012 1:26 pm
by unagiroon
First, I thought this problem is simple. It turns out that tie-breaking part can be tricky.
Try this test cases:

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

507 - Jill Rides Again WA

Posted: Sat Sep 28, 2013 5:58 am
by hpjhc
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

int divide(int, int);
int state[20001], start, end, max;
int main(void)
{
int t, n, i, m;
scanf("%d", &t);
m = 0;
while(t--)
{
scanf("%d", &n);
for(i = 1; i < n; i++)
{
scanf("%d", &state);
}
max = -1;
divide(1, n);
if(max < 0)
printf("Route %d has no nice parts\n", ++m);
else
printf("The nicest part of route %d is between stops %d and %d\n", ++m, start, end+1);
}
return 0;
}

int divide(int x, int y)
{
int l, r, left, right, m;
int i, L, R, v, Max;
if(y-x == 1)
{
if(state[x] > max)
{
max = state[x];
start = end = x;
}
return state[x];
}
m = x+(y-x)/2;
left = divide(x, m);
right = divide(m, y);
Max = left > right ? left : right;
L = state[m-1];
l = m-1;
for(i = m-2, v = L; i >= x; i--)
{
v += state;
if(v >= L)
{
L = v;
l = i;
}
}
R = state[m];
r = m;
for(i = m+1, v = R; i < y; i++)
{
v += state;
if(v >= R)
{
R = v;
r = i;
}
}
if(L+R >= Max)
{
Max = L+R;
if(r-l > end-start)
{
start = l;
end = r;
}
}
if(Max > max)
max = Max;
return Max;
}