Pozorovanie

Ako prvé si vieme všimnúť, že sa nám nikdy neoplatí navštíviť vrch (resp. spodok) nejakej priehradky dvakrát.

Dole sa robot musí presunúť práve raz, a preto vo všeobecnosti optimálny pohyb bude vyzerať nasledovne:

1. Robot sa presunie (pohybmi doprava alebo doľava) na vrch nejakej priehradky (resp. ostane tam, kde sme začínali)

2. Robot prejde na spodok priehradky

3. Robot prejde (pohybmi doprava alebo doľava) na spodok cieľovej priehradky (resp. ostane na mieste, ak tam už po druhom kroku je)

Navyše pohyb v prvom a treťom kroku bude zjavne iba doprava, alebo iba doľava (inak by robot navštívil vrch, resp. spodok nejakej priehradky dvakrát). Otázka je teda, ako vybrať priehradku, v ktorej robot vykoná pohyb dole.

Bruteforce

Keď je $n$ malé vieme použiť hrubú silu, a vyskúšať všetky možnosti, kde by mohol robot ísť dole.

Ak by sme sa chceli dostať z vrchu priehradky číslo $x$ na spodok priehradky číslo $x’$ tak, že robot prejde dole na pozícii $i$, bude to trvať čas za ktorý sa dostame z $x$ na $i$ (teda $\min(|x-i|, n-|x-i|)$) plus čas na prejdenie dole priehradkou $i$ (čiže $a_i$), plus čas na dostanie sa z vrchu priehradky $i$ na vrch priehradky $x’$.

V čase $O(n)$ na otázku vieme prejsť všetky možnosti a vybrať minimum. Časová zložitosť tohoto riešenia je preto $O(nq)$ – všimnite si, že aj keď vieme udalosti typu ! simulovať v konštantnom čase, v najhoršom prípade nám každá otázka zaberie lineárne dlho.

Pamäťová zložitosť je $O(n)$, pamätáme si iba vstup v poli, ktorý postupne meníme.

Špeciálny prípad – $|x-x’|=n/2$

Predstavme si teraz, že pre každú udalosť typu ? platí $|x-x’| = n/2$.

Vieme si všimnúť, že nech vyberieme akékoľvek číslo priehradky $i$ v ktorej robot vykoná pohyb dole, tak v horizontálnom smere vždy prejdeme iba vzdialenosť $n/2$.

Tým pádom je optimálne riešenie vybrať $i$ tak, aby sme minimalizovali $a_{i}$, takže vždy vyberieme najmenšie $a_{i}$, to vieme robiť rýchlo aj so zmenami použitím obyčajného intervalového stromu alebo haldy.

Časová zložitosť daného riešenia je $O(n+ q \log n)$.

Optimálne riešenie

Ako sme si už všimli, optimálne riešenie vždy vieme rozložiť na 3 typy pohybov:

• Pohyb po vrchoch priehradiek v jednom smere.

• Pohyb dole.

• Pohyb po spodkoch priehradiek v jednom smere.

Pozrime sa na to podrobnejšie. V prvom a druhom kroku máme dve možnosti: ísť doprava, alebo doľava. Takto máme štyri typy ciest, ktorými vie robot ísť: doľava-dole-doľava, doľava-dole-doprava, doprava-dole-doľava, a doprava-dole-doprava.

Následne si ešte rozdelíme prípady podľa toho, či $x < x’$, alebo $x\geq x’$.

Pozrime sa na prípad, že náš pohyb je doprava-dole-doprava. Podľa relatívneho poradia $x$ a $x’$:

Prípad doprava-dole-doprava

Pozorný čitateľ si môže všimnúť, že sme zdanlivo vynechali dva prípady: vo vrchnom obrázku by sa $i$ mohlo nachádzať za $x’$ (teda by sme cestou doľava prešli okolo $x’$). Avšak vtedy by sme horizontálne prešli vyše $n$ priehradiek. V tomto prípade sa však cesta ku $i$ dá zrýchliť, ak by sme išli iba doľava, viď obrázok:

Prípad doprava-dole-doprava-ale-zle

Takže máme dva prípady. Pozrime sa najskôr na prípad, kde $x < x’$, a dole prejdeme na priehradke číslo $x\leq i\leq x’$. Koľko to bude trvať? $a_i + (i - x) + (x’ - i) = x’ - x + a_i$. Takže na nájdenie najlepšieho indexu $i$ pre tento prípad nám stačí použiť intervalový strom na nájdenie $x\leq i\leq x’$ s najmenším možným $i$.

Čo sa stane ak $x\geq x’$. Rovnakým počítaním si môžme všimnúť, že sa nám oplatí jednoducho nájsť $i$ s najmenším $a_i$ pre ktoré buď platí $i\leq x’$ alebo $i\geq x$). Toto tiež vieme spraviť pomocou intervalového stromu.

Prípad doľava-dole-doľava, je v princípe identický, takže zostávajúce dva zaujímavé prípady sú doľava-dole-doprava a doprava-dole-doprava.

Ďalej sa pozrime na prípad doprava-dole-doľava. V tomto prípade máme štyri možnosti¹, ako môžeme uvidieť na nasledujúcom obrázku:

Prípad doprava-dole-doľava

Aby sme sa vyhli ďalšej analýze prípadov (prechod cez $n$), všimnime si, že ak máme pole veľkosti $2n$, kde $a_i = a_{n+i}$, vtedy si môžme predstaviť, že namiesto $i<x$ (pri ktorom by sme museli prejsť cez $n$) prechádzame cez $i+n$. Teraz si vieme spraviť analýzu prípadov:

• Prípad $x<x’$

• $x’ \leq i \leq x + n$ (tento príklad je na obrázku zvýraznený červenou): táto cesta trvá $a_i + (i-x) + (i - x’) = a_i + 2i - x - x’$

• $x + n \leq i \leq x’ + n$ (tento príklad je na obrázku zvýraznený modrou): táto cesta trvá $a_i + (i-(x+n)) + (i - x’) = a_i + 2i - x - x’ - n$ Prípad $x > x’$:

• $x \leq i \leq x’ + n$ (tento príklad je na obrázku zvýraznený červenou): táto cesta trvá $a_i + (i-x) + (i - x’) = a_i + 2i - x - x’$

• $x’ + n \leq i \leq x + n$ (tento príklad je na obrázku zvýraznený modrou): táto cesta trvá $a_i + (i-x) + (i - (x’+n)) = a_i + 2i - x - x’ - n$

Všimnime si, že v každom z týchto štyroch prípadov sa nám cena rozloží na $a_i + 2i$ a konštantu závisiacu iba od otázky (buď $x+x’+n$ alebo $x+x’$). Prvé číslo vieme pre každý prípad zistiť intervalovým stromom ktorý si na $i$-tej priehradke pamätá čísla $a_i+2i$, druhé číslo záleží od prípadu.

A napokon, aj prípad doľava-dole-doprava vieme riešiť nápodobne, len miesto $a_i + 2i$ potrebujeme hodnoty $a_i-2i$. Ďalšia možnosť je pozorovanie, že toto je to isté ako doprava-dole-doľava ak vymeníme $x$ a $x’$.

Takže aby sme to zhrnuli, potrebujeme niekoľko (dva alebo tri) intervalové stromy² s hodnotami $a_i$, $a_i + 2i$ (resp. $a_i-2i$). Aby sme nemuseli riešiť prechody cez $n$, cyklickosť poľa implementujeme tak, že máme hodnoty dvakrát za sebou. Pri udalostiach typu ! jednoducho zmeníme hodnoty v intervalových stromoch na vhodných miestach.

Pri udalostiach typu ? si poriadne rozpíšeme možnosti, a spýtame sa vhodné otázky.

Ako rýchlo toto riešenie beží? Pre každú otázku použijeme konštantný počet queries pre intervalový strom, a teda použime $O(\log n)$ operácií pre každú udalosť. Na vybudovanie intervalových stromov a načítanie vstupu potrebujeme lineárny čas, takže dostaneme výslednú časovú zložitosť $O(n+q\log n)$.

Pamäťová zložitosť je $O(n)$, keďže si musíme uložiť vstup a intervalové stromy.

Implementácia

Vzhľadom na veľké množstvo jednotlivých prípadov je sa v tejto úlohe veľmi ľahké pomýliť, preto pri implementácii si odporúčame použiť prístup lenivého programátora³ a prípady si poriadne rozpísať, resp. nakresliť.