507 - Jill Rides Again

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

[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

[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

[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

[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.

[@ce]

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

Code: Select all

Code removed after AC

[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

[@ce]

I had intialised si and ei wrong...thanks brianfry...you r a savior...i got AC

[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

[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

[Achilies_Saiful_Buet]

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

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

[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.

[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

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