5. Éra fanúšika hviezdnych bitiek vzorové riešenie

2
1 1 0 1
300 300
300

600

3
1 2 3 2 1 0 1 3
100 150 50 90
500 400
800

1350

4
1 2 4 1 1 4 0 1 1 1 0 4 3 2 4 0
1 2 4 8 3 4 5 8
4 5 6 7
9 8
15

73

Štandardný pavúk je v informatických pojmoch vlastne úplný binárny strom, čo je taký strom, pre ktorý má každý vrchol okrem listov (tých naspodu) práve dvoch synov. V našom prípade má každý zápas, teda vrchol, cenu, a v listoch (tímy) máme uložené, koľko najviac zápasov si vieme dovoliť vymeškať pre tento tím. Hľadáme teda nejakú množinu vrcholov, ktorá by spĺňala, že pre každý tím (list) je na jeho ceste do koreňa (finále) najviac \(a_i\) nekúpených zápasov.

Bruteforce

Najprv sa pozrime na to, čo sa dalo robiť s druhou sadou, kde sme mali zápasov najviac \(16\). Tu sme vedeli vyskúšať každú kombináciu zápasov a skontrolovať, či nám pokryje tímy tak ako chceme, a potom z tých fungujúcich vybrať tú najlacnejšiu. Na to by sme potrebovali vygenerovať každú kombináciu. To vieme spraviť napríklad tak, že sa pre každý vrchol rozhodneme, či do množiny ktorú kupujeme patrí alebo nie, a teda máme dve možnosti pre \(2^r\) zápasov, teda totálne musíme vyskúšať \(2^{2^r}\) možností. Pre každú možnosť potrebujeme však skontrolovať, či naozaj pokrýva tímy podľa zadania. To vieme spraviť DFSkom v čase \(O(2^r)\), kedy si budeme jednoducho počítať, koľko zápasov sme na ceste od finále k tímu kúpili. Celková časová zložitosť je teda \(O(2^{2^r})\), čo je naozaj pomalé, ale pre túto sadu to stačí.

Zaujímavá myšlienka

Pozrime sa teraz na prvú sadu, kde majú všetky zápasy rovnakú cenu. Určite sa nám teda vždy oplatí pre každý tím kupovať tie zápasy, čo by mohli hrať najneskôr, lebo týmto pokryjeme najväčšie množstvo tímov. Teda ak pre nejaký tím potrebujeme mať kúpený aspoň jeden zápas, tak sa nám určite oplatí kúpiť finále, pretože to stojí rovnako ako iné zápasy a ešte nám to pokryje najviac iných tímov. Teda náš výsledný strom bude vyzerať asi tak, že si pre každý tím necháme prvých \(a_i\) zápasov nekúpených, a potom zvyšné až do finále kúpime. Toto nám pekne pokryje všetky tímy, a vieme tento algoritmus pekne spraviť DFSkom v \(O(r2^r)\), čo úplne stačí.

Niečo všeobecnejšie

(Tu už referujem na zápasy ako na vrcholy) Čo by sme však museli spraviť, ak by sa nám zrazu tie ceny lístkov všelijako pomenili? Povedzme, že sme si už vyplnili strom tak ako v prvej sade, a zmenili sa nám ceny. Ako vieme zistiť, čo sa nám už teraz neoplatí? No a tu prichádzame k zaujímavej myšlienke: Riešenie nie je optimálne, ak kupujeme vrchol A, a v jeho podstrome existujú také nekúpené vrcholy s cenou v súčte menšou ako A, že ak by sme nekúpili A a kúpili tieto vrcholy, riešenie je validné. Hľadáme teda, či nevieme nejaký vrchol jednoducho nahradiť nejakými inými z jeho podstromu, ktoré sú v súčte lacnejšie. Napríklad, namiesto finále by sa nám možno mohlo oplatiť kúpiť oboje semifinále. Ako by sme to mohli spraviť?

Vieme pustiť nejaké DFS z našeho vrcholu A. Pre každý vrchol, ktorý navštívime, sa ho opýtame: nájdi mi, ako najlacnejšie by si mohol pokryť tímy vo svojom podstrome ešte jedným zápasom (to je ten, ktorý odstraňujeme vyššie vo vrchole A). Potom keď obaja synovia pošlú túto hodnotu, máme dve možnosti. Buď je optimálne ten zápas v A v tomto podstrome nahradiť týmto vrcholom, alebo nejakými z jeho podstromov. A tak súčet tých hodnôt od synov porovnáme s cenou vrcholu, v ktorom sme (ak už nie je kúpený). Tú lepšiu cenu pošlem svojmu rodičovi. Potom keď prídem do A, už viem, ako najlacnejšie by bolo možné “nahradiť” to, že odstránime tento vrchol A.

Takže odhora si pre každý aktuálne kúpený vrchol skontrolujem, či ho neviem nejako lacnejšie nahradiť vrcholmi v jeho podstrome. Je dôležité, aby som to robil odhora, pretože takto keď už prejdem tie horné vrcholy mám garantované, že sú v optimálnom stave. Musím si však dať pozor na to, aby som nejaký tím nepokryl viac ako potrebujem. To vyriešim napríklad tak, že v každom vrchole si pamätám, o koľko viac zápasov ako aktuálne potrebuje má nad sebou. Toto vieme tiež updatovať DFSkom po každej iterácii. Kadžé spustené DFS nám potrvá \(O(2^r)\), tak zložitosť celého algoritmu bude \(O({2^r}*{2^r})\). Takéto riešenie by nám stačilo na získanie 6tich bodov, za predpokladu, že v prvej sade robíme algoritmus popísaný vyššie. Čo sa však dá robiť na plný počet bodov? No, zamyslime sa (najťažšia čast príkladu).

Ako to zlepšiť?

Už teraz si v DFSku počítame, ako zlepšiť hodnoty pokrytia pre každý vrchol, tak nevieme pustiť jedno DFSko a spočítať to všetko naraz? DFSko musíme samozrejme upraviť, lebo teraz počíta najlacnejšie ceny pre aktuálny stav toho čo kupujeme, a my by sme ich menili počas toho počítania. Vyriešime to tak, že si pre každý vrchol vyrátame, koľko “navyše” by sme chceli v jeho v podstrome tých pokrytí kúpiť. Respektíve, pýtame sa niečo takéto: Odstránil som \(t\) vrcholov nad tebou, ako najlacnejšie vieš pokryť vo svojom podstrome to, čo hore ubudlo? Toto nám hovorí o všetkých úpravách zároveň.

Na túto otázku viem zodpovedať podobne ako pri prvom DFSku, avšak si proste pre každý vrchol pamätám každú hodnotu, na ktorú sa vrchný vrchol môže pýtať. Všimnime si, že týchto hodnôt môže byť len málo (iba \(r\)), takže ani časová zložitosť nebude taká zlá. V tom našom DFSku si potom pre vrchol prejdeme všetky požiadavky na pokrytie čo môže dostať (teda \(r\) hodnôt), a vyplníme ich najlacnejšie pokrytie pomocou najlacnejších pokrytí takých istých požiadaviek na pokrytie od jeho detí, prípadne zarátame aj seba. Triviálne.

A v tomto momente si možno chytáte hlavu, pretože nechápete o čom to točím, alebo s víziou implementačného pekla a debuggovacej bolesti pred očami. Avšak s 25 riadkami implementácie nás príde zachrániť dynamické programovanie.

Optimálne riešenie

Niektorí ste už možno robili dynamické programovanie na poli. Robili ste ho už na stromoch?

Ešte raz prečítame náš návrh na to nové, upravené DFSko. Parafrázujem: pre každý vrchol chceme vedieť pre každú hodnotu \(x\) od \(0\) do \(r\), ako najlacnejšie viem kúpiť zápasy tak, aby nad týmto vrcholom mohlo chýbať o \(x\) vrcholov viac. Všimnime si, ako nešikovné a ťažko spracovateľné je toto zadefinovanie. Doteraz sme ho používali, lebo viedlo od našej pôvodnej myšlienky kontrolovať každý vrchol zvlášť (teda \(x\) sa vtedy rovnalo 1), avšak to už teraz nechceme robiť. Zadefinujme si teda nový cieľ: Pre každý vrchol chceme vedieť, koľko nás najmenej bude stáť, aby sme ešte mohli na ceste do finále vymeškať \(x\) zápasov.

Takéto zadefinovanie je veľmi šikovné, lebo môžeme pekne prirodzene ísť od listov stromu. Pre každý vrchol si chceme vypočítať pole dĺžky \(r+1\). V \(i\) - tom políčku tohoto poľa (indexované od nuly) bude, koľko najmenej by nás stálo, aby sme mohli vo zvyšných zápasoch odtiaľto až do finále vymeškať ešte \(i\) zápasov. Potom postupujeme takto: Ako vypočítať \(i\) - tú hodnotu v tom poli pre vrchol? Napíšem tu taký dlhý vzorček a potom ho vysvetlím. \(DP[vrchol][i] = min(DP[syn1][i] + DP[syn2][i] + cena[vrchol], DP[syn1][i+1] + DP[syn2][i+1])\)

Poďme si to rozobrať. Na to, aby sme vedeli po tomto vrchole vymeškať \(i\) ďalších, môžeme buď zaplatiť: - Zobrať najlacnejší spôsob ako môžem vymeškať ešte \(i\) zápasov od mojich synov, a kúpiť samého seba. (\(DP[syn1][i] + DP[syn2][i] + cena[vrchol]\)) - Zobrať najlacnejší spôsob ako môžem vymeškať ešte \(i+1\) zápasov od mojich synov, a vymeškať samého seba (\(DP[syn1][i+1] + DP[syn2][i+1]\))

Vždy si vezmem lepšie riešenie z týchto dvoch, a to bude tým najlepším riešením. Takto viem ísť pekne od listov po kolách hore, alebo aj DFSkom. To je však náročnejšie. No a aká by bola časová zložitosť? V každom vrchole musíme zbehnúť ten vzorček napísaný vyššie pre každé \(i\). Teda to bude jednoducho \(O(r*{2^r})\), a toto nám teda zbehne vo všetkých sadách.