3. Technologická singularita vzorové riešenie

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

3
2
3
4

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

1
2
3
4
5

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

2
1
2
3
2
3
2

Predstavme si graf s \(n\) vrcholmi, pričom z vrcholu \(a\) vedie orientovaná hrana do \(b\) práve vtedy, keď \(P[a] = b\). Potom vrchol \(b\) nazveme následníkom \(a\), a vrchol \(a\) nazveme predchodcom \(b\). Môžeme si všimnúť, že každý vrchol má práve jedného následníka a práve jedného predchodcu. To je nutná a zároveň postačujúca podmienka na to, aby graf pozostával z orientovaných cyklov (ktoré zodpovedajú cyklom v permutácii) a žiadnych ďalších hrán. Dôkaz tohto tvrdenia nie je ťažký.

Potom vieme ľahko pre ľubovoľný vrchol \(v\) nájsť všetky vrcholy, ktoré patria do toho istého cyklu — začneme vrcholom \(a\), potom sa pozrieme na jeho následníka, potom na následníka následníka \(a\), potom na ďalšieho následníka, … až kým nenarazíme opäť na vrchol \(a\). Všetky takto nájdené vrcholy patria do cyklu s \(a\).

Počet cyklov vieme potom zistiť jednoducho — prechádzame postupne všetkými vrcholmi, a vždy, keď narazíme na neoznačený vrchol, zvýšime počet cyklov o \(1\) a označíme všetky vrcholy v tom istom cykle ako ten vrchol. Toto beží v čase \(O(n)\). Takto vieme implementovať riešenie hodné \(2\) bodov bežiace v čase \(O(nq)\) — na začiatku a po každej z \(q\) výmen spustíme výpočet počtu cyklov.

Chceme viac ako \(2\) body !!!

Budeme musieť nejako využiť, že po výmene sa nezmení permutácia na hocijakú inú. Dá sa ľahko dokázať, že po výmene sa počet cyklov zvýši o \(1\) ak čísla (vrcholy), ktoré sme vymieňali, ležia v rovnakom cykle; ak ležia v rôznych cykloch, počet cyklov sa zníži o \(1\).

Vyzbrojení týmto tvrdením vieme implementovať nasledujúce riešenie: na začiatku spočítame počet cyklov. Po každej výmene na pozíciách \(a,b\) zistíme, či sú \(a,b\) v rovnakom cykle, a príslušne upravíme počet cyklov. Zistiť, či \(a,b\) ležia v rovnakom cykle vieme napríklad nasledovne: nájdeme všetky pozície v cykle s \(a\), a zistíme, či medzi nimi je aj \(b\). Lepším (ako neskôr uvidíme) sa ale ukáže nasledujúci spôsob: nájdeme všetky pozície v cykle s \(a\), a najväčšiu z nich označíme \(m_a\). Podobne najväčšiu pozíciu v cykle s \(b\) označíme \(m_b\). Potom \(a,b\) ležia v rovnakom cykle práve vtedy, keď \(m_a = m_b\).

Takto dostávame riešenie s časom \(O(nq)\). Vo vstupných sadách \(2\) a \(3\) sa ale dá dokázať lepší čas \(O(n + q^2)\) a máme riešenie hodné \(6\) bodov.

Chceme viac ako \(6\) bodov !!!

Nastáva čas zamyslieť sa nad tým, ako rýchlejšie zistiť, či sú vymieňané pozície v rovnakom cykle. Najprv si ale vyriešime pomocný problém:

Na začiatku máme vrchol s nejakým číslom a nejakou hodnotou. Postupne prichádzajú udalosti troch typov:

• pýtame sa na najväčšiu hodnotu na vrcholoch s číslami v intervale \(\left\langle a; b \right)\)
• vznikol nový vrchol s číslom \(a\) a hodnotou \(b\) (máme zaručené, že neexistoval)
• vrchol s číslom \(a\) zanikol (máme zaručené, že existoval)

a na každú by sme chceli vedieť rýchlo odpovedať. Pozrime sa najprv na naivné riešenie, ktoré implementuje spájaný zoznam v ktorom si vrcholy pamätá v poradí podľa čísla:

• keď príde udalosť prvého typu, nájde v zozname v \(O(n)\) vrchol s najmenším číslom väčším rovným \(a\), a v \(O(n)\) sa pozerá na následníkov \(a\) až kým nenarazí na vrchol s číslom aspoň \(b\). Spomedzi nájdených vrcholov (okrem \(b\)) vyberie ten s najväčšou hodnotou a vráti ju.
• pri udalosti druhého typu v \(O(n)\) nájde vrchol s najväčším číslom \(x\), ktoré je menšie ako \(a\). Jeho následník — vrchol s číslom \(y\), spĺňa \(y > a\). Vložíme vrchol \(a\) “medzi” tieto dva vrcholy (príslušne nastavíme následníkov a predchodcov).
• pri udalosti tretieho typu v \(O(n)\) nájde v zozname vrchol s číslom \(a\), zmaže ho, a jeho predchodcovi a následníkovi nastaví následníka / predchodcu.

Výrazne by sa to urýchlilo, keby sme vedeli cestovať spájaným zoznamom rýchlejšie (prejsť viac hrán v jednej operácii). Do nášho spájaného zoznamu teda môžeme pridať akési hrany navyše. V takýchto hranách si pamätáme, akú najväčšiu hodnotu by sme objavili, keby sme tak cestovali v pôvodnom spájanom zozname (toto nazveme hodnotou hrany):

Po pridaní ďalších hrán sa ale naskytá viacero otázok.

• Ktorou hranou sa pri cestovaní zoznamom pohnúť ďalej? Z aktuálneho vrchola ich totiž môže viesť viacero. Toto veľmi závisí od pridaných hrán, no my sa uspokojíme s tým, že si vždy zvolíme najdlhšiu možnú hranu dopredu, ktorou nedosiahneme \(b\) (= hranu do vrchola s najväčším číslom menším ako \(b\)), ak je interval čísel, ktorých hodnoty nás zaujímajú \(\left\langle a; b \right)\).

• Keď pridáme nový vrchol \(x\) (udalosť druhého typu), každej hrane \(ab\), ktorá ho obsahuje (teda pri ceste z \(a\) do \(b\) v pôvodnom spájanom zozname by sme prešli \(x\)), musíme upraviť jej hodnotu (nastaviť ju na maximum z jej pôvodnej hodnoty a hodnoty \(x\)). Musíme preto vedieť rýchlo zistiť, ktoré hrany obsahujú nový vrchol. Tiež s pridaním nového vrchola potrebujeme niekedy pridať nové hrany — inak by sme si pomohli iba o konštantný faktor.

• Keď odoberieme vrchol \(x\), musíme odobrať všetky hrany, ktoré mali aspoň jeden koncový bod \(x\). A tiež upraviť hodnoty hrán, ktoré \(x\) obsahovali — to ale nie je také jednoduché ako pri udalostiach druhého typu (rozmyslite si prečo).

Vhodnou dátovou štruktúrou, pomocou ktorej vieme všetky tieto problémy vyriešiť, je skiplist. Princíp je nasledovný: pre každý vrchol \(x\) si pamätá jeho úroveň \(l(x)\). Na každej úrovni \(k\) má navyše hrany spájajúce vrcholy s úrovňou aspoň \(k\), a tieto vrcholy s hranami na úrovni \(k\) tvoria spájaný zoznam. Inak povedané: pre každý vrchol \(x\) a pre každú úroveň \(k \leq l(x)\) má skiplist navyše hrany na úrovni \(k\) vedúce do najbližších vrcholov s úrovňou aspoň \(k\).

Aby bol skiplist efektívny, úrovne vrcholov sa volia náhodne tak, aby všetky mali úroveň aspoň \(0\), aby rádovo polovica mala úroveň aspoň \(1\), rádovo štvrtina s úrovňou aspoň \(2\), … A teraz na konkrétnejšie riešenie spomínaných problémov:

• Pri pridaní nového vrchola \(x\) mu najprv náhodne (s vhodným rozložením pravdepodobností) určíme úroveň \(l(x)\). Následne pôjdeme od najnižšej úrovne po najvyššiu: označme aktuálnu úroveň \(u\). Prvého predchodcu na úrovni \(u\) označíme \(a\). Tiež nájdeme prvého následníka na tej úrovni a označíme ho \(b\). Zrejme existuje hrana \(ab\). Ak \(u \leq l(x)\), tak ju nahradíme hranami \(ax\), \(xb\) (ktorých hodnoty vieme vypočítať vďaka hodnotám na nižšej úrovni). Ak \(u > l(x)\), tak upravíme hodnotu hrany \(ab\). (Implementačné detaily, ako napríklad “čo ak neexistuje predchodca alebo následník” prenechávame na domyslenie vám.)

• Odobratie vrchola \(x\): opäť začneme od najnižšej úrovne. Označíme aktuálnu úroveň \(u\), prvého predchodcu na úrovni \(u\) označíme \(a\) a prvého následníka \(b\). Ak \(u \leq l(x)\), zmažeme hrany \(ax\), \(xb\) a nahradíme ich hranou \(ab\) (ktorej hodnotu spočítame podľa nižšej úrovne). Ak \(u > l(x)\), tak upravíme hodnotu hrany \(ab\) podľa nižšej úrovne.

Čas každej z týchto operácií závisí na počte úrovní, ktorých bude približne \(\log n\).

Vřáťme sa teraz k riešeniu pôvodnej úlohy o cykloch v permutáciách. Nie je náročné zovšeobecniť skiplist na cyklický skiplist. Na tomto cyklickom skipliste vykonávame trochu iné operácie — nepridávame a nemažeme žiadne vrcholy, ale vymieňame následníkov. Na to nám stačí implementovať pridanie hrany a odobratie hrany v skipliste, nakoľko výmena na pozíciách \(a,b\) pričom následníkmi sú \(c,d\) je to isté, ako keby sme najprv zmazali hrany \(ac, bd\) a následne pridali hrany \(ad, bc\).

• Pri mazaní hrany \(xy\) na úrovni \(0\) ju zmažeme. Následne postupujeme od najnižšej úrovne po najvyššiu: nech aktuálna úroveň je \(u\). Nájdeme prvého predchodcu \(x\), ktorý má úroveň aspoň \(u\), a označíme ho \(a\). Tiež nájdeme prvého následníka \(x\), ktorý má úroveň aspoň \(u\), a označíme ho \(b\). Zmažeme hranu \(ab\).

• Pri pridaní hrany \(xy\) na úrovni \(0\) ju pridáme. Postupujme od najnižšej úrovne po najvyššiu: nech aktuálna úroveň je \(u\). Nech \(a, b\) sú vrcholy s rovnakým významom ako v predchádzajúcom prípade. Pridáme hranu \(ab\), pričom jej hodnotu vieme spočítať z nižšej úrovne.

Môžete si premyslieť implementačné detaily, prípadne naprogramovať si skiplist.

Pomocou skiplistu vieme potom každú výmenu vykonať v čase \(O(\log{n})\). Celkový čas je teda \(O(n + q \log{n})\). Toto riešenie dostane \(20\) bodov.

A dá sa získať aj niečo medzi \(6\) a \(20\) bodmi?

Existuje “odmocninové” riešenie bežiace v čase \(O(n + q\sqrt{n})\), ktoré implementuje skiplist len s dvoma úrovňami, pričom na druhej je \(O(\sqrt{n})\) vrcholov. Toto riešenie bolo odmenené \(14\) bodmi, ale s nejakou optimalizáciou a tlačením konštánt sa dalo pretlačiť na \(20\).

Ako vyriešiť úlohu bez skiplistu?

Táto úloha sa dala riešiť aj bez ťažkých dátových štruktúr (akými sú skiplist, treap, a rôzne iné varianty vyvažovaných binárnych vyhľadávacích stromov). Riešenie je založené na nasledujúcej myšlienke:

Predpokladajme, že \(n >> q\). Vrcholy, ktoré sa nachádzajú v aspoň jednej výmene, budeme nazývať nestabilné. V opačnom prípade vrchol nazveme stabilný.

Zamerajme sa na konkrétny nestabilný vrchol \(a\). Pozrime sa na jeho predchodcu, na predchodcu predchodcu, … až kým nenarazíme na nestabilný vrchol (nie nutne rôzny od \(a\)). Postupnosť týchto vrcholov (vrátane prvého \(a\), bez nestabilného vrcholu, na ktorom sme skončili) označme \(P_0\). Zopakujme to isté po prvej výmene a dostaneme postupnosť \(P_1\). Rovnako po druhej, tretej, … Dá sa ľahko dokázať, že všetky tieto postupnosti sú rovnaké (\(P_0 = P_1 = \ldots = P_q\)) — teda že výmenami sa “chvost” vrcholu \(a\) nemení. (Rozmyslite si, prečo.)

Nech chvost \(a\) je \(a = a_0, a_1, \ldots, a_k\). Potom vieme chvost \(a\) nahradiť jedným novým vrcholom \(v\), pričom jeho následníkom je pôvodný následník \(a_0\), a jeho predchodcom je pôvodný predchodca \(a_k\). Na začiatku teda v \(O(n+q)\) zostrojíme reprezentantov chvostov (a upravíme príslušne všetky výmeny), a na tomto pustíme riešenie ktoré obdrží za normálnych okolností \(2\) body. Reprezentantov chvostov je \(O(q)\), takže dostávame celkový čas \(O(n + q^2)\) a riešenie dostane \(8\) bodov.

Na zvýšenie nášho počtu bodov použijeme prístup divide and conquer (rozdeľuj a panuj):

Rozdelíme si všetky otázky na prvú polovicu a druhú polovicu. Permutáciu / graf zmenšíme tým, že si zostrojíme reprezentantov chvostov ako v predchádzajúcom riešení, a problém vyriešime rekurzívne (už iba s prvou polovicou otázok). Druhú polovicu otázok vyriešime podobne, až na to, že počiatočný stav na začiatku druhej polovice je iný od počiatočného stavu na začiatku úlohy. To ale vyriešime jednoducho — prvú polovicu výmen odsimulujeme (v lineárnom čase).

O tomto riešení sa dá dokázať, že má čas \(O(n + q\log{q})\), a dosiahne plný počet bodov. Jeho nevýhodou oproti riešeniam s ťažkými dátovými štruktúrami je, že nie je online, čo ale na vyriešenie úlohy nebolo potrebné.