6. Taylor sendvič vzorové riešenie

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

5

Pár slov na začiatok

Tento príklad sa dal na plný počet riešiť dvoma spôsobmi.

Jeden je náročnejší, no myšlienky v ňom sú možno trochu všeobecnejšie. Ten sa dá vymyslieť celkom jednoducho, pokiaľ poznáte správne nástroje. Je pri ňom možno oveľa jasnejšie, že funguje, no je o niečo ťažší na implementáciu. Tento rozoberieme postupne po subtaskoch na začiatku.

Na konci je druhý prístup, ktorý je jednoduchší na vysvetlenie a implementáciu, no ťažší na vymyslenie a uvedomenie si, že naozaj funguje. Ten rozoberieme v poslednom odstavci.

Bruteforce

Je ťažké pozerať sa naraz na veľa farieb, pozrime sa teda na jednu. Pre jednu farbu x vzniknú “územia”, kde sú iné farby ohraničené farbou x. Cesta, čo sa začína na okraji tohto územia a končí niekde inde na okraji je jedna z hľadaných ciest. Začnime prehľadávanie v jednom z týchto okrajových bodov a vždy, keď nájdeme vrchol farby x, ďalej už nepokračujeme. Všetky takéto konce nám tvoria validné cesty zo začiatku prehľadávania. Keď pustíme prehľadávanie z každého vrchola (každý je niekedy okrajom nejakého územia), dostaneme výsledok.

Toto riešenie má časovú zložitosť \(O(n^2)\), čo samo o sebe stačilo na polovicu bodov.

Prečo sa nepozerať na všetky vrcholy naraz?

Keď prechádzame veľakrát DFS-kom strom, prechádzame kopu vrcholov, s ktorými nič nerobíme, lebo nie sú správnej farby. Poďme to teda robiť všetko naraz.

Strom si v ľubovoľnom vrchole zakoreníme a spustíme z neho prehľadávanie do hĺbky. V každom vrchole si budeme pamätať pre každú farbu, ku koľkým takýmto “okrajovým vrcholom” v jeho podstrome môže viesť takáto cesta (pamätáme si to napríklad v mape s farbou a počtom okrajových vrcholov). Vždy keď sme v nejakom vrchole s farbou x, pozrieme sa, koľko okrajových vrcholov s farbou x je v jeho podstrome. To sú všetky cesty, čo môžu vychádzať z neho smerom dole. Toto nám už stačí na \(3.\) podúlohu, kde sme na ceste, teda v DFS-ku idú všetky cesty iba hore. (aj keď sa dala riešiť aj oveľa jednoduchšie)

Ale vo všeobecnom strome budeme mať ešte cesty, ktoré nejdú iba hore. Každú takúto cestu zarátame v jej najvyššom vrchole. Takže keď spracovávame nejaký vrchol, môžeme zobrať nejakú farbu x okrajových vrcholov v jednom podstrome a poslať z nich cestu do okrajových vrcholov tej istej farby v ostatných podstromoch.

Ako si udržiavať takéto informácie v DFS-ku?

V každom vrchole máme v mape pre všetky farby ich príslušné počty okrajových vrcholov. Z ich otca sa dá dostať do tých istých vrcholov, okrem tých, ktoré majú rovnakú farbu ako ich otec, lebo ich otec zablokuje. Potrebujeme teda spojiť mapy pre synov do jedného pre otca a zmeniť hodnotu pre jeho farbu na \(1\).

Na toto použijeme metódu, ktorá sa volá “small to large merging”. Jej myšlienka je jednoduchá, vždy keď spájame dve mapy, jednu z nich musíme celú presypať do druhej. Presypeme teda tu menšiu. (to, ku ktorému vrcholu patrí ktorá mapa vieme ľahko zmeniť pomocou metódy swap). Ak sa na tento proces pozrieme z pohľadu prvku, tak ak je v nejakej mape a presype sa do inej, veľkosť mapy, do ktorej sa práve presypal, sa aspoň zdvojnásobí. Finálna veľkosť mapy je najviac \(n\), teda presypaní každého prvku bude najviac \(O(log(n))\).

Každé prehodenie prvku trvá v mape tiež \(O(log(n))\), teda dokopy bude časová zložitosť \(O(nlog^2(n))\), prípadne \(O(nlog(n))\) ak použijeme hash mapu. Pamäte nám stačí \(O(n)\), lebo každý vrchol je naraz len v jednej z máp. Toto riešenie stačilo na plný počet bodov.

Optimálne riešenie

Dá sa to ale ešte rýchlejšie. Na cesty sme sa pozerali v ich najvyššom bode, ale vrátme sa na chvíľu na počítanie podľa okrajových bodov.

Graf si znova zakoreníme v ľubovoľnom vrchole a spustíme z neho prehľadávanie do hĺbky. Cesty si ale tentokrát zorientujeme tak, aby začiatok danej cesty bol v DFS prechode navštívený skôr ako jej koniec. Teda keď v DFS-ku prechádzame nejaký vrchol, zaujíma nás, koľko možných začiatkov tejto farby je prístupných z vrcholov, ktoré sme už navštívili.

Keď prejdeme cez vrchol farby x do jeho podstromu, vrchol zablokuje všetky začiatky, ktoré boli prístupné, teda jeho hodnotu v zozname nastavíme na \(1\). Keď z jeho podstromu vychádzame, zablokujú sa všetky, čo sme videli v podstrome, no odbolokujú sa tie, čo sme pred tým zahodili, a pribudne \(1\) za tento vrchol, ktorý je teraz tiež dostupný a už sme ho spracovali v DFS-ku.

Odpoveď počítame tak, že vždy pred tým ako, pôjdeme do podstromu a zablokujeme niektorú farbu, spočítame, koľko ciest ide z tohto vrchola do odblokovaných navštívených vrcholov (to sú cesty do všetkých vrcholov, ktoré ideme teraz zablokovať).

Počty začiatkov si môžeme pamätať v zozname, kde sa v každom vrchole mení len jedna hodnota, teda toto riešenie dosahuje časovú zložitosť \(O(n)\) a pamäťovú tiež \(O(n)\).