TVT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest : Click here

Author: arnie8991
Tester: horsbug98
Editorialist: arnie8991

DIFFICULTY:

EASY

PREREQUISITES:

Dequeue

EXPLANATION:

The trick to solving this within the given constraints is to use a dequeue and keep track of the elements inside the array/list using a dictionary/map.
Take a dequeue Li and each time Tony tries to enter a number check if we can enter the number or not and then do a push_right and in order to remove one of his element do a remove_front. Do a push_left and remove_back in case of Thanos.
In order to see if an element can be entered in Li or not check:

  1. If it’s already there in Li. If it is not present then,
    • If the list is full,
      • Check if the other person has got some elements to remove. If he has you can enter the new elements y removing his last entered element from Li.
      • If the other person has no elements to remove we cannot enter the element.
    • If the list is not full, enter the elements

NOTE: Using dequeue is just one way of solving the problem. There are many other ways to solve this. Do let me know about any other ways you solved this in the comments!

SOLUTIONS:

Setter's Solution 
from collections import deque

test  = int(input())

for _ in range(test): 
    tony = []
    thanos = []
    n,k = map(int,input().split())
    tony = [int(x) for x in input().split()]
    thanos = [int(x) for x in input().split()]

    list_numbers = []
    li = deque(list_numbers)

    present_elements = {}

    no_tony = 0 
    no_thanos = 0
    
    for i in range(0,n):
        #Tony's turn 
        if (tony[i] not in present_elements or present_elements[tony[i]] == 0):
            if len(li) == k and no_thanos>0:
                x = li.popleft()
                present_elements[x] = 0
                no_thanos-=1
            if(len(li)<k):
                li.append(tony[i])
                no_tony+=1
                present_elements[tony[i]] = 1
            
        #Thanos's turn
        if (thanos[i] not in present_elements or present_elements[thanos[i]] == 0):
            if len(li) == k and no_tony>0:
                x = li.pop()
                present_elements[x] = 0
                no_tony-=1
            if(len(li)<k):
                li.appendleft(thanos[i])
                no_thanos+=1
                present_elements[thanos[i]] = 1

    if no_tony>no_thanos:
        print('TONY')
    elif no_tony<no_thanos:
        print('THANOS')
    else:
        print('RUN TONY')
Tester's Solution 
#include "bits/stdc++.h"
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n, k, tonyc = 0, thanosc = 0;
        cin >> n >> k;
        vector<int> a(n), b(n);
        for(int i = 0; i < n; ++i)
            cin >> a[i];
        for(int i = 0; i < n; ++i)
            cin >> b[i];
        vector<int> tony, thanos;
        set<int> s;
        for(int i = 0; i < n; ++i) {
            if(!s.count(a[i])) {
                if(s.size() == k && thanosc) {
                    s.erase(thanos.back());
                    thanos.pop_back();
                    --thanosc;
                }
                if(s.size() < k) {
                    s.insert(a[i]);
                    tony.push_back(a[i]);
                     ++tonyc;
                }
            }
            if(!s.count(b[i])) {
                if(s.size() == k && tonyc) {
                    s.erase(tony.back());
                    tony.pop_back();
                    --tonyc;
                }
                if(s.size() < k) {
                    s.insert(b[i]);
                    thanos.push_back(b[i]);
                    ++thanosc;
                }
            }
        }
        if(tonyc > thanosc)
            cout << "TONY\n";
        else if(thanosc > tonyc)
            cout << "THANOS\n";
        else
            cout << "RUN TONY\n";
    }
    return 0;
}
2

looks interesting, thanks for sharing

1 Like