CAC202 - CRACK-A-CODE 2.0 Editorial

PROBLEM LINK:

Practice
Contest

Author: Vallabh Deshpande
Tester: Mayuresh Patle
Editorialist: Vallabh Deshpande

DIFFICULTY:

EASY

PREREQUISITES:

Stack, Queue

PROBLEM:

Given the order of arrival of patients numbered 1 to N in a hospital, determine the order of them meeting the doctor such that:

  1. The patient numbered X booked appointment before patient Y if X < Y.

  2. If the patient who missed the appointment most recently has arrived, that patient should meet the doctor first otherwise the next available person should meet the doctor in order of booking.

QUICK EXPLANATION:

Use two queues for storing order of meeting and arrival and a stack for storing numbers of people who missed their appointment. If the topmost person in stack is available then that person will meet the doctor otherwise next person who arrives shall meet the doctor if that person hasn’t missed the appointment yet.

EXPLANATION:

The problem requires us to fulfill the meeting of the person that booked appointment most recently but has missed his / her appointment and is currently available. Since we have to determine which people have missed their appointment and we require most recent among them we can use a stack to store them, and if the topmost numbered person is available we will keep fulfilling their appointment. Otherwise we store the order of booking and order of arrival in two separate queues and if any person who hasn’t missed his /her appointment arrives we fulfill that person’s appointment.

SOLUTIONS:

Setter's Solution
    #include<bits/stdc++.h>

    using namespace std;

    #define ll long long

    int main()
    {
       ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int t;
        cin>>t;
        while(t--){
            ll n, x;
            cin>>n;
            stack< ll > missed;
            queue< ll > arrival, booking;
            bool available[n + 1] = {0};

            for(ll i = 1; i <= n; ++i){
                cin>>x;
                arrival.push(x);
                booking.push(i);
            }

            x = 0;

            while(!booking.empty() || !missed.empty()){
                while(!arrival.empty() && arrival.front() < x){
                    available[arrival.front()] = true;
                    arrival.pop();
                    if(!arrival.empty()) x = max(x, arrival.front());
                }
                if(!arrival.empty()){
                    x = max(x, arrival.front());
                    available[arrival.front()] = true;
                }
                while(!missed.empty() && available[missed.top()]){
                    cout<<missed.top()<<" ";
                    missed.pop();
                }
                while(!arrival.empty() && !booking.empty() && booking.front() != arrival.front()){
                    missed.push(booking.front());
                    booking.pop();
                }
                if(!booking.empty()){
                    cout<<booking.front()<<" ";
                    booking.pop();
                }

                if(!arrival.empty()){
                    arrival.pop();
                }
            }
            cout<<"\n";
        }
        return 0;
    }
Tester's Solution
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        //freopen("inp.txt","r",stdin); freopen("out.txt","w",stdout);
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int T,n,curr,mx;
        cin>>T;
        while(T--)
        {
            cin>>n;
            stack <int> s;
            vector <bool> in(n+1);
            mx=0;
            while(n--)
            {
                cin>>curr;
                if(mx<curr)
                {
                    cout<<curr<<" ";
                    ++mx;
                    while(mx<curr) s.push(mx++);
                    continue;
                }
                in[curr]=1;
                while(!s.empty() and in[s.top()]) 
                {
                    cout<<s.top()<<" ";
                    s.pop();
                }
            }
            while(!s.empty()) 
            {
                cout<<s.top()<<" ";
                s.pop();
            }
            cout<<"\n";
        }
        return 0;
    } 
1 Like