## 507 - Jill Rides Again

Moderator: Board moderators

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
thanks again, but I think there is some problem between the compilers or something like that
I use Dev-cpp in Win98s and I get right outputs for all your samples, for the last sample you give me:

Code: Select all

``````1
10
20000
20000
20000
20000
20000
20000
20000
20000
20000
``````
in my computer I get this answer:

Code: Select all

``````The nicest part of route 1 is between stops 1 and 10
``````
Besides I read the code again and again and I can't understand how you get this output from my code:

Code: Select all

``````The nicest part of route 1 is between stops 1 and 2
``````
I am just so confused..... but thanks again for spent time and worry about my possible mistakes
good luck! byee! mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi midra
In this time i have compiled ur programm in TC.
Can u explain ur algorithm ?

Thanks

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
I would try to explain it because it is very difficult to me to understand codes even if they are mine the first part just read the input, and then the only important part is the function max_sequence

Code: Select all

``````for(i=1;i<r;i++){
if(max[i-1]>=0){
max[i]+=max[i-1]+s[i];
start[i]=start[i-1];
}
else{
max[i]+=s[i];
start[i]=i;
}
}
``````
here I read the sequence of numbers and I sum it sequentially and if in some moment the sum is <0 then it starts a new interval in a new variable

Code: Select all

``````for(i=r-1;i>0;i--){
if(max[i]>res){
res=max[i];
st=start[i];
en=i+1;
}
else if (max[i]==res){
if((i+1-start[i])>=(en-st)){
st=start[i];
en=i+1;
}
}
}
``````
here I just search in all intervals for the interval with maximal sum and that is bigger
then I just print it
I am a beginner in this field, so maybe my algorithm is wrong, or slow..I really don't know
I appreciate very much your help!
I hope this helps to understand my code
thanks again!
byee

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

### Re: 507 WA!

midra wrote:I don't understand Why I get wa!

Code: Select all

``````...
max_subsequence(int r,int t){
int i,j=0,max,start,res=1,st=-1,en=-1;
start=1;
for(i=1;i<r;i++){
if(max[i-1]>=0){
...``````
You are reading from an uninitialized variable: max. So, set the arrays max[] and start[] to the needed value (0?) before the loop.

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima
Hello ..and what was the error????
tell me please because I have this problem too.
hello !

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
thank you so much!
I finally got AC!

mersault
New poster
Posts: 4
Joined: Tue May 30, 2006 3:03 pm

### 507 - Jill rides again

Hello! I get WA on this problem, I've read the previous post and tried their input, all works with my program. My program seems to handle the rules about longest sequence, and the first in case of ties, so I don't know whats wrong. Maybe some special case I don't recognize? Any help would be most appreciated!
The program is in Java and I use a simple DP approach which I think those that have solved the problem will recognize immediately.

Btw, when I look at the ranklist I see only 3 people have got accepted using Java! I wonder why, should it be that hard...

CODE REMOVED, I GOT AC!
Last edited by mersault on Wed Jun 28, 2006 4:46 pm, edited 2 times in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
First of all, if you read that other thread, why didn't you post there?

Anyway - I tried playing with it, but I just got confused. We are off by one, and in some cases by two? I am not sure why your result prints (beststop+2). The bug must be there somewhere.

I print the result like this:

Code: Select all

``System.out.println("The nicest part of route " + tc	+ " is between stops " + start + " and " + end);``
Our codes are similar, but I can't figure out where that "2" comes from.

mersault
New poster
Posts: 4
Joined: Tue May 30, 2006 3:03 pm
Darko>> Sorry, I thought I'd read somewhere else here that it was preferred to start a new thread and not steal anyone elses thread. In that case I will use old threads in the future. These preferences change from forum to forum so it's sometimes hard to know which is preferred as a newcomer.

I (think I) can explain the +1 and +2. The reason for +1 is that the array starts at 0. Of course I could also have compensated for this earlier, but I chose to do it in the end. The extra +1 for the stop is because we are really looking at the segments between the stops. So the segment 0 (counting with the array index) is between busstop 0 and busstop 1. If I recorded that I start and stop at segment 0, this means I want to output start at busstop 1 (+1) and stop at busstop 2 (+2), so I think there is nothing strange with this?

I will however rewrite my code as you suggested, hopefully I find some bug along the way...

*UPDATE*

I now updated the code (se above) as Darko suggested, but no change. Still gives right answer to test input, though. I thought there could be trouble with the parsing of input and that ACM would interpret a program crash as WA, so I submitted it to SPOJ too (same problem there) I first got a crash error due to that I had written nice.trim() instead of nice = nice.trim(). However, when I corrected it got an "ordinary" WA there too...

*UPDATE AGAIN*

I rewrote the code in C (phew, I hate C!) and still got WA. Suddenly I realized that there was a very small error in the logic for the case of equally long strings (actually the +1 and +2 were not the problem)

If you have problems, try this input:

Code: Select all

``````1
5
1
-1
-2
99
``````
Simple, but none of the earlier inputs catches this.

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:
i am getting correct answers for all available test cases still i am getting WA plz help...

Code: Select all

``````#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
for (int i=0;i<n;i++)
{
int q;
cin>>q;
int a[q-1];
int b[q-1];
for (int j=0;j<q-1;j++)
cin>>a[j];
int sum=0,max=0,e=1,s=0,t=0,r=1,p=1,max1;
bool flag=true;
for (int j=0;j<q-1;j++)
{
sum=sum+a[j];
if (sum < 0)
{
sum=0;
t=j+1;
r=j+2;
p=j+2;

}
else
{
if (sum>=max)
{
int h=max;
max=sum;
r++;
p++;
if (p>r)
r=p;
if (h<sum)
{e=r;
s=t;
max1=sum;
}

}
else
p++;

}
}
if(max1==max && r-t==e-s)
flag=false;
if(!flag)
{if ((s+1==q && e==q) || max<=0)
cout<<"Route "<<i+1<<" has no nice parts"<<endl;
else
{cout<<"The nicest part of route "<<i+1<<" is between stops ";
cout<<s+1<<" and "<<e<<endl;
}
}
else
{if ((t+1==q && r==q) || max<=0)
cout<<"Route "<<i+1<<" has no nice parts"<<endl;
else
{cout<<"The nicest part of route "<<i+1<<" is between stops ";
cout<<t+1<<" and "<<r<<endl;
}
}

}
return 0;
}

``````
[/b]
win

anshul_scorp
New poster
Posts: 2
Joined: Mon Jan 29, 2007 5:59 pm
Contact:

I am getting wrong answer for the problem.
I have not considered the input given in previous post coz it contains entries with o 'niceness' values....which is not allowed as stated in quesiton....
ence, Jill has rated each road on an integer scale of ``niceness.'' Positive niceness values indicate roads Jill likes; negative values are used for roads she does not like. There are not zero values. Jill plans where to l
see the problem at : http://acm.uva.es/p/v5/507.html

I have tried my code for all the given inputs except the ones with zero as input.
Please let me know the input for which my program fails

Code: Select all

``````//http://acm.uva.es/problemset/submit.php

#include <iostream>
using namespace std;

struct range
{
int from,to;
};

range maxsubarray(int* );
int matrix,r=1;
int findmax(int *);
int max(int,int,int);
range value;

int main()
{
int cases,arr;
range value;
cin>>cases;
for(int i=0; i<cases;i++)
{
for(int k=0;k<20000;k++)
arr[k]=0;
value.from=0;
value.to=0;
cin>>arr;
for(int j=1; j<arr;j++)
cin>>arr[j];
value=maxsubarray(arr);
if(value.from==0)
{
cout<<"Route "<<i+1<<" has no nice parts\n";
}
else
{
cout<<"The nicest part of route "<<i+1<<" is between stops "
<<value.from<<" and "<<value.to+1<<"\n";
}
}
}

range maxsubarray(int *a) //to find max subarray of a[i] from i=1 to i=arr
{
int M,from,to,i;
range temp;
bool allnull=true;
M=a;
if(a>=0)
{
M=a;
}
else
{
M=a;
for(i=1;i<a;i++)
{
if(a[i]>0)
allnull=false;
}
if(allnull)
{
temp.from=0;
temp.to=0;
return temp;
}
}
if(a==2)
{
temp.from=1;
temp.to=1;
return temp;
}
else if(a>1)
{
for(i=2;i<a;i++)
{
M[i]=max(M[i-1]+a[i],a[i],i);
}
to=findmax(M);//to is index of maximum number
from=matrix[to];
temp.from=from;
temp.to=to;
return temp;
}
}

int findmax(int *M) //find index of maximum from M to M[M]
{
int max,i,ind;
bool clash=false;
max=M;
ind=1;
for(i=2;i<M;i++)
{
if(max>M[i])
{
}
else if(max<M[i])
{
max=M[i];
ind=i;
}
else
{
clash=true;
if((ind-matrix[ind])>(i-matrix[i]))
{
}
else if((ind-matrix[ind])<(i-matrix[i]))
{
ind=i;
}
else
{
if(matrix[ind]>matrix[i])
{
ind=i;
}
}
}
}
return ind;
}

int max(int a,int b,int d)
{
if(a>=b)
{//if a is maximum
matrix[d]=r;
return a;
}

else
{//if b is maximum
r=d;
matrix[d]=d;
return b;
}
}
``````
Sorry for the length of the code

anshul_scorp
New poster
Posts: 2
Joined: Mon Jan 29, 2007 5:59 pm
Contact:
I am getting wrong answer for the problem.
I have not considered the input given in previous post coz it contains entries with o 'niceness' values....which is not allowed as stated in quesiton....
ence, Jill has rated each road on an integer scale of ``niceness.'' Positive niceness values indicate roads Jill likes; negative values are used for roads she does not like. There are not zero values. Jill plans where to l
see the problem at : http://acm.uva.es/p/v5/507.html I have ... gram fails

Code: Select all

``````

#include <iostream>
using namespace std;

struct range
{
int from,to;
};

range maxsubarray(int* );
int matrix,r=1;
int findmax(int *);
int max(int,int,int);
range value;

int main()
{
int cases,arr;
range value;
cin>>cases;
for(int i=0; i<cases;i++)
{
for(int k=0;k<20000;k++)
arr[k]=0;
value.from=0;
value.to=0;
cin>>arr;
for(int j=1; j<arr;j++)
cin>>arr[j];
value=maxsubarray(arr);
if(value.from==0)
{
cout<<"Route "<<i+1<<" has no nice parts\n";
}
else
{
cout<<"The nicest part of route "<<i+1<<" is between stops "
<<value.from<<" and "<<value.to+1<<"\n";
}
}
}

range maxsubarray(int *a) //to find max subarray of a[i] from i=1 to i=arr
{
int M,from,to,i;
range temp;
bool allnull=true;
M=a;
if(a>=0)
{
M=a;
}
else
{
M=a;
for(i=1;i<a;i++)
{
if(a[i]>0)
allnull=false;
}
if(allnull)
{
temp.from=0;
temp.to=0;
return temp;
}
}
if(a==2)
{
temp.from=1;
temp.to=1;
return temp;
}
else if(a>1)
{
for(i=2;i<a;i++)
{
M[i]=max(M[i-1]+a[i],a[i],i);
}
to=findmax(M);//to is index of maximum number
from=matrix[to];
temp.from=from;
temp.to=to;
return temp;
}
}

int findmax(int *M) //find index of maximum from M to M[M]
{
int max,i,ind;
bool clash=false;
max=M;
ind=1;
for(i=2;i<M;i++)
{
if(max>M[i])
{
}
else if(max<M[i])
{
max=M[i];
ind=i;
}
else
{
clash=true;
if((ind-matrix[ind])>(i-matrix[i]))
{
}
else if((ind-matrix[ind])<(i-matrix[i]))
{
ind=i;
}
else
{
if(matrix[ind]>matrix[i])
{
ind=i;
}
}
}
}
return ind;
}

int max(int a,int b,int d)
{
if(a>=b)
{//if a is maximum
matrix[d]=r;
return a;
}

else
{//if b is maximum
r=d;
matrix[d]=d;
return b;
}
}
``````
Sorry for the length of the code

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

### WA

I am also getting WA in this problem. Here's the code.

Code: Select all

``````#include<iostream>
using namespace std;
int a;
int main()
{
ios_base::sync_with_stdio(false);
int t,n;
cin>>t;
for(int kase=1;kase<=t;kase++)
{
cin>>n;
for(int i=1;i<n;i++)
cin>>a[i];
int x=1,y=1,sum=0,resX=1,resY=1,res=0;
while(y<=n)
{
if(sum>res || (res==sum && y-x>resY-resX))
{
resX=x; resY=y; res=sum;
}
if(sum+a[y]<0)
{
sum=0;
x=y+1;
y=x;
sum=0;
}
sum+=a[y];
y++;
}
if(res>0)
cout<<"The nicest part of route "<<kase<<" is between stops "<<resX<<" and "<<resY<<endl;
else
cout<<"Route "<<kase<<" has no nice parts"<<endl;
}
}
``````
I am not selfish, I just want everything.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the case.

Input:

Code: Select all

``````1
14
-10
-17
17
6
1
-15
15
11
10
1
6
-7
-7``````
Output:

Code: Select all

``The nicest part of route 1 is between stops 3 and 12``
Hope it helps.

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

### @Jan

Thanx...I got AC I am not selfish, I just want everything.