Coach problem

[Pen72]

A train moves from A through a station to B.

Initially, the coaches of the train is numbered by 1,2,...n.

You want to know whether you can rearrange the coaches in the order: a1,a2,...an .

Each coach can be disconnected from the train and

enter the station from A and leave the station to B ,
or move directly from A to B without entering the station.
A coach can only leave the station if the coaches arriving before it have left the station.

Given a1,a2,...an , please output

YES, if it is possible to rearrange the coaches.
NO, if it is impossible.

Input Format
The first line is an integer denoting the number of queries.
For each query, there are 2 lines:
The first line is an integer , i.e. number of coaches.
The second line is an integer sequence


Sample Input 0
3
5
3 4 1 2 5
5
1 2 3 4 5
5
5 4 3 2 1
Sample Output 0

YES
YES
NO

My code shows success in most test cases, but got one wrong answer in a test case. Don't know how to modify it, or is there a better way to write the code.

#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
using namespace std;
 
int main(void)
{
    int T;
    cin >>T;
    while (T--)
    {
        int n;
        cin >> n;
        vector<int> target(n);
        target.clear();
        for (int i = 0; i < n; i++)
        {
            cin >> target[i];
        }
        int num=1,a=0,ans=1;
        queue<int> s;
        while(a<n)
        {
            if(target[a]==num)
            { a++; num++;}
            else if(!s.empty() && s.front()==target[a])
            {s.pop();a++;}   
            else if(num<=n)
            {
                s.push(target[a++]);   
                num++;
            }
            
            else 
            {
                ans=0;
                break;
            }
        }
                
        if (ans)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

[DizzyDon]

It sounds like you're supposed to use a queue, not a stack. Stacks are last-in first-out, whereas queues are first-in first-out.

[Pen72]

I've changed to a queue, am actually not quite sure what to put in the second while loop.

[DizzyDon]

My suggestion was to try the exact same thing but with a queue.
Is it still wrong?
I bet there's a smarter way to do it by analyzing the constraints on the process.
For instance, whatever the first number is, all the smaller values must occur in order after it (not necessarily consecutively, but in order).
E.g., if 4 is first, then 1, 2, 3, must appear in order after it since they must've been moved into the queue before the 4 was moved across.
Anyway, I've gotta get some shuteye, so I'm done here. :-)

[DizzyDon]

Looks like you should be pushing num, not target[a], right?
And I don't understand the num < n test. Maybe num < target[a]?
Something like this:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        vector<int> target(n);
        for (int i = 0; i < n; i++) cin >> target[i];
        queue<int> s;
        int a = 0, num = 1;
        for ( ; a < n; a++)
        {
            if (target[a] == num)
                num++;
            else if (!s.empty() && s.front() == target[a])
                s.pop();
            else if (num < target[a])
                s.push(num++);
            else
                break;
        }
        cout << (a == n ? "YES\n" : "NO\n");
    }
}

[Pen72]

I've tried your code, it still fail at a test case. What's the meaning of num < target[a] at line24?

[DizzyDon]

I was trying to modify your code without thinking about it too much, so I don't really know the meaning of that line. Here's my last attempt for the night.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        vector<int> target(n);
        for (int i = 0; i < n; i++) cin >> target[i];
        queue<int> s;
        int a = 0;
        for (int num = 1; num <= n; num++)
        {
            if (target[a] == num)
                a++;
            else if (!s.empty() && s.front() == target[a])
            {
                s.pop();
                a++;
            }
            else
                s.push(num);
        }
        while (!s.empty() && s.front() == target[a]) { a++; s.pop(); }
        cout << (a == n ? "YES\n" : "NO\n");
    }
}

[lastchance]

The station is the only means by which a coach can be overtaken.

A coach must have been overtaken if it is less than the maximum of the numbers in front of it.

Just check that the coaches which have been overtaken (1 and 2 in the first example) are still in order.

[lastchance]

#include <iostream>
#include <vector>
using namespace std;

bool test( const vector<int> &coach )
{
   int mx_through = 0, mx_station = 0;
   for ( int i = 0; i < coach.size(); i++ )
   {
      if ( coach[i] < mx_through )                    // must have been overtaken, so has passed through the station
      {
         if ( coach[i] < mx_station ) return false;   // can't change order in station
         mx_station = coach[i];
      }
      else
      {
         mx_through = coach[i];
      }
   }
   return true;
}

int main()
{
   int T;
   cin >> T;
   while( T-- )
   {
      int n;
      cin >> n;
      vector<int> coach( n );
      for ( int i = 0; i < n; i++ ) cin >> coach[i];
      
      cout << ( test( coach ) ? "YES" : "NO") << '\n';
   }
}

[DizzyDon]

That's the idea!
Looks like you got rid of the n parameter at the last minute though and forgot to change the n in the function to coach.size(). :-)

[lastchance]

DizzyDon wrote:

Looks like you got rid of the n parameter at the last minute though and forgot to change the n in the function to coach.size(). :-)

Mmm, you're right. I had one of those version-control problems that occur more frequently with approaching old age!

I've corrected the code above. Sorry!

[Pen72]

I've tried to write this problem again, but it shows segmentation fault.
Also, I'd like to ask when should the vector size+1 and when shouldn't. Somtimes it seems essential, but sometimes that is not needed.

#include <iostream>
#include <stack>
#include <vector>
#include <stdio.h>
#include <deque>
#include <cmath>
using namespace std;
 
int main(void)
{
    int T,n; cin >>T;
    while(T--)
    {
        cin>>n;
       deque<int>A(n+1);
        for(auto &a:A)
            cin>>a;
      deque<int>station(n+1);
      deque<int>B(n+1);
      int val;
      while(!A.empty())
      {
          if(A.front()==B.front())
          { 
            A.pop_front();
            B.pop_front();
          }
          else if(station.front()==B.front())
          {
              station.pop_front();
              B.pop_front();
          }
        else
        {  
            val=A.front();
            station.push_back(val);
            A.pop_front();
        }
     }
      if(!station.empty())
        cout<<"NO"<<"\n";
     else
        cout<<"YES"<<"\n";
    }
    return 0;
}

[seeplus]

shows segmentation fault

Probably because a deque is accessed when it is empty. Only A L21 is checked for not empty first before access. Note that .front() needs a non-empty deque.

[Pen72]

What would be the easiest way to modify it?

[seeplus]

Well first I''d check if that is the problem by testing if the object is empty before a .front() or . pop(). and if it is then issue an error alert. If the alert isn't triggered then that's not the issue. If you do get an alert, then if you have a meaningful message you'll know where is the issue.

[Pen72]

I modified my code, shows wrong answer now.

#include <iostream>
#include <stack>
#include <vector>
#include <stdio.h>
#include <deque>
#include <cmath>
using namespace std;
 
int main(void)
{
    int T,n; cin >>T;
    while(T--)
    {
      cin>>n;
      deque<int>A(n);
      for(int num=1;num<=n;num++)
          A.push_back(num);
  
      deque<int>station(n+1);
      deque<int>B(n+1);
        for(int i=0;i<n;i++)
        {int x; cin>>x; B.push_back(x);}
            
      int val;

      while(!A.empty() || (!station.empty() && !B.empty() && station.back()==B.front()))
      {
        
            if(A.front()==B.front())
            { 
            A.pop_front();
            B.pop_front();
            }
            else if(station.back()==B.front())
            {
              station.pop_back();
              B.pop_front();
            }
          else
          {  
            val=A.front();
            station.push_back(val);
            A.pop_front();
          }
       }
     
      if(station.empty())
        cout<<"YES"<<"\n";
     else
     {cout<<"NO"<<"\n";}
        A.clear();
        B.clear();
        station.clear();
    } 
    return 0;
       
}

[TheIdeasMan]

I modified my code, shows wrong answer now.

Time to learn how to use a debugger.

[Pen72]

I did pass the debugger, it's logic problem here.
Sample Output 0 should be
YES
YES
NO

While with the code it shows
NO
NO
NO

[TheIdeasMan]

I did pass the debugger, it's logic problem here.

The compiler is not a debugger. A debugger is what one uses to solve logical errors.

Speaking of compiling, were there any warnings? What warnings were turned on?

[seeplus]

The debugger is what is used to trace through the code as it is executed and watch the contents of variables etc. From the program design you should know how the program is expected to perform. When you find where the program execution/variable values deviate from that expected by the design, then you have found an issue. This may be a coding issue or a design issue. If it's a coding issue (eg off-by-one etc), then fix the code and try again. If it's design issue, then the design needs to be changed accordingly and then the program code changed as needed for the new design. For problems like this, the algorithm design is the important part. If that is not right then the program will never work properly.