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

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

### Re: 507 - Jill rides again

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

avdtech
New poster
Posts: 3
Joined: Wed Jan 05, 2011 11:15 pm

### Re: 507 - Jill rides again

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

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

### Re: 507 - Jill rides again

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``````
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

### Re: 507 - Jill rides again

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

vpanait
New poster
Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

### Re: 507 - Jill rides again

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.

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 507 - Jill rides again

Getting WA...can someone plzz tell the error or give test case showing my error

Code: Select all

``Code removed after AC``
Last edited by @ce on Mon Jun 25, 2012 10:04 am, edited 2 times in total.
-@ce

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

### Re: 507 - Jill rides again

Input:

Code: Select all

``````1
2
1``````
AC output:

Code: Select all

``The nicest part of route 1 is between stops 1 and 2``
Check input and AC output for thousands of problems on uDebug!

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 507 - Jill rides again

I had intialised si and ei wrong...thanks brianfry...you r a savior...i got AC
Last edited by @ce on Tue Jun 19, 2012 7:45 am, edited 1 time in total.
-@ce

Achilies_Saiful_Buet
New poster
Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm
Location: Dhaka,Bangladesh

### Re: 507 - Jill rides again

WA!!!!!!!!!getting continuous WA...i've checked all the inputs posted in the forum..plz help me out

Code: Select all

``````ACCEPTED
``````
Last edited by Achilies_Saiful_Buet on Tue Jun 19, 2012 1:38 pm, edited 1 time in total.

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

### Re: 507 - Jill rides again

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``
Check input and AC output for thousands of problems on uDebug!

Achilies_Saiful_Buet
New poster
Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm
Location: Dhaka,Bangladesh

### Re: 507 - Jill rides again

Thnx brian guru !!!!!!!!!!!got accepted

ahmed_jolani
New poster
Posts: 1
Joined: Sun Nov 11, 2012 10:47 pm

### Re: 507 - Jill rides again

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

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

### Re: 507 - Jill rides again

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.
Check input and AC output for thousands of problems on uDebug!

unagiroon
New poster
Posts: 1
Joined: Fri Nov 16, 2012 1:23 pm

### Re: 507 - Jill rides again

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

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

### 507 - Jill Rides Again WA

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