8. Divné diery vzorové riešenie

1

2
0
2
1
1 1 1
2
1 2
1 1

0
1

2

5
0 1 2 3
4 7 8 6
3
0 7 3
4 2 3
2 1 10
3
3 7
4 14
2 10

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

-1
2
1
6
3
0

Táto úloha mala veľmi nechutne dlhé zadanie. Ak ste sa však nenechali odradiť ani dĺžkou zadania ani číslom úlohy, riešenie na 4 body nebolo vôbec ťažké. Pred tým ako sa bezhlavo pustíme do programovania, je užitočné si ťažkú úlohu čo najviac zľahčiť.

Základné pozorovania

Ako prvé sa zamyslime, ako si zjednodušiť úvahy s dierami.

Môžeme si uvedomiť, že ak sme najskorej chodili peši a potom použili nejakú dieru, mohli sme rovno použiť tú istú dieru a opäť, mali by sme aspoň rovnako dobré riešenie. Teda diery sa oplatí používať len na začiatku, keď sme vo vrchole \(0\).

Druhé pozorovanie je, že vždy sa nám oplatí použiť najviac jednu dieru. Ak by sme použili nejaké dve, najprv \(A\) a potom \(B\), mohli sme rovno použiť \(B\), a mali by sme aspoň také dobré riešenie ako doteraz. To vyplýva z toho, že nezáleží kde sa nachádzame, diera nás k sebe premiestni vždy rovnako rýchlo.

Posledné užitočné aj keď nie nutné je pridať si do vrcholu \(0\) fiktívnu dieru s časom \(0\) a cenou \(0\). To bude zodpovedať možnosti, kde nepoužijeme žiadnu dieru. Zvyšok vzoráku rátame s tým, že sme tento trik spravili.

Naraz sa nám úloha značne zjednodušila: Máme strom, v niektorých vrcholoch sú diery. Ak by sme chceli v \(i\)-tej otázke použiť \(j\)-tu dieru, vieme sa z nej pohnúť o vzdialenosť \(b_i - w_j\). Chceme teda vybrať dieru z najnižšou cenou, z ktorej sa vieme dostať do vrcholu \(a_i\).

Toto nám stačí na pohodlný bruteforce.

Bruteforce

Nasledovné riešenie mohlo získať 4 body:

Z každej diery spustíme prehľadávanie a tým pre každý vrchol spočítame vzdialenosti od všetkých dier. Potom pri query \(i\) nájdeme v zozname pre vrchol \(a_i\) všetky diery \(j\) vo vzdialenosti najviac \(b_i - w_j\) a vyberieme z nich dieru s najlepšiou cenou.

Celková časová zložitosť tohoto riešenia bude \(O((n+q)\cdot m)\), čo stačilo na získanie 4 bodov.

Strom je plytký!

V tretej sade má strom hĺbku najviac \(100\). Skúsme sa zamyslieť, ako nám to pomôže pri riešení úlohy.

Zoberme si \(i\)-tu query a predstavme si, že by sme na ňu použili dieru \(j\). Potom cesta z diery do \(a_i\) musí prejsť nejakým predkom \(a_i\) (každý vrchol je sám sebe predkom). Zoberme si tak každého predka \(a_i\) a diery ktoré sú v jeho podstrome. Všimnime si, že pre každú z týchto dier vieme vypočítať hodnotu “koľko času by nám trvalo sa dostať do \(a_i\) pomocou diery \(j\) ak by sme išli cez predka \(u\)” ako súčet \(w_i+(\text{dĺžka cesty z }u_i\text{ do diery }j) + (\text{dĺžka cesty z }u_i\text{ do }a_i)\). Počítanie týchto hodnôt samo o sebe nie je dobrý nápad, lebo to je pomalé, ale uvidíme, že to povedie k lepšiemu riešeniu.

Túto hodnotu vieme vypočítať ako súčet dvoch hodnôt, jedna závisí od diery \(j\) a \(u\), druhá od \(a_i\) a \(u\), vidíme, že voľba \(j\) ovplyvní len prvú hodnotu a voľba \(i\) len druhu, teda ich môžme spočítať pre všetky \(j\) a \(u\) zvlášť a pre všetky \(i\) a \(u\) zvlášť. Toto počítanie už nebude pomalé, lebo každý vrchol má najviac \(100\) predkov, teda sa vyskytne v \(100\) výpočtoch.

Pre každý vrchol spočítame jeho vzdialenosť od dier v jeho podstrome. Ak by sme mali túto informáciu spočítanú, ľahko nájdeme odpoveď na otázku: ak sme vo vrchole \(u\) a máme ešte \(t\) času, aká je najlacnejšia diera v podstrome vrcholu \(u\), do ktorej sa vieme za čas \(t\) dostať?

Ukážeme si ako:

V každom vrchole \(u\) si budeme pamatať všetky diery v jeho podstrome, ale namiesto ich hodnoty \(w\) k nej ešte pripočítame vzdialenosť do vrcholu \(v\) – vrchol kde sa diera nachádza. Tieto hodnoty označíme \(w'\). Teraz platí:

Ak sa pýtame na otázku pre vrchol \(u\) a čas \(t\), vyberieme tie diery, ktoré majú \(w' \leq t\) a na tie sa budeme vedieť dostať. (Ak hovorím, že sa na ne vieme dostať, myslím že sa vieme z vrcholu \(0\) premiestniť do nich a potom peši prejsť do \(u\), to celé v čase najviac \(t\).)

Teraz si diery vo vrchole \(u\) usporiadame podľa hodnoty \(w'\). Potom nás zaujíma len prvých niekoľko dier s dosť malou \(w'\). Z nich vieme vybrať tú s najlepšou cenou napríklad pomocou prefixových miním, keďže sa vždy pýtame na prefix a hodnoty sa nemenia.

Ak sa teraz budeme pýtať postupne na predkov vrcholu \(a_i\), pričom vhodne upravíme čas, ktorý nám ešte zostáva, a hľadať pomocou tejto otázky najlepšie diery, dostaneme sa zjavne k riešeniu.

Celé predpočitanie teda bude vyzerať takto:

1. Každú dieru \(i\) zaznačíme aj do jej predkov, pričom k \(w_i\) pripočítame vždy dĺžku cesty do toho konkrétneho predka, tým získame hodnoty \(w'\).
2. Pre každý vrchol diery usporiadame podľa \(w'\).
3. Pre každý vrchol spočítame prefixové minimá podľa hodnôt \(c\).

Každú dieru zaznačujeme do jej predkov a potom týchto \(O(mH)\) záznamov utriedime, teda dostávame zložitosť \(O(mH \log m)\).

Odpoveď na otázku: “som vo vrchole \(u\) a mám ešte \(t\) času” potom získame tak, že v zozname pre vrchol \(u\) binárne vyhľadáme poslednú dieru, ktorú vieme použiť a následne sa spýtame na prefixové minimum.

Celé riešenie jednej query teda bude:

1. Začíname vo vrchole \(u=a_i\) s časom \(t=b_i\).
2. Spýtame sa na otázku “som vo vrchole \(u\) a mám \(t\) času” a upravíme výsledok.
3. Ak nie sme v koreni stromu priradíme \(t=t-\)čas na prejdenie do otca u, \(u=\) otec u. Ideme znova na krok 2.
4. Zohľadnili sme všetky možnosti, teda vieme výsledok.

Pre každú query H krát vyhľadáme odpoveď, čo dáva zložitosť \(O(qH \log m)\).

Celé riešenie má časovú zložitosť \(O(n + mH \log m + qH \log m)\). Pamäťová zložitosť bude \(O(mH + n)\).

Na čo nám to bolo?

Prečo sme mali dlhočizný vzorák o nejakom riešení, ktoré ani neprešlo na plný počet bodov? Odpoveď znie, že často sú podúlohy nastavené tak, aby pomohli k riešeniu celej úlohy. A táto úloha nie je výnimkou.

Nechcem spoilovať, tak tento nadpis nenapíšem

Kebyže máme strom plytký, úlohu ľahko vyriešime. Všeobecne, ak je strom hlboký a chceme, aby bol plytký, správnym nástrojom sú centroidy. Ak ste nikdy nepočuli o centroidoch a centroidovej dekompozícií, môžete si o tom prečítať tu.

V rýchlosti sa to da opisať takto:
Centroidovou dekompozíciou vhodne usporiadame vrcholy stromu tak, že sa úplne nezachová samotná štruktúra zadaného stromu, ale vznikne nový, úplne iný strom hĺbky najviac \(\log n\) - čo je dobré znamenie, lebo pre takto hlboké stromy už poznáme riešenie.

Tento strom však bude mať jednu peknú vlastnosť. Keď sa pozrieme na jeho ľubovolný vrchol v centroidovom a pôvodnom strome, a pozrieme sa na podgrafy, ktoré vzniknú keď ho odstránime, budú mať tieto podgrafy rovnaké vrcholy pre centroidový aj pôvodný strom.

Toto sa ukáže ako veľmi užitočná vlastnosť, ak sa pýtame na cesty v strome, lebo pre vrchol na ceste v pôvodnom aj centroidovom strome platí, že ak ho odstránime, bude začiatočný a koncový vrchol cesty v rôznych podstromoch – z formulácie vidíme, že je práve to čo centroidové stromy poskytujú.

Keď si teraz porovnáme, čo sme robili v predošlom odseku za 6 bodov, jediná podstatná vlastnosť, ktorú sme potrebovali, bola, že aspoň v jednom vrchole, ktorý je na ceste medzi nejakou dierou a query, zohľadníme túto dieru. Stále je to tá istá vlastnosť, čo som prakticky napísal 3x za sebou, aby to bolo vidieť, a čo sa v centroidových stromoch zachováva. (toto celé ešte nižšie dokážeme)

Otázka znie, či si aj pre takýto strom budeme vedieť predpočítať podobné hodnoty ako minule. Bystrému čitateľovi hneď dojde, že to je len rečnícka otázka, a že to ide :p

Začneme rovnako ako predtým, každú dieru zaznačíme aj do jej predkov v centroidovom strome. Problém bude, že novú hodnotu \(w'\) diery nebudeme tak ľahko vedieť spočítať. Nebudeme sa môcť vždy iba pozrieť na cenu hrany do otca a túto cenu pripočítať. Na chvíľu ale predpokladajme že máme funkciu \(\textit{tree}\_\textit{dist}(a, b)\), ktorá vráti vzdialenosť vrcholov \(a\) a \(b\) v strome zo vstupu.

Pomocou tejto funkcie už ľahko dokončíme predpočítanie tak ako sme to robili minule, s výnimkou, že hodnota, ktorú si uložíme vo vrchole \(u\), ak sme pridali dieru do vrcholu \(v\) bude \(w + \textit{tree}\_\textit{dist}(u, v)\).

Ak by sme aj druhú časť riešenia upravili dostávame to isté riešenie, len s drobnými zmenami:

1. Prvý krok je rovnaký.
2. Spýtame sa otázku na vrchol \(u\) s časom \(b_i - \textit{tree}\_\textit{dist}(a_i, u)\) – uvedomme si, že presne toto robíme aj v predošlej verzií.
3. Nastavíme \(u\) na jeho otca v centroidovom strome.

Vidíme, že sa naozaj oplatilo robiť celé to predošlé riešenie, keďže toto nie je o moc iné – teda samozrejme za predpokladu, že to čo sme tu teraz napísali a (vyššie som povedal, že to platí) naozaj platí.

Ukážeme, že to naozaj funguje a implementácia

Môžeme si všimnúť, že v tomto riešení sa nám dosť často stane, že keď v nejakom vrchole \(v\) zohľadňujeme nejakú dieru \(d\), museli by sme, kebyže si to nakreslíme v pôvodnom strome, viackrát prejsť po tej istej hrane/ceste. (formálne vrchol \(v\) je predok \(lca(v, d)\)) Teda hodnota \(w'\) bude v takýchto prípadoch moc veľká. Nikdy sa nám našťastie ale nestane, že by sme mali pre nejakú dieru hodnotu \(w'\) moc malú, keďže vždy pripočítame \(\textit{tree}\_\textit{dist}\).

Teda určite nájdeme výsledok aspoň tak veľký ako má byť. To je fajn. Teraz nám stačí ukázať, že aspoň pri jednom vrchole \(v\), ktorý budeme pri query kontrolovať budeme mať cestu do diery \(d\), kde ani jednu hranu nepoužijeme viac krát. Inými slovami, že nájdeme výsledok taký malý, resp. práve taký, aký má byť.

Nie je ťažké si uvedomiť, že správne vzdialenosti bez opakovaných hrán dostaneme práve pre vrcholy \(v\), ktoré sú v centroidovom strome predkami \(d\) aj \(a_i\) (alebo sú to \(d\) alebo \(a_i\)) a pre ktoré \(a_i\) a \(d\) ležia v rozdielných centroidových podstromoch, a teda aj v rozdielných podstromoch v pôvodnom strome. Chceme ukázať, že existuje aspoň jeden vrchol, ktorý spĺňa túto vlastnosť. Na to aby sme to ukázali, zíde sa nám vedieť ako centroidový strom vytvárame – z tohoto postupu to už priamo vyplýva.

Centroidová dekompozícia

Pre nejaký strom vieme nájsť centroid jedným prehľadávaním. Ak pre vrchol platí, že veľkosti podstromov vo všetkých jeho susedoch je \(\leq\) polovici vrcholov v strome, je tento vrchol centroid. Inak je centroid v podstrome, ktorý má najväčšiu veľkosť a na ten sa rekurzívne zavoláme. Každý strom má centroid a týmto postupom ho nájdeme. (Dôkaz tohoto algoritmu neuvádzame.)

Keď sme našli centroid, musíme nájsť centroidy v podstromoch jeho synov a na to rekurzívne opäť použijeme vyššie popísaný algoritmus.

Pauza na pitie.

Pokračujme v dôkaze. Pozrime sa na vrcholy na ceste medzi \(a_i\) a \(d\). Ak za centroid zvolíme ľubovoľný iný vrchol a graf rozdelíme na jeho podstromy, celá táto cesta bude stále v jednom podstrome. Čiže z hľadiska cesty sa nič zaujímavé nestalo.

A ak vyberieme za centroid jeden z vrcholov na ceste, cesta sa rozdelí do jeho podstromov, a to tak, že vrchol \(a_i\) bude v podstrome jedného jeho syna a vrchol s dierou \(d\) bude v nejakom inom. Teda minimálne prvý vrchol z cesty, ktorý v algoritme vyššie vyberieme za centroid bude spĺňať požadovanú vlastnosť, a teda pri ňom dostaneme správne vzdialenosti od \(a_i\) aj \(d\).

Teraz vieme, že máme správne riešenie, stačí nám implementovať posledný detail.

Funkcia \(\textit{tree}\_\textit{dist}\)

Na implementáciu tejto funkcie vieme napríklad použiť binary lifting, alebo teda klasický LCA algoritmus. Ak ste o tom ešte nikdy nepočuli, môžete si viac prečítať v tomto článku, kvôli dĺžke vzoráku to tu už neuvádzame.

Ak sa nám ale nechce kódiť binary lifting, ide to aj krajšie! Celkovú časovú zložitosť to síce nezlepší, ale v praxi to program môže niekoľkonásobne zrýchliť.

Môžme si uvedomiť, že vždy sa pýtame len na vzdialenosti medzi vrcholom a nejakým jeho centroidovým predkom. Tých je však len \(O(\log n)\) preto môžeme mať zapamätanú pre každý vrchol vzdialenosť do jeho centroidových predkov. Jeden spôsob ako takúto informáciu získať, je priamo pri dekompozícií si pre novonájdený centroid spočítať vzdialenosť do všetkých vrcholov v jeho podstrome. Zložitosť na predpočítanie zostane \(O(n \log n)\), ale na query sa zmenšila na \(O(1)\), lebo sa stačí len hodnoty pamätať v poli. Detaily implementácie prenecháme na čitateľovi.

Časová a pamäťová zložitosť

Centroidovú dekompozíciu zvládneme v čase \(O(n \log n)\), rovnako rýchlo bude trvať aj predpočítanie vzdialeností do centroidových predkov.

Predpočítanie dier nám zaberie \(O(m \log m \log n)\) času – najskôr diery zapisujeme do predkov, čo trvá \(O(m \log n)\), teda to zanedbáme, potom to celé utriedime a spravíme prefixové súčty – to je výsledná zložitosť.

Samotné odpovede na queries budú trvať \(O(q \log n \log m)\) – pozrieme \(O(\log n)\) predkov a binárne vyhľadáme, ktoré diery sú použiteľné.

Celá časová zložitosť bude \(O(m\log m \log n + q \log n \log m + n \log n)\).

Pamäťová bude \(O(n \log n + m \log n)\), lebo si pamätáme vzdialenosti z vrcholov do centroidových predkov a každú dieru v jej centroidových predkoch.

Postup, ktorý sme si tu ukázali má tú výhodu, že je online – teda otázky spracuváva postupne, každú dostatočne rýchlo. Na precvičenie môžeš skúsiť vymyslieť riešenie na rovnakú úlohu s tým, že vrámci query môže pribudnúť nová diera. Hint – stačí len vhodne upraviť toto riešenie.