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

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra » Wed May 25, 2005 5:38 am

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.....
:oops:
but thanks again for spent time and worry about my possible mistakes
good luck! byee!
:D

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Thu May 26, 2005 9:25 am

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:

Post by midra » Fri May 27, 2005 4:25 am

I would try to explain it because it is very difficult to me to understand codes even if they are mine :oops:

the first part just read the input, and then the only important part is the function max_sequence
(sorry for my bad english)

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!

Post by stubbscroll » Fri May 27, 2005 12:26 pm

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

Code: Select all

...
max_subsequence(int r,int t){
  int i,j=0,max[20003],start[20003],res=1,st=-1,en=-1;
  start[0]=1;
  for(i=1;i<r;i++){
    if(max[i-1]>=0){
...
You are reading from an uninitialized variable: max[0]. 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

Post by PerHagen » Fri May 27, 2005 5:32 pm

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:

Post by midra » Sun May 29, 2005 2:20 am

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

Post by mersault » Tue Jun 27, 2006 4:15 pm

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
Location: Calgary, Canada

Post by Darko » Tue Jun 27, 2006 11:06 pm

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

Post by mersault » Wed Jun 28, 2006 1:31 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:

Post by vinit_iiita » Wed Aug 09, 2006 7:44 pm

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:

Please see my problem

Post by anshul_scorp » Mon Jan 29, 2007 6:17 pm

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[20000],r=1;
int findmax(int *);
int max(int,int,int);
range value;

int main()
{
	int cases,arr[20000];
	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[0];
	        for(int j=1; j<arr[0];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[0]
{
int M[20000],from,to,i;
range temp;
bool allnull=true;
M[0]=a[0];
if(a[1]>=0)
        {
        M[1]=a[1];
        }
else
{
	M[1]=a[1];
	for(i=1;i<a[0];i++)
	{
		if(a[i]>0)
			allnull=false;
	}
	if(allnull)
	{
		temp.from=0;
		temp.to=0;
		return temp;
	}
}
if(a[0]==2)
{
	temp.from=1;
	temp.to=1;
	return temp;
}
else if(a[0]>1)
{
	for(i=2;i<a[0];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[1] to M[M[0]]
{
int max,i,ind;
bool clash=false;
max=M[1];
ind=1;
for(i=2;i<M[0];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
Please reply ASAP

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

Post by anshul_scorp » Mon Jan 29, 2007 6:32 pm

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[20000],r=1;
int findmax(int *);
int max(int,int,int);
range value;

int main()
{
   int cases,arr[20000];
   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[0];
           for(int j=1; j<arr[0];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[0]
{
int M[20000],from,to,i;
range temp;
bool allnull=true;
M[0]=a[0];
if(a[1]>=0)
        {
        M[1]=a[1];
        }
else
{
   M[1]=a[1];
   for(i=1;i<a[0];i++)
   {
      if(a[i]>0)
         allnull=false;
   }
   if(allnull)
   {
      temp.from=0;
      temp.to=0;
      return temp;
   }
}
if(a[0]==2)
{
   temp.from=1;
   temp.to=1;
   return temp;
}
else if(a[0]>1)
{
   for(i=2;i<a[0];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[1] to M[M[0]]
{
int max,i,ind;
bool clash=false;
max=M[1];
ind=1;
for(i=2;i<M[0];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
Please reply ASAP[/url]

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

WA

Post by soddy » Thu Feb 07, 2008 11:41 pm

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

Code: Select all

#include<iostream>
using namespace std;
int a[20001];
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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Feb 08, 2008 6:29 pm

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

Post by soddy » Sun Feb 10, 2008 8:10 am

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

Post Reply

Return to “Volume 5 (500-599)”