Úloha 4.u2: Hřebenovka (3 b)

Zadáno v čísle 23.4.

Řešeno v čísle 23.6.

Zadání

Na celé cestě je $N$ bodů tak, že mezi každými dvěma sousedními body cesta buď o jeden metr klesne, nebo o jeden metr stoupne. Cestovatele vždy zajímá, jaký je nejvyšší bod na nějakém úseku cesty, neboť z něj bude nejhezčí výhled. Na dotaz „Jaký je nejvyšší bod na cestě mezi body $a$$b$?“ tedy jako odpověď očekává bod $c$, který leží mezi body $a$$b$ (včetně) a zároveň má největší možnou nadmořskou výšku (viz Obrázek 1).

Vaším cílem je navrhnout co nejefektivnější algoritmus, který pro danou cestu (zadanou jako posloupnost nadmořských výšek bodů na ní tak, jak jdou za sebou) bude odpovídat na dotazy. Dotazy samozřejmě neznáte předem, ale můžete předpokládat, že počet dotazů $K$ je řádově větší než $N$ – počet bodů na cestě.

Obrázek 1: Příklad hřebenovky s 16 body, nad každým bodem je jeho nadmořská výška. Pro dotaz na kus cesty mezi body $a$$b$ by správnou odpovědí byl bod $c$ s výškou 8. Pro dotaz na cestu mezi $a$$b^\prime $ můžeme odpovědět buď opět bodem $c$, nebo bodem $b’$, jelikož oba mají stejnou výšku.

Řešení

Nejdříve nějaké značení. Body na cestě si označíme čísly od 1 do $N$ tak, jak jdou za sebou, a výšku bodu $i$ si označíme $v_ i$. Úsek cesty mezi body $i$$j$ (včetně) budeme značit $[i,\, j]$.

Začněme s tím nejjednodušším řešením – pro každý dotaz si prostě spočítáme maximum výšek. Spočítat maximum z $L$ bodů snadno zvládneme v $\mathcal{O}(L)$, jeden dotaz nám tedy zabere nejhůře $\mathcal{O}(N)$. Zodpovědět všechny dotazy nám tudíž bude trvat $\mathcal{O}(KN)$. Ač toto řešení na první pohled možná nevypadá tak špatně, dokážeme ho ještě zlepšit.

Nabízí se dva přístupy ke zlepšení naivního algoritmu. První je si nad cestou vybudovat nějakou datovou strukturu, která nám hledání maxima zrychlí. Druhý spočívá v tom, že když už při zodpovídání dotazu něco spočítáme, tak si to uložíme, abychom si usnadnili práci při zodpovídání dalších dotazů. Zajímavé je, že v obou případech dojdeme v podstatě k totožnému algoritmu jen s tím rozdílem, že v prvním případě všechnu práci oddřeme v předvýpočtu, zatímco v druhém případě se tatáž práce rozprostře do dotazů. Proto se vydáme jen prvním směrem, neboť ten je snazší na analýzu.

Pojďme tedy nad naší cestou vybudovat nějakou datovou strukturu, která nám zrychlí dotazy. Mnoho řešení navrhovalo použít intervalový strom. Intervalové stromy jsou mocnou datovou strukturou, která je určena pro zodpovídání intervalových dotazů (jako třeba „Jaký je součet čísel v daném intervalu?“)1, na první pohled tedy vypadá jako ideální kandidát. Intervalový strom pro hledání maxima lze zkonstruovat v čase $\mathcal{O}(N)$ a potřebuje čas $\mathcal{O}(\log N)$ na dotaz, tedy celkem bychom dosáhli složitosti $\mathcal{O}(N + K\log N)$.

Bohužel, pro naše účely je intervalový strom až příliš silná zbraň (například proto, že podporuje změny posloupnosti, nad níž je vybudován, což je pro naše potřeby zbytečné) a vystačíme si s mnohem jednodušší a efektivnější strukturou. Stačí si všimnout, že různých dotazů je jen $N(N-1)/2 \le N^2$. Můžeme si tedy předpočítat tabulku $N\times N$, která bude obsahovat odpověď pro každý možný dotaz. Na dotaz tak dokážeme odpovědět v čase $\mathcal{O}(1)$ – což je optimální! Tabulku dokážeme spočítat v čase $\mathcal{O}(N^2)$ – maximum z $[i,\, i]$ je $v_ i$ a maximum z $[i,\, j]$ je buď $v_ j$ nebo maximum z $[i,\, j-1]$. Celkem máme tedy složitost $\mathcal{O}(N^2 + K)$. To je čas, za který jste mohli získat plný počet bodů.

Můžeme algoritmus ještě zlepšit? Čas na dotaz už máme minimální, zkusme tedy nějak zlepšit předvýpočet. Všimněme si, že vlastně nepotřebujeme mít předpočítanou odpověď pro každý úsek – stačily by jen takové, ze kterých dokážeme v konstantním čase poskládat odpověď pro ostatní úseky. Předpočítáme si proto jen úseky, jejichž délky jsou mocninou dvojky – tedy pro každé $i\in \{ 1, 2, \dots , N\} $ a $k\in \{ 0, 1, \dots , \log N\} $ si předpočítáme maximum z úseku $[i,\, i + 2^ k]$. Jelikož maximum z $[i,\, i + 2^{k}]$ dokážeme v $\mathcal{O}(1)$ spočítat z maxima pro $[i,\, i + 2^{k-1}]$ a pro $[i + 2^{k-1} + 1,\, i + 2^ k]$, předvýpočet nám zabere čas $\mathcal{O}(N\log N)$. Dotaz na $[i,\, j]$ zodpovíme tak, že najdeme největší $k$ takové, že $j - i \ge k$ (buď pomocí bitových triků, nebo si prostě pro všech $N$ možných hodnot $j - i$ předpočítáme správné $k$), a vrátíme větší z maxim pro úseky $[i,\, i + 2^ k]$ a $[j - 2^ k,\, j]$.

Tím jsme se dostali na čas $\mathcal{O}(N\log N)$ na předvýpočet a $\mathcal{O}(1)$ na dotaz. Nicméně, předvýpočet lze stihnout v lineárním čase! K tomu použijeme následující trik: Cestu si rozdělíme na $N/B$ bloků o $B$ prvcích (pro vhodně zvolené $B$). Nad každým blokem si postavíme mikrostrukturu, která bude umět odpovídat na dotazy ohledně zadaného bloku. Následně si celou cestu „zahustíme“ – každý blok nahradíme jeho maximem, čímž dostaneme cestu délky $N/B$. Nad takto zahuštěnou cestou si postavíme makrostrukturu, která bude umět odpovídat na dotazy ohledně zahuštěné cesty. Každý dotaz na původní cestu pak můžeme rozdělit na jeden dotaz na makrostrukturu a nejvýše dva dotazy na mikrostruktury, viz Obrázku 2.

Obrázek 2: Ukázka dekompozice na mikro- a makrostrukturu. Cesta je rozdělena na čtyři bloky a nad každým vybudujeme mikrostrukturu. Nad maximy bloků (zakroužkované body) vybudujeme makrostrukturu. Každý dotaz na celou cestu pak můžeme rozložit na nejvýše jeden dotaz do makrostruktury a nejvýše dva dotazy do mikrostruktur.

Pro mikrostruktury použijeme naši předchozí konstrukci s kvadratickým předvýpočtem, pro makrostrukturu naopak použijeme konstrukci s $\mathcal{O}(N\log N)$. Velikost bloku $B$ si zvolíme jako $1/2\log N$. Dotazy tedy jistě zvládneme zodpovědět v konstantním čase, ale co předvýpočet? Konstrukce makrostruktury nám zabere čas $\mathcal{O}\left({N\over B} \log \left({N\over B}\right)\right)$. Nyní

\[ {N\over B} \log \left({N\over B}\right) = \left({N\over {1\over 2} \log N} \right) \log \left({N\over {1\over 2} \log N }\right) = \]\[ = \left({2N \over \log N} \right) \log \left({2N \over \log N} \right) = {2N \over \log N} \cdot \left(\log N + \log 2 -\log \log N\right) \]\[ \mathcal{O}\left({2N \over \log N} \cdot \left( \log N + \log 2 - \log \log N\right)\right) = \mathcal{O}\left({N\over \log N} \log N\right) = \mathcal{O}(N), \]

ale konstrukce všech mikrostruktur nám zabere čas

\[ \mathcal{O}\left({N\over B}\cdot B^2\right) = \mathcal{O}(N\log N). \]

Vypadá to tedy, že jsme si moc nepomohli. Teď ale přijde druhý trik – konečně využijeme toho, že naše cesta vždy buď o metr klesne nebo stoupne. Takových cest je totiž málo. Nejdříve si všimněme, že pokud se dvě cesty liší jen tím, v jaké výšce začínají, a posloupnost klesání a stoupání mají stejnou, pak mají maximum ve stejném bodě. Můžeme tedy předpokládat, že všechny cesty odpovídající blokům začínají ve výšce nula – z polohy maxima na cestě už snadno vyčteme jeho hodnotu. A kolik je tedy různých cest délky $B$ začínáních v nule? Inu, v každém bodě cesty (krom posledního) máme jen dvě možnosti – buď cesta o metr stoupne, nebo o metr klesne. Takových cest je tedy jen $2^{B-1} \le 2^ B$.

Pro námi zvolené $B = 1/2\log N$ je různých cestiček délky $B$ nejvýše $2^{1/2\log N} = \sqrt {N}$. Vůbec tedy nemusíme počítat pro každý blok zvlášť jeho mikrostrukturu. Místo toho si spočítáme $\sqrt {N}$ mikrostruktur pro každou možnou cestičku délky $B$ a každý blok si jen bude pamatovat ukazatel na mikrostrukturu, která odpovídá cestičce, kterou blok reprezentuje. Na předvýpočet mikrostruktur nám bude tedy stačit jen čas $\mathcal{O}(\log ^2 N\sqrt {N}) \subseteq \mathcal{O}(N)$. Máme tedy lineární čas na předvýpočet a konstantní čas na dotaz.

Mimochodem, kdybychom na cestě povolili libovolně velká stoupání a klesání, tak dokážeme také odpovídat na dotazy v konstantním čase a mít předvýpočet v lineárním čase. To je ale o poznání komplikovanější konstrukce – hledání maxima na obecné cestě se nejdříve převede na problém hledání stromových předchůdců, který se pak převede zpět na hledání maxima na cestě, ale tentokrát už s klesáním nebo stoupáním jeden metr. Podrobněji se o tom můžete dočíst ve skriptíčkách Krajinou grafových algoritmů2.

$\mathcal{O}(N)$dra


1) Více se o intervalových stromech můžete dozvědět např. zde: http://ksp.mff.cuni.cz/kucharky/intervalove-stromy/

2) http://mj.ucw.cz/vyuka/ga/, kapitola 9