7. Istota čistoty vzorové riešenie

3 3
1 1 10 10
2 2 9 9
4 4 6 8
2 10 1
2 9 2
5 7 3

3
2
1

Riešenie hrubou silou je jednoduché. Pre každý koberec môžeme mať set a farbu každej lentilky vložíme do setu každého koberca, na ktorom sa nachádza. Dostaneme riešenie s časovou zložitosťou \(O(nm \log m)\). Ak namiesto setu použijeme hešovaciu tabuľku, tak to zlepšíme na \(O(nm)\). Pamäť bude \(O(n + m)\), ak si zapamätáme iba koberce, lentilky a sety.

Vzorové riešenie

Predstavme si, že by vždy ležal menší koberec na väčšom. Uvedomme si, že toto nijak nezmení odpoveď, pretože farba z lentilky presiakne cez všetky koberce pod ňou bez ohľadu na ich poradie. Môžeme teda predpokladať, že koberce skutočne ležia týmto spôsobom.

Keďže sa koberce nepretínajú stranami, tak nám vzniklo niekoľko kôpok kobercov. Každá z týchto kôpok je v podstate strom. Jeho koreňom je spodný, najväčší koberec.

Poďme si rozmyslieť, ako spraviť, aby sme každú lentilku nemuseli zapisovať do každého koberca, ktorý ofarbí, ale iba do jedného. Zapíšeme ju iba do najvrchnejšieho. To nám stačí, pretože pod ním sú už iba väčšie koberce. Keď zapíšeme všetky lentilky, tak nám bude stačit prejsť každý strom a každému vrcholu, čiže kobercu, priradiť farby tak, že zjednotíme farby všetkých jeho synov. Potlačíme teda farby z listov, kam sme ich zapísali, dohora.

Vieme to spraviť rýchlo? Pre každý koberec môžeme mať set, do ktorého budeme dávať jeho farby. Keby sme do otca vkladali farby zo synov len tak ledajako, mohlo by sa nám stať, že budeme jednu farbu kopírovať príliš veľa krát. Použijeme teda trik používaný napríklad v dátovej štruktúre union-find, kde spájame dve množiny tak, že kopírujeme prvky z menšej tabuľky do väčšej. Predstavme si spájanie jedného zo synov s otcom. Ak je viac farieb v otcovi, prekopírujeme farby zo syna do otca. Ak je viac farieb v synovi, prekopírujeme farby z otcovského setu do synovho a prehlásime ho za nový otcov set. Takto bude každá lentilka prekopírovaná nanajvýš \(\log m\)-krát. Na tomto mieste sa vieme zbaviť jedného logaritmu tým, že namiesto setu použijeme hešovaciu tabuľku. Táto časť teda bude mať zložitosť \(O(m \log m)\).

Ostáva nám vyriešiť iba to, ako zapísať každú lentilku iba do najvrchnejšieho koberca. Toto je celkom známa úloha. Budeme mať intervalový strom. Z obdĺžnikov zoberieme začiatočnú a konečnú zvslú úsečku a o každej si zapamätáme, či je začiatočná, alebo konečná. Tieto úsečky si usporiadame podľa \(x\)-ovej súradnice spolu s lentilkami. Usporiadané úsečky pozametáme intervaláčom. Vždy, keď nájdeme začiatočnú úsečku, v intervalovom strome si zapamätáme že daný obdĺžnik je na celom intervale, ktorý pokrýva daná úsečka aktuálne najvyššie. Ináč povedané, na intervale danej úsečky pridáme na stack korešpondujúci obdĺžnik. Keď dojdeme ku koncu obdĺžnika, odoberieme daný obdĺžnik zo stacku na celom intervale tejto koncovej úsečky. Keď nájdeme lentilku, pozrieme sa do intervalového stromu, ktorý obdĺžnik je najvyššie na danom mieste a lentilku do neho zapíšeme. Keďže súradnice sú veľké, budeme pre intervalový strom potrebovať spraviť kompresiu súradníc, alebo ho stavať dynamicky. Táto časť bude mať zložitosť \(O((n + m) \log (n + m))\), čo bude aj výsledná časová zložitosť programu. Pamäťová zložitosť bude \(O(n + m)\).