Zadanie

“Ojojoooj, kedy už Dano pripraví tú úlohu? Dalo by sa? Bolo by možné? Mohlo by byť umožnené?!”, hovoril si Adam počas vykonávania potreby na svojej záhradnej latríne, ktorú postavil ešte jeho starý otec. Ako si to tak hovoril, a rozčuľoval sa, podvedome si pripravoval toaletný papier. Rôzne ho skladal a podsúval, až mu ostal iba jeden \(n\)-vrstvový obdĺžniček. Začal teda rozmýšľať, akými rôznymi spôsobmi sa dá \(n\)-kúskový toaletný papier poprekladať. Adam má svojich favoritov, no nevie, či sa vôbec dajú vytvoriť. Zmyslel si teda, že Danovi napíše a povie mu, aby ako úlohu do KSP pripravil toto.

Úloha

Adam vám povie niekoľko permutácií obdĺžničkov toaletného papiera. O každej z nich by chcel vedieť, či sa skutočne dá získať nejakým poprekladaním. Adamov papier je taký tenký, že jeho hrúbku môžeme zanedbávať.

Prekladanie a podsúvanie funguje nasledovne. Adam rozvinie celý papier na zem a jeho obdĺžničky si očísluje od 1 do \(n\). Prekladať môže iba po perforáciách. Následne vždy môže priložiť ľubovoľný obdĺžniček na iný obdĺžniček zhora alebo zdola, ak mu nebránia iné obdĺžničky. Môže teda ľubovoľne prekladať. Ak si stále nie ste istí, či môže prekladať nejakým konkrétnym spôsobom, pravdepodobne ním prekladať môže.

Formát vstupu

Na prvom riadku vstupu je číslo \(t\) – počet permutácií, na ktoré sa vás Adam opýta. Platí \(1 \leq t \leq 100\). Nasleduje \(t\) dvojíc riadkov. Na prvom riadku z \(i\)-tej dvojice je číslo \(n_i\) – počet obdĺžničkov celého toaletného papiera. Na druhom riadku z \(i\)-tej dvojice je \(n_i\) medzerou oddelených čísiel predstavujúcich permutáciu, na ktorú sa Adam pýta. Prvé číslo v permutácii je číslo obdĺžnička navrchu, posledné predstavuje číslo spodného obdĺžnička. Platí \(1 \leq n_i \leq 10\,000\).

Formát výstupu

Pre \(i\)-tu permutáciu vypíšte na samostatnom riadku Vyter mozny, ak je možné poprekladať toaletný papier do danej permutácie. V opačnom prípade na tomto riadku vypíšte Vyter nemozny.

Príklad

Input:

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

Output:

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)\)\(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.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.