4. Odporné psiská, FUJ! vzorové riešenie

4 5
1 0 10
0 2 4
0 3 4
3 1 4
2 1 7

4

2 1
0 1 3

3

Mesto, kde Dog Show Winner býva si vieme reprezentovať ako graf – ulice sú hrany a miesta kde sa ulice spájajú (väčšinou sa im hovorí križovatky) budú vrcholy. Každej hrane potom priradíme váhu – to, koľko ňuchá pes na danej ulici. Keď chceme nájsť odpoveď, musíme nájsť najmenšie číslo \(R\) také, že existuje kostra grafu tvorená hranami, ktorých bitový OR je rovný \(R\).

Nech najväčšia OR všetkých váh hrán na vstupe je \(W\).

Bruteforce

Najviac bruteforce prístup by bol nájsť všetky kostry grafu a z nich vybrať tú s najmenším bitovým _OR_om ich hrán. Časová zložitosť je \(O(v \cdot \binom{e}{v-1})\). Toto riešenie by prešlo iba prvou sadou.

Iný, oveľa lepší bruteforce je skúšať nie všetky kostry, ale všetky výsledky. Nech \(R\) je želaný výsledný OR kostry a k nemu skúsime dorobiť kostru grafu. \(R\) budeme hľadať tak, že postupne budeme prechádzať čísla od 0 po \(W\). Čo potrebujeme skontrolovať je, či existuje kostra grafu s bitovým _OR_om \(R\). To môžeme spraviť tak, že “povyhadzujeme” z grafu všetky hrany, ktoré by nám pokazili želaný výsledok, a teda také, ktorých bitový OR s \(R\) je väčší ako \(R\). Takto vytvorený nový graf môže mať bitový OR najviac \(R\).

V tomto novom grafe sa už nemusíme zaoberať váhami hrán, ale iba ich existenciou. Teda iba potrebujeme skontrolovať, či je náš graf spojitý. To môžeme spraviť pomocou Union-Find alebo DFS (ak sa dostaneme pomocou DFS do každého vrcholu grafu, tak graf je aj napriek vyhodeným hranám súvislý). Keďže prechádzame \(R\) v rastúcom poradí, tak prvé \(R\) na ktoré narazíme je správna odpoveď. Toto riešenie má časovú zložitosť \(O(W \cdot e)\) a pamäťovú zložitosť \(O(e)\).

Upozornime, že riešenie ktoré hrany reálne nevyhadzuje (teda nevytvára nový graf), je aj rýchlejšie aj jednoduchšie na implementáciu. Prekvapivo, aj keď má Union-Find horšiu časovú zložitosť (\(O(e \alpha(e))\)), tak v praxi je na tejto úlohe oveľa rýchlejší než DFS.

Optimálne riešenie

Na predchádzajúcom riešení je časovo dominantný faktor iterovanie \(R\) po \(W\). Musíme nájsť efektívnejší spôsob hľadania \(R\). Vieme, že \(R\) môže byť ľubovoľné číslo od 0 do \(W \approx 2^{31}\). Budeme sa na potenciálne riešenie pozerať po bitoch.

Najskôr zistíme, či môže byť bit s najväčšou váhou nastavený na 0. To zistíme tak, že vyhodíme z grafu všetky hrany, ktoré na tom mieste majú 1. Robíme teda rovnaké riešenie ako bruteforce, ale s \(R=011111...111_2\). Ak náš graf zostal po vyhodení hrán spojitý, tak určite existuje \(R\) také, že má na najvyššej pozícií 0. Naopak, ak graf po vyhodení hrán s 1 na najvyššom mieste prestal byť spojitý, nemôže existovať žiadne \(R\) také, že má na najvyššom mieste 0 (nespojitý graf nemá kostru). Keď sme našli najväčší bit, presunieme sa na ten menší.

Toto riešenie má časovú zložitosť \(O(e \log(W))\). Ale keďže počet bitov môže byť v tejto úlohe najviac 30 a väčšinou sa ako premenná neudáva, môžeme to písať ako \(O(e)\). Pamäťovú zložitosť má toto riešenie \(O(e)\).

Dôkaz

Bitmi musíme prechádzať od najväčšieho po najmenší. Dáva to intuitívne zmysel, keďže chceme najprv prioritizovať bity, ktoré majú väčší dopad na výsledok. Taktiež ľahko vidno, že opačné poradie absolútne nefunguje na grafe, kde existuje kostra s váhami iba \(1\) a druhá s váhami iba \(2\). Na tomto grafe by opačné poradie zahodilo všetky \(1\) hrany a skončilo by s \(R=2\).

Vidno, že opačný postup vôbec nefunguje. Aby sme ukázali, že postup od najväčších po najmenšie bity funguje, musíme ukázať, že ak existuje riešenie, tak ho tento postup nájde a zároveň bude najmenšie možné.

To, že nejaké riešenie nájde, je zrejmé – prinajhoršom prídeme ku \(R=111...111_2\), pri ktorom vieme použiť všetky hrany, a teda určite nájdeme kostru. Prečo bude najmenšie možné? Vyplýva to z toho, že najvyšší bit je dôležitejší než všetky ostatné dokopy. Ak nemusíme použiť najvyšší bit, nikdy sa nám neoplatí ho použiť, keďže \(0111...111_2 < 1000...000_2\).

Výborne, máme riešenie a ukázali sme, že je správne. Ako nás ale mohlo niečo takéto napadnúť? No toto čo robíme je iba binárne vyhľadávanie výsledku. Ale čo je na ňom špeciálne je, že ho musíme robiť opatrne. Štandardne, keď robíme binárne vyhľadávanie výsledku, tak ak riešenie existuje pre nejaké \(R\) tak existuje aj pre všetky \(R' > R\) a podobne ak neexistuje pre \(R\) tak neexistuje ani pre \(R' < R\). V tomto prípade si vieme ľahko predstaviť, že ak existuje riešenie pre \(R = 10010_2\), tak nemusí existovať pre \(R' = 10100_2\) alebo naopak. Ale platí, že ak neexistuje pre \(R\) tak nebude existovať ani pre žiadne \(R'\), ktoré majú iba podmnožinu bitov nastavených na 1. V našom prípade teda zoberieme \(R\) s čo najviac bitmi nastavenými na 1 a ak neexistuje riešenie, tak nemusíme skúšať ani žiadnu podmnožinu. A ak naopak riešenie existuje, tak ako sme spomínali, môžeme sa sústrediť iba na tieto podmnožiny.