4. Slizká pochúťka vzorové riešenie

8 4
4 7
1 1
3 5
6 7

1 0 1 1 1 1 1 0

V tejto úlohe sme dostali \(q\) úsekov dážďovky, ktoré máme natrieť omáčkou. Mali sme určiť, ako bude dážďovka vyzerať na konci. Chceli sme teda pre každé políčko dážďovky zistiť, či bude, alebo nebude natreté.

Hrubá sila

Spraviť bruteforce na túto úlohu je pomerne priamočiare. Majme pole dĺžky \(n\) so samými nulami. Nazvime ho d[] a bude reprezentovať, neprekvapivo, dážďovku. Hodnota \(0\) predstavuje nenatreté políčko, hodnota \(1\) bude predstavovať natreté políčko.

Pre každý úsek \([a, b]\) zo vstupu prejdeme všetky políčka v poli d[] od \(a\)-teho po \(b\)-te políčko a na každé z nich nastavíme hodnotu \(1\). To bude znamenať, že je natreté. Na konci nám teda stačí iba vypísať obsah poľa d[].

Každý úsek na vstupe môže mať dĺžku najviac \(n\). Úsekov je \(q\), takže časová zložitosť tohto riešenia je \(O(nq)\). Pamätáme si iba dážďovku, takže pamäťová zložitosť je \(O(n)\).

Lepšie riešenie

Prečo je riešenie hrubou silou také pomalé? Lebo sa veľakrát pozerá na tie isté políčka dážďovky. Možno by sa dalo spraviť to, že dva prekrývajúce sa úseky spojíme do jedného, dlhšieho. Ak takto úseky pospájame, ostanú nám na konci iba neprekrývajúce sa úseky. To znamená, že súčet dĺžok všetkých týchto úsekov bude nanajvýš \(n\).

Ako to ale spraviť efektívne? Povedzme si, že chceme ísť po dážďovke zľava doprava a nikdy sa nechceme vracať na políčka, ktoré sme už prešli. Načítajme si teda najskôr všetky úseky a usporiadajme si ich podľa začiatku. To znamená, že úsek, ktorý začína viac vľavo spracujeme skôr ako ten, ktorý začína viac vpravo. Rovnako ako v riešení hrubou silou, majme pole d[] veľkosti \(n\) so samými nulami.

Zoberme prvý úsek, nazvime ho A, a prejdime všetky políčka dážďovky, ktoré reprezentuje. Každému z týchto políčok v poli d[] nastavíme hodnotu \(1\). Nastavenie hodnoty \(1\) v poli d[] budeme odteraz nazývať natretím políčka dážďovky.

Pozrime sa na druhý úsek v usporiadanom poradí a nazvime ho B. Vieme, že B určite nezačína skôr, ako A, lebo sme ich usporiadali podľa začiatkov. Nastať teda mohol iba jeden z nasledovných prípadov:

1. B je podúsekom A, teda B začína aj končí skôr ako A
2. B začína v A a končí neskôr, ako A
3. B začína neskôr, ako A končí

V prvom prípade môžeme úsek B odignorovať, lebo všetky políčka, ktoré tento úsek zasahuje boli už natreté úsekom A.

V druhom prípade niektoré políčka zo začiatku úseku B už boli natreté úsekom A. Pri natieraní teda stačí pokračovať od konca úseku A až po koniec B.

No a v treťom prípade môžeme natrieť celý úsek B, lebo vieme, že žiadne z jeho políčok doteraz neboli natreté.

Môžeme si všimnúť, že nikdy nepotrebujeme vedieť, kedy začínal naposledy spracovaný úsek. Jediné, čo nás zaujíma je to, ktoré políčko dážďovky sme natreli ako posledné. Stačí nám teda mať jednu premennú, ktorá bude hovoriť, ktoré natreté políčko dážďovky sa nachádza najviac vpravo. Ak teda spracujeme úsek, ktorý končil ďalej, ako bola hodnota tejto premennej v čase jeho spracovania, tak túto premennú nastavíme na koniec tohto úseku.

Máme teda algoritmus, ktorý sa na každé z \(n\) políčok dážďovky pozrie najviac raz. Z toho vyplýva časová zložitosť \(O(n)\). Pozor ale na to, čo robíme s úsekmi. Usporiadavame ich, čo trvá čas \(O(q \log q)\). Naše riešenie má teda zložitosť \(O(n + q \log q)\). Pamäťová zložitosť je \(O(n + q)\), pretože si pamätáme všetky úseky a celú dážďovku.

Všimnime si, že začiatku a konce zadaných úsekov sú z rozsahu od \(1\) po \(n\). Pri triedení čísel s takýmto obmedzením vieme využiť aj rýchlejšie triedenia, napríklad countsort, ktorého zložitosť je \(O(q + n)\). Tým zlepšíme aj celkovú časovú zložitosť na \(O(n + q)\). Ako si však ukážeme o chvíľu, túto zložitosť vieme dosiahnuť aj bez toho, aby sme poznali niektorý z týchto špeciálnych triediacich algoritmov.

Vzorové riešenie

Optimálnu časovú zložitosť sme už síce získali drobným trikom v predchádzajúcom riešení, no poďme sa pozrieť na krajšie a jednoduchšie riešenie, ktoré má dokonca lepšiu pamäťovú zložitosť.

Opäť budeme mať pole dĺžky \(n\), nazvime ho p[]. Tentokrát ale \(i\)-te políčko tohto poľa bude hovoriť, koľko úsekov na tomto políčku začína alebo končí. To znamená, že ak spracúvame úsek [a, b], tak k p[a] pripočítame \(1\) a k p[b + 1] pripočítame \(-1\). Kladné číslo označuje začiatok a záporné koniec. Naviac si všimnite, že koniec je v skutočnosti až jedno políčko za reálnych koncom a to preto, aby sme sme aj toto posledné políčko započítali do zadaného úseku.

Čo teraz môžeme robiť s týmto poľom? Môžeme pre každé políčko zistiť, koľko úsekov ho prekrýva. Majme počítadlo, ktoré hovorí, koľkými úsekmi je prekryté aktuálne políčko. Na začiatku bude mať počítadlo hodnotu \(0\). Teraz prejdime cez všetky políčka poľa p[] zľava doprava. Keď spracúvame \(i\)-te políčko, tak k nášmu počítadlu pripočítame hodnotu p[i]. Ak totiž na \(i\)-tom políčku začínajú nejaké úseky, tak ich počet chceme pripočítať k počítadlu. Ak nejaké úseky končili na políčku \(i-1\), tak ich teraz chceme od počítadla odpočítať.

Navyše, naše pole p[] bez problémov zvláda aj viaceré úseky začínajúce alebo končiace na tom istom políčku. Ak napríklad na pozícii \(a\) začínajú tri rôzne úseky, tak hodnotu p[a] sme zvýšili o 1 trikrát, preto je tam hodnota \(3\). A ak na políčku \(a\) začína úsek a zároveň na políčku \(a-1\) nejaký skončil, tak hodnota p[a] bude rovná 0. To je však v poriadku, pretože 0 znamená, že sa nič nemení.

No a tu už vidíme riešenie. Budeme prechádzať pole p[] a aktualizovať počítadlo úsekov. Ak po aktualizácii počítadla políčkom p[i] bude počítadlo väčšie, ako \(0\), tak vieme, že \(i\)-te políčko je natreté. Ak je počítadlo \(0\), tak je \(i\)-te políčko nenatreté, lebo ho neprekrýva žiaden úsek. Počítadlo určite nikdy nebude menšie, ako \(0\), pretože ak je niekde v poli p[] hodnota \(-1\), tak niekde skôr musí byť jej zodpovedajúca \(+1\).

Pre každý úsek zapíšeme iba dve hodnoty do poľa p[] a toto pole následne raz prejdeme. Výsledná časová zložitosť je teda \(O(q + n)\). Pamätáme si však už len pole p[] (a jednu premennú na počítadlo), preto je pamäťová zložitosť \(O(n)\).

Iné riešenia

Riešení tejto úlohy existuje viac a nespomenieme tu všetky. Za zmienku ale stojí riešenie s neoptimálnou časovou zložitosťou \(O(q \log n)\). Toto riešenie vie natrieť celý úsek v čase \(O(\log n)\). To je veľmi jednoduché, ak na reprezentáciu dážďovky použijeme vhodnú dátovú štruktúru. Najjednoduchšou z možností je asi použiť intervalový strom s lazy propagáciou. Táto dátová štruktúra má široké uplatnenie a ak ju nepoznáte, určite si o nej niečo prečítajte. Keď si o nej už niečo prečítate, vymyslieť toto riešenie bude triviálne a nechávame ho ako cvičenie pre vás.