4. Rolka výterov vzorové riešenie

2
5
1 4 5 3 2
5
1 5 3 2 4

Vyter mozny
Vyter nemozny

Na prvý pohľad môže úloha vyzerať zložito. V tejto situácii zvykne pomôcť urobiť čo najviac pozorovaní a z nich potom prísť na riešenie. Nuž, poďme teda skúsiť spraviť nejaké pozorovania.

Prvým zjavným faktom je, že dielik \(i\) má vedľa seba dieliky \(i-1\) a \(i + 1\). Ďalším pozorovaním je, že keď toaleťák nejak skladáme, tak dieliky na párnych pozíciách pôjdu zľava doprava a dieliky na nepárnych pozíciách pôjcu sprava doľava, alebo naopak.

Pomalé riešenie

Našim cieľom je zistiť, či toaleťák niekde neprechádza sám sebou. Toaleťák sa pretína sám so sebou práve vtedy, keď medzi dielikom \(i\) a \(i+1\) leží nejaké \(j\) také, že dielik \(j-1\) alebo \(j+1\) nie je v permutácii medzi \(i\) a \(i+1\). Samozrejme, zároveň musí platiť, že \(i\) a \(j\) majú rovnakú paritu.

Ak majú \(i\) a \(j\) rovnakú paritu, znamená to, že zhyb medzi \(i\) a \(i+1\) je na rovnakej strane ako zhyb medzi \(j\) a \(j+1\). Preto ak by boli dieliky v permutácii v poradí \(i\), \(j\), \(i+1\), \(j+1\), zjavne by to znamenalo, že zhyb medzi \(i\) a \(i+1\) pretína zhyb medzi \(j\) a \(j+1\).

Stačí nám teda overiť, či naša podmienka pretínania neplatí pre žiadne \(i\), \(j\) rovnakej parity. Toto riešenie bude mať v závislosti od implementácie časovú zložitosť \(O(n^2)\) až \(O(n^3)\) na permutáciu a pamäťovú zložitosť \(O(n)\).

Vzorové riešenie

Permutáciu budeme konštruovať zhora nadol. Nech je najvrchnejší dielik \(i\). Z tohto dieliku nám doľava visí dielik \(i-1\) a doprava dielik \(i+1\). Ak je ďalším dielikom v permutácii \(i-1\), tak môžeme jednoducho podložiť visiaci dielik \(i-1\) pod \(i\). Dieliky, ktoré visia pod \(i-1\) teraz už budú visieť na pravej strane (kde už budú 2 visiace vrstvy). Analogicky by sme vedeli vyriešiť aj prípad, kde by bol ďalším očakávaným dielikom \(i+1\).

Čo ale máme spraviť, ak je ďalším očakávaným dielikom niečo iné, napríklad \(j\)? Nuž, na niektorej strane nám tento dielik visí (nie navrchu, ale niekde nižšie). Podložíme ho teda pod posledný pridaný dielik. Ak je \(j\) párne (resp. nepárne, podľa toho ako sme začali), tak po podložení na ľavej strane začne visieť \(j-1\) a na pravej \(j+1\).

Vždy teda máme na ľavej aj na pravej strane niekoľko visiacich vrstiev. V každom kroku sa môžeme zbaviť iba jednej z vnútorných vrstiev. Tu už možno vidno, že na reprezentáciu toho, čo visí naľavo a napravo vieme použiť dva stacky.

Algoritmus následne bude vyzerať tak, že prejdeme celú permutáciu a každý jej dielik samostatne spracujeme. Vždy, keď spracovávame dielik, pozrieme sa, či zrovna nie je na vrchu niektorého stacku. Ak je, môžeme ho zo stacku odstrániť. Ak na vrchu stacku nie je, tak na jednotlivé stacky pridáme jeho susedov (podľa parity).

Časová aj pamäťová zložitosť tohto riešenia je \(O(n)\) na permutáciu.

TC = int(input())

for _ in range(TC):
    n = int(input())
    
    left, right = [], []
    ok = lambda x: 0 < x <= n
    for x in map(int, input().split()):
        xl, xr = x - 1, x + 1
        if x % 2 == 0:
            xl, xr = xr, xl
    
        if left and left[-1] == xl:
            left.pop()
        elif ok(xl):
            left.append(x)
    
        if right and right[-1] == xr:
            right.pop()
        elif ok(xr):
            right.append(x)
    
    print(["Vyter nemozny", "Vyter mozny"][not left and not right])

#include <bits/stdc++.h>

using namespace std;

bool ok(int x, int n) {
    return 0 < x && x <= n;
}

int main() {
    int TC;
    cin >> TC;
    while(TC--) {
        int n;
        stack<int> left, right;
        cin >> n;
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            int xl = x - 1, xr = x + 1;
            if(x % 2 == 0)
                swap(xl, xr);
            if(!left.empty() && left.top() == xl)
                left.pop();
            else if(ok(xl, n))
                left.push(x);
            if(!right.empty() && right.top() == xr)
                right.pop();
            else if(ok(xr, n))
                right.push(x);
        }
        cout << "Vyter " << (left.empty() && right.empty() ? "mozny" : "nemozny") << '\n';
    }

    return 0;
}