MPALACE - Editorial

Mind Palace Editorial.

PROBLEM LINK: Contest Page | CodeChef

Practice
Contest

Author: Reyaan Jagnani
Tester: Jay Sharma
Editorialist: Reyaan Jagnani

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Heaps Heap (data structure) - Wikipedia

PROBLEM:

To make lexicographically smallest sequence combining all the given sequences such that all the elements are different from each other.

QUICK EXPLANATION:

Take the first elements from the sequences and subsequently add the numbers to new sequence till every element in every sequence is iterated

EXPLANATION:

First of all make a 2D array or vector to store all the sequences. Then note the sizes of these sequences in another array.
Then make a priority queue which can store pairs and the topmost element of priority queue is smallest.
Now, insert first element of each sequence in the priority queue along with the index of the respective sequences in the second element of pair.
Now, remove the fist element from the priority queue, and note its value as well as index of its sequence. Now insert the value into final sequence
and add the next element (if present) of the sequence corresponding to the index of the removed element.
Repeat this procedure until every element of the given sequences is traversed and the priority queue becomes empty.
Print the final sequence obtained.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define testcase ll t; cin>>t; while(t--)
#define endl "\n"
#define quick ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define timetaken cerr<<fixed<<setprecision(10); cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl
using namespace std;
int main()
{
    quick;
    testcase
    {
        ll n;
        cin>>n;
        vector<vector<ll>> vect(n);
        ll pos[n] = {};
        ll sum_of_sizes = 0;
        for(ll i=0; i<n; i++)
        {
            ll m;
            cin>>m;
            sum_of_sizes+=m;
            vect[i] = vector<ll>(m);
            for(ll j = 0; j<m; j++)
            {
                cin>>vect[i][j];
            }
        }
        vector<ll> ans;
        priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> q1;
        for(ll i=0; i<n; i++)
        {
            q1.push({vect[i][0],i});
            pos[i]++;
        }
        while(ans.size()!=sum_of_sizes)
        {
            pair<ll,ll> p1 = q1.top();
            q1.pop();
            ans.push_back(p1.first);
            if(pos[p1.second]<vect[p1.second].size())
            {
                q1.push({vect[p1.second][pos[p1.second]], p1.second});
                pos[p1.second]++;
            }
        }
        for(ll i=0; i<ans.size(); i++)
        {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    timetaken;
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tt=1;
    cin >> tt;
    while(tt--)
    {
        int n;
        cin >> n;
        queue<int> a[n];
        for(int i=0;i<n;i++)
        {
            int m;
            cin >> m;
            for(int j=0;j<m;j++)
            {
                int x;
                cin >> x;
                a[i].push(x);
            }
        }
        priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
        for(int i=0;i<n;i++)
        {
            pq.push({a[i].front(),i});
            a[i].pop();
        }
        vector<int> ans;
        while(!pq.empty())
        {
            ans.push_back(pq.top().first);
            int i = pq.top().second;
            pq.pop();
            if(!a[i].empty())
            {
                pq.push({a[i].front(),i});
                a[i].pop();
            }
        }
        for(int i=0;i<ans.size();i++)
            cout << ans[i] << " ";
        cout << '\n';
    }
    return 0;
}
2 Likes