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

Post by sir. manuel » Sun Dec 26, 2010 10:52 am

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

Post by avdtech » Wed Jan 05, 2011 11:44 pm

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

Post by sazzadcsedu » Sat Jan 08, 2011 9:33 pm

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

Post by valkov » Fri Apr 29, 2011 10:00 am

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

Post by vpanait » Sat Apr 21, 2012 6:59 pm

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.

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

Re: 507 - Jill rides again

Post by @ce » Thu Jun 14, 2012 11:02 pm

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

Post by brianfry713 » Fri Jun 15, 2012 11:03 pm

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!

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

Re: 507 - Jill rides again

Post by @ce » Sat Jun 16, 2012 8:56 am

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

Post by Achilies_Saiful_Buet » Sun Jun 17, 2012 10:48 pm

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

Post by brianfry713 » Tue Jun 19, 2012 1:51 am

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

Post by Achilies_Saiful_Buet » Tue Jun 19, 2012 1:37 pm

Thnx brian guru !!!!!!!!!!!got accepted :D

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

Re: 507 - Jill rides again

Post by ahmed_jolani » Sun Nov 11, 2012 10:50 pm

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

Post by brianfry713 » Tue Nov 13, 2012 2:56 am

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

Post by unagiroon » Fri Nov 16, 2012 1:26 pm

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

Post by hpjhc » Sat Sep 28, 2013 5:58 am

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

Post Reply

Return to “Volume 5 (500-599)”