7. Jedenie v polceste vzorové riešenie

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

1
3

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

3
1 7 5

Táto úloha sa vlastne skladá z dvoch separátnych úloh:

• Pre každú túru potrebujeme zistiť, na ktorých miestach sa pre ňu môže nachádzať obed
• Následne musíme vybrať, na ktorých miestach sa obedy budú servírovať

Všimnite si, že ak máme len túry nepárnej dĺžky, druhý problém máme vyriešený automaticky – nemáme na výber. Zamerajme sa teda na prípad, že máme aj túry párnej dĺžky.

Druhá časť

Poďme sa najskôr pozrieť na druhú časť úlohy. Ako sme si už povedali, pre túry nepárnej dĺžky je problém vyriešený. Povedzme, že tieto obedové miesta sú povinné vrcholy. Zoberme si teda túry nepárnej dĺžky. Povedzme, že vrchol pokrýva túru, ak by sa na ňom mohol servírovať obed pre túto túru. Povedzme, že množina vrcholov je pokrývajúca ak je každá túra pokrytá nejakým vrcholom.

Všimnime si, že ak nejakú túru pokrýva povinný vrchol, tak na ňu môžeme zabudnúť. Takto nám ostanú iba túry párnej dĺžky nepokryté povinnými vrcholmi a úloha sa zúži na to, nájsť najmenšiu pokrývajúcu množinu pre tieto túry.

Ďalej sa pozrime na to, čo sú to za dvojice vrcholov na ktorých môže byť servírovaný obed pre nejakú túru nepárnej dĺžky. Konkrétne, tieto vrcholy sú dva stredné vrcholy na ceste. Čiže musia byť spojené hranou. Teda sa úloha zúži na to, že máme podmnožinu hrán stromu, a chceme vybrať čo najmenšie množstvo vrcholov tak, aby každá z “obedových hrán” mala aspoň jeden koniec v množine.

Všimnime si, že hrany, ktoré nie sú v strede nejakej nepokrytej párnej túry nás nezaujímajú. Takže ich môžeme vyhodiť zo stromu. Strom sa nám takto rozpadne na viacero podstromov – to voláme les. Každý z týchto podstromov môžeme riešiť separátne.

Napríklad na dolnom obrázku máme strom s \(10\) vrcholmi, v ktorom chceme pokryť \(6\) hrán. Strom sa nám tak rozpadne na dva podstromy s aspoň jednou hranou (a dva izolované vrcholy).

Nová úloha

Dostali sme teda nasledovnú novú úlohu: máme zadaný strom a chceme vybrať najmenšiu pokrývajúcu množinu vrcholov (takú, že každá hrana bude mať aspoň jeden pokrytý koniec).

Pokiaľ strom nemá žiadnu, alebo najviac jednu hranu, riešenie je jednoduché: zoberieme prázdnu množinu (ak tam nie je žiadna hrana), alebo ľubovoľný vrchol (ak je hrana presne jedna). Čo robiť, ak je strom väčší?

Samozrejme, dá sa to riešiť v exponciálnom čase skúšaním všetkých možností¹, našťastie, ide to aj oveľa rýchlejšie a jednoduchšie, a to: pažravo.

Prvé pozorovanie

Predstavme si, že strom tvoria aspoň dve hrany. Vtedy vieme spraviť nasledovné pozorovanie: vždy existuje pokrývajúca množina optimálnej veľkosti, ktorá neobsahuje žiadny list (listy sú vrcholy z ktorých ide jediná hrana).

Prečo to platí? Zoberme si ľubovoľnú pokrývajúcu množinu minimálnej veľkosti a predstavme si, že sa v nej nachádza nejaký list. Tento list pokrýva jedinú hranu (keďže listy majú len jedného suseda). Ak vyberieme list z množiny a nahradíme ho jeho susedom, tak táto hrana bude stále pokrytá a množinu nezväčšíme (keďže odstránime jeden vrchol a pridáme jeden vrchol).

Pokiaľ sú v strome aspoň dve hrany, list nikdy nesusedí s iným listom (schválne, skúste si to). Takže sme teda dostali množinu minimálnej veľkosti neobsahujúcu žiadne listy.

Pažravé riešenie

Na základe tohto pozorovania získame jednoduchý algoritmus: pokiaľ má strom najviac jednu hranu, skončili sme. Inak pridáme do riešenia najskôr všetkých susedov listov (keďže hrany do listov musia byť pokryté a existuje optimálne riešenie bez listov). Vyhodíme všetky hrany, ktoré sme takto pokryli a dostaneme menší les (alebo menší strom). Spustíme algoritmus na každý zo zostávajúcich menších stromov.

Výsledné riešenie musí byť optimálne, keďže akonáhle neberieme listy (a vieme, že to môžeme urobiť), tak sú naše zvyšné voľby vynútené. Na obrázku dole môžeme vidieť dve iterácie tohto procesu.

Toto by sme mohli implementovať naivne, v kvadratickom čase. Ale stačí krátke zamyslenie, a zistíme, že nám v skutočnosti stačí jedno prehľadávanie do hĺbky. Pre každý vrchol si vrátime, či patrí do množiny. Ako toto vyhodnotíme? Ak sme v liste, povieme nie. Ak sme v nie-liste odpovieme áno, len ak musíme (máme nepokryté dieťa). Môžete si rozmyslieť, prečo to funguje.

S trochou zamyslenia takto vieme vyriešiť všetky podstromy, ktoré nám vznikli z prvej časti úlohy naraz, jedným prehľadávaním, a zaberie nám to lineárny čas.

Prvá časť: ako nájsť stredy?

Tak sme si vyriešili druhú časť úlohy a už nám ostáva len zistiť, ktoré hrany alebo vrcholy sú to v strede ciest.

Táto časť úlohy zahŕňa dva podproblémy: chceme zistiť: ako ďaleko je od seba dvojica vrcholov, a ktorý vrchol je následne v polceste.

Mohli by sme to, samozrejme, riešiť naivne, v lineárnom čase na otázku, a získať takto 4 body.

Vo vzorovom riešení vieme tieto otázky riešiť v \(O(\log n)\) čase na otázku (s \(O(n\log n)\) predpočítaním). Použijeme na to dátovú štruktúru zvanú najbližší spoločný predok (inak známy ako LCA). Predstavme si, že si zakoreníme strom (vyberieme si jeden vrchol ako koreň a strom si naň zavesíme). Predkovia vrchola sú vrcholy na ceste z neho do koreňa. Všimnime si, že pri každej ceste medzi dvoma vrcholmi ideme najskôr hore do najbližšieho spoločného predka a potom dole. Takže na zistenie cesty chceme vedieť, ktorý je ten najbližší spoločný predok. A stred, resp. stredy cesty vieme zistiť tak, že z jedného z vrcholov ideme o pol-dĺžku cesty hore.

Ako toto zistíme rýchlo? V skratke (ak si to chcete prečítať detailnejšie, návod je v kuchárke) si pre každý vrchol zistíme, aký vrchol je jeho priamy predok, vrchol o dva vyššie, o štyri vyššie, o osem vyššie (až tak ďalej, \(O(\log n)\) informácií). Najbližšieho spoločného predka vieme binárne vyhľadávať v \(O(\log n)\) čase (ak je \(i\)-ty predok rovnaký, potom aj \((i+1)\)-ty bude rovnaký). A vrchol ktorý je o \(l\) levelov vyššie vieme získať tak, že sa na číslo \(l\) pozrieme v binárke a správne vystaváme skoky.

Celé riešenie má dokopy časovú zložitosť \(O((n+m)\log n)\), a pamäťovú zložitosť \(O(n\log n)\), pričom si všimnime, že druhá časť úlohy nám zložitosť nemení.