## 507 - Jill Rides Again

Moderator: Board moderators

ishtiaq
New poster
Posts: 1
Joined: Thu Feb 14, 2013 8:50 am

### Re: 507 - Jill Rides Again

What should be the output for this input?
1
9
3 -3 8 -11 2 2 2 2

It should be:
The nicest part of route 1 is between stops 5 and 9
But My Accepted Code shows:
The nicest part of route 1 is between stops 1 and 9
.

UVa should add a test case like this for my code.  MrRusof
New poster
Posts: 2
Joined: Thu May 25, 2006 5:30 am

### Re: 507 - Jill Rides Again

Hi, I have the following code, have tested on every input I found here and elsewhere, and I am still getting WA. Could a guru show me an input that the code does not solve?

Even though some example inputs in this thread consider roads with zero niceness, I have not because the problem description says there are no roads with zero niceness in the input.

Code: Select all

``````#include <stdlib.h>
#include <stdio.h>

/* #define DEBUG 0 */

typedef struct segment {
int value;
int i;
int j;
struct segment* prev;
struct segment* next;
} segment;

void print_route(struct segment* first) {
struct segment *curr = first;
while(curr != NULL){
printf("%2d (%2d, %2d)\n", curr->value, curr->i, curr->j);
curr = curr->next;
}
printf("\n");
}

void solve(const int r, const int s) {
int n;
int i = 0;
int len = s - 1;
struct segment* first;
struct segment* curr;
struct segment* prev;
struct segment* next;
struct segment* max;

/* Ignore negative prefix. */
while(i<len) {
scanf("%d", &n);
if(n > 0) break;
i++;
}

/* Route has no nice parts if we reached the end. */
if(i == len) {
printf("Route %d has no nice parts\n", r);
return;
}

/* Preprocess the route. */
first = curr = (segment *)malloc(sizeof(segment));
curr->value = n;
curr->i = i + 1;
curr->j = i + 2;
curr->prev = NULL;
curr->next = NULL;
i++;
while(i<len) {
scanf("%d", &n);
if((curr->value > 0 && n > 0) || (curr->value < 0 && n < 0)) {
curr->value += n;
curr->j++;
} else {
prev = curr;
curr = (segment *)malloc(sizeof(segment));
prev->next = curr;
curr->value = n;
curr->i = i + 1;
curr->j = i + 2;
curr->prev = prev;
curr->next = NULL;
}
i++;
}

/* Cut a negative tail. */
if(curr->value < 0) {
prev = curr->prev;
prev->next = NULL;
free(curr);
}

#ifdef DEBUG
/* Print preprocessed route. */
printf("Preprocessed route\n");
print_route(first);
#endif

/* Visit each separator. */
curr = first->next;
while(curr != NULL) {
if(curr->prev->value >= -curr->value && curr->next->value >= -curr->value) {
#ifdef DEBUG
printf("Found pivot %d\n", curr->value);
printf("curr->value = %d\n", curr->value);
printf("curr->prev = %d\n", curr->prev->value);
printf("curr->next = %d\n", curr->next->value);
printf("curr->i = %d\n", curr->i);
printf("curr->j = %d\n\n", curr->j);
#endif

/* Join previous and next. */
curr = curr->prev;
next = curr->next;

curr->value += next->value + next->next->value;
curr->j = next->next->j;
curr->next = next->next->next;
if(curr->next != NULL) curr->next->prev = curr;

free(next->next);
free(next);

#ifdef DEBUG
printf("New segment\n");
printf("curr->value = %d\n", curr->value);
if(curr->prev != NULL) printf("curr->prev = %d\n", curr->prev->value);
else printf("curr->prev = NULL\n");
if(curr->next != NULL) printf("curr->next = %d\n", curr->next->value);
else printf("curr->next = NULL\n");
printf("curr->i = %d\n", curr->i);
printf("curr->j = %d\n\n", curr->j);

printf("Current route\n");
print_route(first);
#endif

if(curr->prev != NULL) {
curr = curr->prev;
} else {
curr = curr->next;
}
} else {
curr = curr->next->next;
}
}

#ifdef DEBUG
printf("Processed route\n");
print_route(first);
#endif

/* Select maximum */
max = curr = first;
while(curr != NULL) {
if(curr->value > max->value) {
max = curr;
} else if(curr->value == max->value) {
if(curr->j - curr->i > max->j - max->i) {
max = curr;
}
}
curr = curr->next;
}

/* Print result. */
printf("The nicest part of route %d is between stops %d and %d\n", r, max->i, max->j);

/* Free the route. */
curr = first;
while(curr != NULL) {
prev = curr;
curr = curr->next;
free(prev);
}
}

int main() {
int b, r, s;
scanf("%d", &b);
r = 0;
while(r++ < b) {
scanf("%d", &s);
solve(r, s);
}
return 0;
}
``````

ifty
New poster
Posts: 1
Joined: Wed Nov 16, 2016 6:19 pm

### Re: 507 - Jill Rides Again

I am getting WA pls help me

Code: Select all

``````#include<bits/stdc++.h>
using namespace std;
long long arr,l,r,m;
int main()
{
//freopen("out.txt","w",stdout);
long long i,j,n,key,cs,k;
cin>>cs;
for(k=1;k<=cs;k++){
cin>>n;
for(j=0;j<n-1;j++)
cin>>arr[j];
//cout<<n<<" input ";
//for(j=0;j<n-1;j++)
//cout<<arr[j]<<" ";
if(n==2&&arr<=0)
{
cout<<"Route "<<k<<" has no nice parts\n";
continue;
}

long long cur = arr >= 0? arr : 0, mx = arr;
long long start = 0, endpoint = 0;
long long i,j = cur == 0 ? 1 : 0;
for (i = 1; i < n-1; i++) {
cur += arr[i];
if (cur >= mx) {

mx = cur;
endpoint = i;
if (j > start) start = j;
}
if (cur < 0) {
cur = 0;
j = i+1;
}
m[i-1]=cur;
r[i-1]=start;
l[i-1]=endpoint;
// cout<<cur<<' '<<start<<' '<<endpoint<<endl;
}
long long left=endpoint,right=start;
for(long long t=n-2;t>=0;t--)
{
if(mx==m[t])
{
long long p=left-right;
long long q=l[t]-r[t];
if(q>=p)
{
left=l[t];
right=r[t];
}
}
}
//cout<<mx;
if(mx<=0)
cout<<"Route "<<k<<" has no nice parts\n";
else
cout<<"The nicest part of route "<<k<<" is between stops "<<right+1<<" and "<<left+2<<endl;
if(k==cs)
break;
}
return 0;
}

``````