Kdybychom chtěli řešit úlohu experimentálně a ne programem, mohli bychom postupovat následovně:
Seženeme si dostatečné množství dobrovolníků. Na začátku budou všichni jen tak sedět u vstupu na tobogany a budou pasivní. Postupně budeme zpracovávat jednotlivé zaznamenané události, kdy došlo k nasednutí člověka na tobogan. Tyto události zpracováváme v pořadí, v jakém k nim došlo. Máme-li nechat někoho nasednout na tobogan, podíváme se, zda máme k jízdě připraveného nějakého aktivního dobrovolníka. Pokud ano, jednoho z nich (je jedno, kterého) pošleme na jízdu dolů toboganem. Pokud ne, vezmeme jednoho pasivního dobrovolníka, prohlásíme ho za aktivního a pošleme dolů toboganem jeho. Dobrovolník má samozřejmě za úkol vyběhnout zpět na místo startu, jakmile jízdu na toboganu ukončí. U startu pak bude čekat připraven na další jízdu (zůstává již stále aktivní). Tvrdíme, že počet aktivních dobrovolníků na konci dne je roven minimálnímu počtu návštěvníků aquaparku, kteří mohli v ten den tobogany používat.
Popsané řešení vypadá docela dobře – nového aktivního dobrovolníka přidáme, jen když opravdu musíme. To ale ještě není důkazem správnosti. Musíme se zamyslet, zda by nebylo lepší někdy dříve přidat třeba více aktivních dobrovolníků a díky tomu někdy později ušetřit. Správnost řešení proto raději dokážeme pořádně.
Předpokládejme, že máme libovolné optimální řešení O a že máme řešení N nalezené naším algoritmem. Ukážeme, že O se dá konečným počtem kroků transformovat na N, přičemž nezměníme počet lidí, které potřebujeme.
Všimněte si první události, kdy se O a N odliší, tzn. poprvé se stane, že na nějaký tobogan nasedne v každém z těchto řešení jiná osoba. Jak se to mohlo stát? Rozebereme si několik případů:
Ukázali jsme, že pokud se řešení O a N liší, pak bez ohledu na to, jaký případ nastal, vždy můžeme řešení O upravit tak, abychom získali stejně dobré řešení, které se odlišuje od N až v nějakém pozdějším kroku. Po konečně mnoha opakováních výše uvedeného postupu tedy z řešení O vytvoříme naše řešení N. Tím jsme dokázali, že i naše řešení N je nutně optimální.
Zbývá navrhnout implementaci uvedeného postupu. Program jsme vytvořili tak, aby se s jeho pomocí dal navíc přímo sestrojit jeden optimální rozvrh jízd. Vstup si budeme reprezentovat pomocí tří front (pro každý tobogan jedna). Rovněž výstupy z toboganů (tj. časy, kdy z nich vystupují dobrovolníci po skončení jízdy) si udržujeme v dalších třech frontách. Nejbližší událost vždy zjistíme jako minimum z hodnot ve vstupních frontách. Při zpracování každé události se podíváme na aktuální situaci na výstupu a určíme tam nejdříve vystupujícího dobrovolníka. Jestliže stíhá jízdu odpovídající zpracovávané události, vezmeme ho z patřičné výstupní fronty. Pokud nestíhá, musíme přidat nového aktivního dobrovolníka.
Časová i paměťová složitost tohoto řešení je O(N), kde N je celkový počet jízd.
Můžeme postupovat také jinak. Vezmeme prvního dobrovolníka, pošleme ho na úplně první jízdu, potom na nejbližší další takovou jízdu, kterou stíhá, atd. Jestliže nám zbyly neuskutečněné jízdy, přidáme druhého člověka, pak případně ještě třetího, atd., dokud nepokryjeme všechny jízdy.
Důkaz správnosti tohoto řešení vypadá podobně jako v případě našeho vzorového řešení. (Přesněji, kdybychom do našeho vzorového řešení přidali podmínku „máš-li k dispozici více aktivních dobrovolníků, pošli na tobogan toho s nejmenším pořadovým číslem”, sestrojili bychom totéž řešení, jako tímto postupem.)
Přímočará implementace má v nejhorším možném případě časovou složitost O(N2). Existuje i implementace tohoto řešení s časovou složitostí O(NlogN).
Za zmínku stojí také pomalejší řešení, které je ale obecnější a dalo by se použít i tehdy, kdyby jednotlivé tobogany začínaly a končily na různých místech v aquaparku, takže pěší přesuny mezi jejich konci a začátky by trvaly různě dlouho. Úlohu převedeme na hledání maximálního párování v bipartitním grafu. Jednu část grafu budou tvořit časy konců jízd, druhou časy začátků. Hrana znamená, že se po daném konci jízdy stíhá daný začátek další jízdy. Každému platnému rozvrhu jízd odpovídá nějaké párování v tomto grafu a naopak. Každá hrana zařazená do párování vlastně znamená, že člověk, který právě dokončil jednu jízdu, má jako následující uskutečnit příslušnou druhou jízdu. Je zjevné, že každou hranou zařazenou do párování ušetříme jednoho člověka. Hledaný minimální počet lidí proto můžeme spočítat jako N minus velikost maximálního párování v našem bipartitním grafu.
Vzorové řešení tohoto příkladu bude využívat stejný postup, jaký jsme použili v úloze o čokoládě z domácího kola. Každý čtvercový úsek farmy můžeme jednoznačně identifikovat bodem, v němž leží jeho pravý dolní roh, a délkou jeho strany. Základní myšlenkou řešení je, že místo počítání pestrých (tzn. vícebarevných) čtverců můžeme spočítat všechny čtverce a od jejich počtu odečíst počet jednobarevných čtverců.
Kdybychom pro každý bod (r,s) znali počet jednobarevných čtverců, jejichž pravý dolní roh je (r,s), dokázali bychom pak už hledaný výsledek snadno spočítat. Počet všech čtverců (jednobarevných i pestrých dohromady) s pravým dolním rohem (r,s) je totiž min(r,s). Počet pestrých čtverců pro (r,s) spočítáme tedy jako min(r,s) minus počet jednobarevných čtverců pro (r,s).
Podívejme se pozorněji na čtverce různých velikostí, které mají pravý dolní roh na políčku (r,s). Je-li některý z nich pestrý, jsou pestré i všechny čtverce větší, neboť ty ho celý obsahují.
Označme K(r,s) délku strany největšího čtverce, který má pravý dolní roh na (r,s) a je jednobarevný (všechny plodiny v něm jsou stejné). Číslo K(r,s) je zároveň rovno počtu všech jednobarevných čtverců, jejichž pravý dolní roh je (r,s).
Jak spočítáme hodnotu K(r,s)? Uvažujme políčka (r,s-1), (r-1,s) a (r-1,s-1). Je-li aspoň na jednom z těchto políček jiná plodina než na políčku (r,s), potom je K(r,s) rovno jedné, jelikož čtverec s délkou strany dva už je pestrý. V případě, že se plodiny pěstované na těchto třech políčkách shodují s plodinou na políčku (r,s), potom platí vztah:
K(r,s) = 1 + min( K(r-1,s), K(r,s-1), K(r-1,s-1) ).
Důkaz této rovnosti je stejný jako důkaz uvedený v řešení úloh domácího kola.
Protože k výpočtu K(r,s) stačí znát K(r-1,s), K(r,s-1), K(r-1,s-1), můžeme postupovat po řádcích shora dolů a v rámci každého řádku zleva doprava. Každou hodnotu přitom získáme v konstantním čase s využitím hodnot, které už známe. Řešení má proto časovou složitost O(RS). Kdybychom si načetli a uložili celý vstup, měli bychom také paměťovou složitost O(RS). Podobně jako v domácím kole můžeme paměťovou složitost snížit na O(R), když si uvědomíme, že stačí udržovat v paměti pouze dva řádky vstupu a dva řádky hodnot K(r,s), jelikož předcházející řádky již nebudeme potřebovat.
Ať si zvolíme jakoukoliv trasu, optimální nastavení omezovače rychlosti bude jistě rovno minimu z maximální rychlosti povolené na cestách tvořících naši trasu – méně se nevyplatí, více nesmíme. Pro dosažení nejnižší doby jízdy mezi dvěma městy má proto smysl nastavovat omezovač rychlosti jedině na některou z rychlostí, které jsou zadány na vstupu.
Uvažujme nejprve, za jaký čas se dokážeme dostat z města x do města y, když už máme nastaveno omezení na nějakou rychlost v. Nech Gv je podgraf původního grafu, který obsahuje jen hrany, na nichž je rychlost v ještě povolena. Máme-li tedy nastaveno omezení na rychlost v, můžeme jet pouze po hranách grafu Gv. Jelikož rychlost jízdy už máme určenou, nejlepší dobu jízdy dosáhneme tehdy, pokud zvolíme nejkratší možnou trasu (v kilometrech).
Tím dostáváme následující řešení: Pro každou rychlost v ze vstupu vytvoříme graf Gv. V něm určíme délky (v kilometrech) nejkratších cest mezi všemi dvojicemi měst x a y – označíme je distv(x,y). Výsledné optimální doby jízdy mají hodnotu distv(x,y) / v.
Jakou časovou složitost má toto řešení? Podle našeho úvodního pozorování stačí jako hodnoty v uvažovat všechny rychlosti zadané na vstupu – těch je celkem M. Graf Gv sestrojíme snadno v čase O(M) tak, že projdeme všechny hrany původního grafu. Zbývá vyřešit standardní problém určení délky nejkratší cesty v grafu Gv mezi každou dvojicí vrcholů. Nabízejí se dva možné přístupy:
Naše vzorové řešení využívá podobnou myšlenku jako Floydův-Warshallův algoritmus. Nejprve seřadíme všechny hrany ze vstupu do posloupnosti e1,e2,..,em tak, aby pro jejich maximální povolené rychlosti platilo v1 ≥v2 ≥v3 ≥..≥vm. Úlohu nyní vyřešíme metodou dynamického programování. Postupně pro každé k spočítáme všechny hodnoty dk(x,y) – délka nejkratší cesty (v kilometrech) mezi městy x a y, jestliže se smíme pohybovat pouze po hranách e1,e2,..,ek (resp. dk(x,y)=∞, pokud taková cesta neexistuje.) Podle definice z předcházejícího řešení můžeme také říci, že dk(x,y) je délka nejkratší cesty mezi městy x a y v grafu Gvk. Jak jsme již ukázali, k vyřešení úlohy stačí nalézt hodnoty dk(x,y) pro každé k=1,2,..,M.
V k-tém kroku výpočtu chceme "zpřístupnit" hranu ek a přepočítat hodnoty dk(x,y) pro všechny dvojice měst x,y. Při stanovení hodnoty dk(x,y) uvažujeme dvě možnosti.
Jestliže označíme uk,1 a uk,2 vrcholy spojené hranou ek, potom platí buď
dk(x,y)= dk-1(x,uk,1) + |ek|+ dk-1(uk,2,y)
nebo
dk(x,y)= dk-1(x,uk,2) + |ek|+ dk-1(uk,1,y)
podle toho, kterým směrem naše trasa prochází hranou ek.
Můžeme si zvolit, zda hranu ek použijeme nebo ne, a pokud ano, tak v kterém směru. Vybereme si samozřejmě nejlepší z uvedených tří možností. Proto je hodnota dk(x,y) rovna minimu z uvedených tří možností.
Tím jsme získali rekurzivní vztah pro výpočet hodnot dk(x,y). Každou z těchto MN2 hodnot pomocí něho spočítáme v konstantním čase, celé řešení má proto časovou složitost O(MN2).
Pro snížení paměťové složitosti si stačí uvědomit, že hodnoty dk závisejí jenom na hodnotách dk-1. Vystačíme proto s pamětí velikosti O(N2).
(V celém řešení automaticky předpokládáme, že všechna sčítání se počítají modulo 65 536.)
Použijeme dva registry a a b. Na začátku výpočtu do nich vložíme hodnoty L0 = 2 a L1 = 1.
Představme si situaci, že v a máme hodnotu Lx-2, v b hodnotu Lx-1 a roura je prázdná. Hodnotu Lx spočítáme tak, že vložíme do roury hodnoty z registru a a z registru b a provedeme příkaz add. Následně do roury vložíme ještě jednou hodnotu z registru b. V rouře tedy budeme mít za sebou nejprve hodnotu Lx-2+Lx-1 = Lx a potom hodnotu Lx-1. První z nich přečteme do registru b a druhou do registru a. Tím jsme se posunuli o jeden krok výpočtu: začínali jsme s hodnotami Lx-2 a Lx-1, skončili jsme s hodnotami Lx-1 a Lx.
Nyní již dokážeme snadno napsat celý program řešící zadanou úlohu: Číslo z roury uložíme do registru n. Inicializujeme registry a a b na hodnoty L0 a L1. Výše uvedený postup n-krát zopakujeme, čímž dostaneme v registrech a a b hodnoty Ln a Ln+1. Nakonec hodnotu z registru a vypíšeme na výstup.
get n put 2 ; get a put 1 ; get b label loop jz n konec put n ; put 1 ; sub ; get n put a ; put b ; add put b get b get a jump loop label konec put a print
K otestování, zda je číslo rovno 47, použijeme příkaz jeq – skok v případě rovnosti hodnot dvou registrů. Nejprve ale musíme dostat hodnotu 47 do některého registru. To nemůžeme provést jednoduše tak, že ji vložíme do roury a hned přečteme do registru, neboť rouru máme na začátku výpočtu plnou vstupních údajů. Celý obsah roury proto budeme muset přetočit.
Do roury nejprve vložíme hodnotu 0, která bude sloužit jako zarážka za vstupní posloupností kladných čísel. Za tuto 0 vložíme číslo 47. Nyní budeme opakovaně číst čísla z roury do registru a vkládat je zpět do roury, dokud nepřečteme naši nulu. V tomto okamžiku víme, že prvním číslem v rouře je 47 a za ním následuje celá původní vstupní posloupnost. Hodnotu 47 si tedy přečteme do registru z. Tím se dostaneme do stejné situace, jako na začátku výpočtu, jen s jediným rozdílem – v registru z máme připraveno číslo 47. S ním teď každou hodnotu z roury porovnáme. Pokud se nám roura vyprázdní, aniž bychom v ní hodnotu 47 našli, vložíme do roury 0, vypíšeme ji na výstup a skončíme. Když naopak hodnotu 47 najdeme, nejprve v cyklu vyprázdníme zbytek roury, pak do ní vložíme hodnotu 1, vypíšeme ji na výstup a skončíme.
put 0 put 47 label pretoc get a ; jz a dal ; put a jump pretoc label dal get z label testuj jempty nenasel get a jeq a z nasel jump testuj label nasel jempty pis1 get x jump nasel label pis1 put 1 ; print stop label nenasel put 0 ; print
Pro zajímavost uvedeme ještě jednu možnost, jak lze řešit druhou část úlohy. Za posloupnost si opět vložíme nulu jako zarážku. Postupně čteme zadanou posloupnost a vždy, když narazíme na hodnotu 47, vložíme do roury číslo 1. Po přečtení nuly-zarážky, vložíme do roury ještě jednu 0.
V tomto okamžiku tedy máme v rouře nejprve tolik jedniček, kolikrát byla ve vstupní posloupnosti obsažena hodnota 47, a za nimi jednu nulu. První číslo z roury vypíšeme na výstup a skončíme.
Pro zjištění, zda je nějaké číslo sudé, spočítáme zbytek čísla po dělení 2 a ověříme, zde je roven nule. Zbytek po celočíselném dělení umíme určit příkazem mod. Zároveň si ale musíme někde uchovat i původní hodnotu čísla, neboť příkaz mod svoje vstupy z roury odstraní.
V první fázi řešení si upravíme obsah roury tak, abychom mohli následně používat příkaz mod na výpočet zbytků po dělení dvěma. Použijeme stejný trik jako v předchozí úloze – začneme tím, že za vstupní posloupnost vložíme 0 jako zarážku. Nyní budeme po jednom číst čísla ze vstupní posloupnosti a za každé přečtené číslo a do roury postupně vložíme hodnoty 1, a, 2, a. Hodnota 1 bude signalizovat, že ještě následuje další číslo, další dvě hodnoty a a 2 použijeme jako vstupy pro příkaz mod a poslední hodnota a zůstane zachována.
Druhou fázi řešení zahájíme opět vložením zarážky 0 na konec posloupnosti. Potom opakovaně čteme čísla z roury do zvoleného registru. Když přečteme nulu, máme zpracovanou celou posloupnost a přejdeme na třetí fázi výpočtu. Jinak provedeme příkaz mod, který vyzvedne ze začátku roury hodnoty a a 2 a místo nich vloží na konec roury amod 2. Následně přečteme z roury hodnotu a do registru a vložíme ji zpět do roury.
Jestliže v rouře byla původně posloupnost čísel (s1, .., sk), pak po skončení druhé fáze našeho řešení tam budeme mít posloupnost (s1 mod 2,s1, s2mod 2,s2, .., skmod 2, sk).
Ve třetí, závěrečné fázi výpočtu použijeme spočítané zbytky po dělení dvěma k tomu, abychom určili, která čísla máme vypsat a která nikoli. Přečteme vždy zbytek, je-li roven 1, následující číslo zahodíme, je-li roven 0, následující číslo vypíšeme na výstup. Po vyprázdnění roury výpočet skončí.
put 0 label mark get a ; jz a druha_faze put 1 ; put a ; put 2 ; put a jump mark label druha_faze put 0 label dale get a ; jz a vypis mod get a ; put a jump dale label vypis jempty konec get b jz b chceme get a jump vypis label chceme print jump vypis label konec