SBLBCK-Editorial

editorial
1

PROBLEM LINK: Click here

Contest: Hey Newbees, Here is Some Honey -ROUND 3

Author: Arefin Labib

Co-Author: Samia Rahman

Tester: Sanjida Akter

Tester: Redowan Ibrahim

Tester: Nazmus Sakib

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Data structure.

PROBLEM:

There are T test cases. In each cases, you are given n strings and an integer x with each string. The strings must not have to be unique. You have to make a queue with the strings in such way that, you have to place the string S_i to the x th position of that queue. (i \leq n)
Then there are m strings denoted as A_i. You have to remove all the strings similar to A_i from the queue.
After the operations, you have to print the remaining queue.

EXPLANATION:

This is a basic Data structure problem. The operations in this problems are designed following some operations of std::list.
In this problem, There are two operations with the queue. First one is to add a string to the given position. We can do this operation by list::insert.
Then we have to remove all the strings that is similar to the given string. We can use list::remove to do that.
Thats it, at last print the list.

The problem can also be solved using different data structures. Have a look in the status.

TIME COMPLEXITY

O(n)

SOLUTIONS:

C++ 
//BISMILLAHIR RAHMANIR RAHIM
//INNALLAHA_MA_AS_SABIRIN
//SOTO's
#include<bits/stdc++.h>
#define ls ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define __ <<" "<<
#define loop(m,n) for(m=0;m<n;m++)
#define rloop(m,n) for(m=n-1;m>=0;m--)
#define case(z) "Case " << z++ << ": "
#define ptf(b) puts(b?"YES":"NO")
#define newline cout<<endl
#define quit return 0

using namespace std;


int main()
{
    //ls
    //freopen("ain.txt","r",stdin);
    //freopen("aoutt.txt","w",stdout);
    int t;cin>>t;while(t--){
        ll n,m,i,x;
        cin>>n;
        list<string> li;
        list<string>::iterator it;
        string s,a;
        loop(i,n)
        {
            cin >> s >> x ;
            it=li.begin();
            advance(it,x-1);
            li.insert(it,s);
        }
        cin>>m;
        loop(i,m)
        {
            cin>>a;
            li.remove(a);
        }
        if(li.size()==0)
            cout << -1 << endl;
        else
        {
            for(it=li.begin();it!=li.end();it++)
            {
                cout << *it << endl;
            }
        }
    }
    quit;
}
1 Like