ALTTAB - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: vlad_c
Tester: satyam_343
Editorialist: iceknight1093

DIFFICULTY:

1396

PREREQUISITES:

Sets, maps, or similar data structures

PROBLEM:

You’re given the order in which N programs are opened (or reopened).
Each time a program is (re)opened, it moves to the front of the list.

Find the final order of programs; print the last 2 characters of each one.

EXPLANATION:

Let S_i denote the i-th input string.

Instead of looking at the process in forward order, let’s look at it in reverse order.

  • Clearly, S_N is the last program opened, which means it’ll be in the front of the list.
  • S_{N-1} is the penultimate program opened.
    If it doesn’t equal S_N, we know it’s the second program in the list; otherwise it equals S_N and was already processed.
  • Similarly, if S_{N-2} equals either S_N or S_{N-1}, then it would’ve been processed already.
    Otherwise, it’s the next program in the list.
  • More generally, for any 1 \leq i \leq N,
    • If S_i equals one of S_{i+1}, S_{i+2}, \ldots, S_N, then it was already processed ‘later’.
    • Otherwise, it’s the next program in the list since everything in front of it was taken care of.

This gives us a straightforward algorithm:

  • For each i from N down to 1, check if S_i equals one of S_{i+1}, S_{i+2}, \ldots, S_N, i.e, if it was seen before.
    To do this quickly, the simplest way is to maintain a set or map of strings, each time inserting S_i into it.
    This can be implemented with, for example, std::set<string> or std::unordered_set<string> in C++, set in Python, or HashSet in Java.
  • If has occurred earlier, ignore it. Otherwise, print its last two characters.

TIME COMPLEXITY

\mathcal{O}(N) set/map operations per testcase.

CODE:

Author's code (C++) 
///(sol_stl.cpp) Expected: AC.
#include <bits/stdc++.h>
#define maxs 45

using namespace std;
char s[maxs+5];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    stack<string> stk;
    string s;

    while (n--) {
        cin >> s; stk.push(s);

    }

    set<string> ss;
    while (!stk.empty()) {
        if (!ss.count(stk.top())) {
            cout << stk.top().substr(stk.top().size() - 2, 2);
            ss.insert(stk.top());
        }
        
        stk.pop();
    }
    
    return 0;
}
Editorialist's code (Python) 
n = int(input())
names = []
for i in range(n):
    names.append(input())

seen = set()
ans = ''
for i in reversed(range(n)):
    if names[i] in seen: continue
    ans += names[i][-2]
    ans += names[i][-1]
    seen.add(names[i])
print(ans)
2

I’d encourage the reader to try to implement some solutions without stl (e.g. own hashtable, trie). After all, one of the purposes of the problem is to help one get better at applying some DS.

Also, maybe some code golf? Can you make a shorter implementation than this:

ss = set()
for word in reversed([input() for _ in range(int(input()))]):
	if word not in ss:
		print(word[-2:], end = '')
		ss.add(word)

I hope you learned something useful from this problem.

3

https://www.codechef.com/viewsolution/98831543

My solution is giving TLE. Can anyone help me find what specific block of code is responsible for TLE error.

4

Finding an element in an array may take O(n) comparisons, each O(MAXLEN). Your solution is O(n^2 \cdot MAXLEN).

For example, the last test’s input is something like p_1, p_2, p_3, .. p_k, p_1, p_2, p_3, .. p_k, with 2k = n. The program names p_1, p_2, p_3, .. p_k are all pairwise distinct. For the last half you always need to go to the back of the array and bring the program to the front, so for the last n/2 find operations you do n/2 comparisons every time, so you do 1/4 n^2 \cdot O(MAXLEN) operations.

You need to use a more efficient method of querying if a string is already present in a Data Structure. Either keep the hashes for the strings and query a hashtable in O(1) comparisons amortised (the tests haven’t been created to counter hashes), or use a trie for exactly one comparison, or use binary tree-like structures (std::set) for O(\log n) comparisons.

1 Like
5

include <bits/stdc++.h>
using namespace std;

int main() {
int n;
cin>>n;
vectorvec(n);
for(int i=0;i<n;i++)
cin>>vec[i];
unordered_setst;
for(auto it:vec){
if(st.find(it)!=st.end())
st.erase(it);
st.insert(it);
}
string ans=“”;
for(auto it:st){
int n=it.size();
ans+=it.substr(n-2,2);
}
cout<<ans;

return 0;

}
Can anyone tell me why this code is giving wrong answer , i didn’t able to think of any test case

6

Thank you

7

hmmm can anyone help me identify what is wrong with my code? Thank you

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    set<string> check;
    stack<string> tabs;
    stack<string> holder;
    for(int i=0 ;i<n;++i){
        string s;
        cin>>s;
        if(i==0){
            tabs.push(s);
            continue;
        }
        auto pos = check.find(s);
        if(pos==check.end()){
            tabs.push(s);
            check.insert(s);
            continue;
        }
        if(pos!=check.end()){
            holder.push(s);
            while(tabs.top()!=s){
                string temp = tabs.top();
                tabs.pop();
                holder.push(temp);
            }
            tabs.pop();
            
            while(!holder.empty()){
                string temp= holder.top();
                holder.pop();
                tabs.push(temp);
            }
            continue;

        }
    }
    while(!tabs.empty()){
        string s=tabs.top();
        int len=s.size();
        cout<<s[len-2]<<s[len-1];
        tabs.pop();
    }
    return 0;
}