Kdykoliv máme určit nejmenší počet kroků, jimiž lze dosáhnout nějakého cíle, měli bychom uvažovat o možnosti sestrojit vhodný graf a v tomto grafu nalézt nejkratší cestu. Graf vznikne pokaždé stejně: jeho vrcholy odpovídají stavům, v nichž se můžeme nacházet, a hrany vycházející z vrcholu odpovídají tahům, které můžeme v dané situaci provést.
Jak to bude vypadat v našem případě? Stavy, tedy vrcholy grafu, budou odpovídat jednotlivým pozicím, na nichž se Santa může nacházet. Přesněji, budeme uvažovat pozice, na kterých může ležet levý horní roh Santy – tím je jeho poloha jednoznačně určená. Každý vrchol grafu můžeme jednoznačně popsat dvěma čísly: jeho souřadnicemi. Protože r1,s1≤2 000, náš graf bude mít nejvýše 4 miliony vrcholů.
Z každého vrcholu povedou hrany odpovídající krokům, které v té chvíli může Santa provést. Na výběr máme jen 4 směry pohybu, takže z libovolného vrcholu budou vycházet nejvýše 4 hrany.
Abychom věděli, jaké hrany v grafu máme, potřebujeme zjistit, na kterých pozicích může Santa stát a na kterých (kvůli překážkám) stát nemůže. Tím se budeme zabývat později. Zatím předpokládejme, že to umíme zjistit, a vraťme se zpět k našemu grafu.
Když už máme sestrojený graf, zbývá v něm nalézt nejkratší cestu. K tomu použijeme algoritmus prohledávání do šířky (breadth-first search, BFS). Toto prohledávání představuje způsob, jak by se v daném grafu šířila voda z počátečního vrcholu rovnoměrně do všech směrů. Nejprve zpracujeme počáteční vrchol (vzdálenost 0), potom postupně všechny jeho sousedy (každý z nich má vzdálenost 1 od počátečního vrcholu), potom sousedy jeho sousedů (vzdálenost 2), atd.
Prohledávání do šířky snadno implementujeme pomocí fronty:
prohledej(vrchol v):
Označ v jako navštívený.
Vzdálenost do v = 0.
Vytvoř frontu Q obsahující jediný prvek v.
Dokud fronta Q není prázdná:
Vyber ze začátku fronty Q prvek x.
Pro každou hranu vedoucí z x:
Jestliže její koncový vrchol w není navštívený:
Označ w jako navštívený.
Vzdálenost do w = 1 + vzdálenost do v.
Zapamatuj si, že do w jsme se dostali z x.
Vlož w na konec fronty Q.
Časová i paměťová složitost tohoto řešení je lineární vzhledem k velikosti místnosti, tedy O(r1s1). Proč tomu tak je? V první řadě si uvědomíme, že máme r1s1 vrcholů a nejvýše 4r1s1 hran, tedy dohromady máme O(r1s1) vrcholů a hran. Každý vrchol nejvýše jednou vložíme do fronty (v okamžiku, když se do něj poprvé dostaneme) a nejvýše jednou ho potom z fronty vyzvedneme. Každou hranu také zpracujeme nejvýše jednou: tehdy, když zpracováváme vrchol, z něhož tato hrana vede. Celkový počet kroků, které náš algoritmus vykoná, je proto přímo úměrný počtu vrcholů a hran v grafu.
Při implementaci si nepotřebujeme samostatně značit, které vrcholy jsou již navštívené. Poznáme to jednoduše tak, že navštívený vrchol má vzdálenost jinou než nekonečno.
V naší úloze máme také vypsat, kudy vede nalezená nejkratší cesta. Pro každé políčko si proto zapamatujeme, odkud jsme se na něj během prohledávání poprvé dostali. Následně můžeme pomocí těchto údajů od konce zrekonstruovat cestu.
Před spuštěním vlastního prohledávání do šířky potřebujeme zjistit, na které pozice může Santa vstoupit. Jsou to takové pozice, na kterých Santa překryje nejvýše M překážek (tolik jich dokáže pomocí magie schovat.)
Do tabulky T si chceme na políčko T[y,x] zapsat, kolik překážek je v obdélníku [y,x] až [y+r2-1,x+s2+1]. Jestliže T[y,x] ≤M, Santa může vstoupit na pozici y,x.
Jednoduchým řešením je pro každé políčko se podívat na r2×s2 políček vpravo dolů od něho a spočítat překážky. Toto řešení ale vykoná celkem Ω(r1s1r2s2) kroků, což je pro velké vstupy příliš.
Při hledání rychlejšího řešení se zkusíme nejprve podívat na jednorozměrný případ. V jednorozměrném případě nám stačí spočítat, kolik překážek je na políčkách [y, x] až [y, x+s2-1]. To vypočítáme postupně pro každé x:
T[y,0] = počet překážek od [y,0] do [y,s2-1] T[y,1] = T[y,0] + (1 když [y,s2] je 'X') - (1 když [y,0] je 'X') ... T[y,i] = T[y,i-1] + (1 když [y,i+s2-1] je 'X') - (1 když [y,i-1] je 'X') .. T[y,s1-s2] = T[y,s1-s2-1] + (1 když [y,s1-1] je 'X') - (1 když [y,s1-s2-1] je 'X')
Výpočet T[y, 0] nám sice bude trvat s2 kroků, ale potom už každé ze zbývajících s1-s2 políček spočítáme v konstantním čase. Celkem tedy provedeme při zpracovaní jednoho řádku jen O(s1) kroků.
Dále je to už jednoduché. Pokud nám 6 bodů nestačí, stačí si uvědomit, že dvojrozměrný případ vyřešíme tak, že provedeme ještě jednou totéž, ale tentokrát po sloupcích. Přitom použijeme hodnoty, které jsme právě vypočítali průchodem po řádcích. Tento předvýpočet zvládneme v čase O(r1s1). Totéž platí i pro BFS, takže dostáváme řešení se zjevně optimální časovou složitostí O(r1s1). Paměťová složitost je také O(r1s1).
Místo předvýpočtu výše uvedeným způsobem můžeme přímo použít dvojrozměrné prefixové součty: pro každé y,x určíme počet překážek P[y,x] v obdélníku, který má v protilehlých rozích políčka [0,0] a [y-1,x-1]. To dokážeme vhodným trikem spočítat v čase O(r1s1). Pomocí těchto hodnot pak už umíme v konstantním čase o libovolném obdélníku říci, kolik překážek obsahuje.
Předvýpočet:
P[y,x] = P[y-1,x] + P[y,x-1] - P[y-1,x-1] + (1 když [y-1,x-1] je 'X')
Počet překážek v obdélníku od [y1,x1] do [y2-1,x2-1]:
počet = P[y2,x2] - P[y2,x1] - P[y1,x2] + P[y1,x1]
Naším cílem samozřejmě je nalézt řešení, které bude efektivnější než přímočará simulace každého příkazu. Struktura ministerstva popsaná na vstupu představuje strom. A protože na obecném stromě se předepsané operace provádějí obtížně, prvním krokem řešení bude převedení úlohy na trochu jinou – na operace s intervaly a s prvky v poli. Každému vrcholu stromu tedy přiřadíme jeden prvek pole tak, aby každému oddělení v úřadu odpovídal souvislý úsek pole. Příkaz se potom bude týkat buď jednoho prvku pole, nebo nějakého intervalu.
Vhodné přiřazení pozic v poli vrcholům stromu získáme snadno: stačí libovolným způsobem prohledat strom do hloubky a každému vrcholu přiřadit index rovný pořadí, v němž byl poprvé navštíven. (Existuje více vyhovujících očíslování, toto je jen jedno z nich, které lze snadno a systematicky sestrojit.)
Během prohledávání si zároveň můžeme pro každý vrchol zapamatovat, kde začíná a kde končí interval, který obsahuje jeho podřízené. (Při prohledávání do hloubky interval odpovídající vrcholu v začíná tímto vrcholem samotným. Konec intervalu zjistíme tehdy, když prohledávání opouští vrchol v.)
Tuto část řešení dokážeme vykonat v čase O(n).
V tuto chvíli tedy už můžeme na strom zapomenout, máme jen obyčejné pole. Abychom mohli provádět příkazy ze zadání, potřebujeme s ním efektivně provádět následující operace:
Začneme efektivní implementací prvních dvou operací. (Za to získáme 9 bodů. Stačí navíc doplnit, že vždy, když budeme potřebovat zvýšit mzdu celému oddělení, projdeme všechny zaměstnance oddělení a každému zvýšíme jeho mzdu.)
Nad polem si postavíme binární strom. Hodnota každého vrcholu bude rovna součtu hodnot jeho synů, tedy zároveň součtu v celém intervalu pole, který je pokryt tímto vrcholem.
Změnu hodnoty implementujeme snadno: změníme hodnotu v poli a potom postupujeme stromeme nahoru a upravujeme hodnotu všech předků daného vrcholu. Časová složitost je úměrná hloubce tohoto stromu, tzn. O(logn). Zjištění součtu v úseku bude trochu komplikovanější, ale stejně rychlé. Potřebujeme sečíst ty vrcholy stromu, které interval pokrývá celé a zároveň nepokrývá jejich otce. Těchto vrcholů bude maximálně O(logn) – uvědomte si, že z každé úrovně stromu sčítáme maximálně dva vrcholy. Najdeme je jednoduchou rekurzivní procedurou, která prochází strom shora dolů:
zjisti_součet(vrchol x, sčítaný interval I):
Je-li interval I disjunktní s intervalem, který pokrývá podstrom ve vrcholu x:
Vrať 0.
Je-li interval I nadmnožinou intervalu, který pokrývá podstrom ve vrcholu x:
Vrať součet ve vrcholu x.
Vrať zjistisoučet(levý syn x, I) + zjistisoučet(pravý syn x, I).
Tento průchod má také časovou složitost O(logn). Analogicky, pomocí rekurze, můžeme implementovat i první operaci: začneme v kořeni stromu, sestoupíme dolů na správné políčko pole, to upravíme a při vynořování se z rekurze přepočítáme hodnoty v jeho předcích. U tohoto řešení to ještě není podstatné, ale právě takováto rekurzivní implementace bude potřebná při modifikacích popsaných v následující časti řešení.
Nyní si ukážeme, jak efektivně provádět zbývající operace. Začneme třetí operací a na ní si ukážeme princip řešení. Zbývající dvě operace potom už dořešíme analogicky.
Hlavní myšlenkou bude „nedělej nic předčasně”. Představte si, že chceme zvýšit o k všechny hodnoty v intervalu, který odpovídá nějakému vrcholu v našeho binárního stromu. Místo toho, abychom procházeli celý podstrom a zvyšovali každý jeho prvek, jednoduše si ve vrcholu v upravíme jeho součet (to můžeme udělat hned) a poznačíme si: „všechny prvky pod tímto vrcholem je třeba o k zvýšit”. Jeho potomky tedy zatím necháme tak, budou mít dočasně nesprávné hodnoty. To nám ale nevadí – jestliže někdy v budoucnosti budeme chtít přistupovat k potomkům vrcholu v, musíme přitom projít vrcholem v. No a právě až v tomto okamžiku vykonáme zaznamenaný příkaz. Přesněji, pokaždé když chceme z nějakého vrcholu u sestupovat po stromu dolů, nejdříve se podíváme, zda v u nemáme „odloženou” nějakou operaci. Pokud ano, nejprve tuto operaci přesuneme z u do obou jeho synů, a až potom se posuneme o krok níže (a tam celý postup opakujeme, je-li třeba).
Obecně bude zvyšování intervalu o x vypadat podobně jako zjišťování součtu. Jenom do všech třech operací (zvyšování prvku, zvyšování intervalu, zjišťování součtu intervalu) musíme doplnit část, v níž zkontrolujeme a případně vyřešíme odložené operace. Potřebujeme také umět „skládat” zvýšení: máme-li již v nějakém vrcholu zaznamenané zvýšení o a a přijde další zvýšení o b, jednoduše změníme zaznamenanou hodnotu na a+b.
Zbývají poslední dvě operace – zjišťování minima a úprava intervalu na konkrétní hodnotu. Zjišťování minima bude jednoduché: v každém vrchole si budeme udržovat navíc minimum příslušného intervalu. Úprava intervalu na konkrétní hodnotu proběhne podobně jako zvýšení celého intervalu o k. Provedeme ji líně jen ve vrcholech, které jsou celé pokryty intervalem, který měníme. Když provádíme tuto operaci a náhodou se ve vrcholu předtím objevila operace přidání, tuto starší operaci zahodíme (neboť nová operace všechny hodnoty stejně přepíše). Naopak, máme-li odloženou změnu na hodnotu a a přijde nám zvýšení o b, můžeme si například změnit zapamatovanou operaci na „změň hodnotu na a+b”.
Díky línému provádění dokážeme každou operaci vykonat v čase O(logn).