## 507 - Jill rides again

Moderator: Board moderators

### 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;}`
sir. manuel
New poster

Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

### Re: 507 - Jill rides again

what should be the output for this?

Code: Select all
`27123-3433733-34123`

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

The nicest part of route 1 is between stops 1 and 4
The nicest part of route 2 is between stops 1 and 3
avdtech
New poster

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

### Re: 507 - Jill rides again

Correct output-

Code: Select all
`The nicest part of route 1 is between stops 1 and 4The nicest part of route 2 is between stops 4 and 7`
Experienced poster

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

### 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
valkov
New poster

Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

### 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.
vpanait
New poster

Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

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

@ce
Learning poster

Posts: 57
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 507 - Jill rides again

Input:
Code: Select all
`121`

AC output:
Code: Select all
`The nicest part of route 1 is between stops 1 and 2`
brianfry713
Guru

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

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

@ce
Learning poster

Posts: 57
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### 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.
Achilies_Saiful_Buet
New poster

Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm

### Re: 507 - Jill rides again

Input:
Code: Select all
`1101111-1004-10022`

AC Output:
Code: Select all
`The nicest part of route 1 is between stops 1 and 5`
brianfry713
Guru

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

### Re: 507 - Jill rides again

Thnx brian guru !!!!!!!!!!!got accepted
Achilies_Saiful_Buet
New poster

Posts: 16
Joined: Wed Mar 28, 2012 7:24 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-9using 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;}`
ahmed_jolani
New poster

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

### 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.
brianfry713
Guru

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

### 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
unagiroon
New poster

Posts: 1
Joined: Fri Nov 16, 2012 1:23 pm

Previous