507 - Jill Rides Again

[midra]

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]

Hi midra
In this time i have compiled ur programm in TC.
Can u explain ur algorithm ?

Thanks

[midra]

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
(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]

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]

Hello ..and what was the error????
tell me please because I have this problem too.

[midra]

thank you so much!
I finally got AC!

[mersault]

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!

[Darko]

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]

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]

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]

[anshul_scorp]

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]

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]

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

[Jan]

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]

Thanx...I got AC