Úlohu budeme řešit pomocí Dijkstrova algoritmu pro nalezení nejkratší cesty, jehož podrobný popis lze nalézt například v Programátorské kuchařce KSP (viz http://ksp.mff.cuni.cz/tasks/20/cook4.html). Vstupem Dijkstrova algoritmu je n měst propojených m silnicemi různých délek. Algoritmus v čase O((n+m)logn) nalezne nejkratší cestu mezi dvěma zadanými městy, tj. takovou, že součet délek silnic této cesty je nejmenší možný. Poznamenejme, že existuje implementace tohoto algoritmu v čase O(m+nlogn), která využívá tzv. Fibonacciho haldy. Ve vzorovém řešení nám však bude stačit jednodušší implementace za použití standardní haldy.
V našem případě budou políčka čtvercové sítě představovat města a dvě sousední políčka spojíme „silnicí” délky cS, pokud se jejich nadmořské výšky liší nejvýše o 1 obří sáh. Dále musíme přidat silnice, které reprezentují mosty a tunely. Jednou z možností by bylo se z každého políčka vydat všemi čtyřmi možnými směry, dokud nenarazíme na políčko stejné výšky nebo okraj čtvercové sítě, a v prvním případě přidat silnici odpovídající mostu nebo tunelu. Takovéto řešení by vyžadovalo čas O(RS(R+S)) na určení všech silnic. My si ukážeme, jak lze všechny silnice určit v čase O(RS).
Zamysleme se, jak lze určit možné mosty v jednom řádku čtvercové sítě. Řádek budeme procházet zleva doprava a budeme si v poli pamatovat ta políčka, která jsou od aktuálního políčka vlevo a všechna políčka mezi tímto políčkem a aktuálním políčkem mají menší výšku. Například pokud S=10 a výšky políček v řádku jsou 10, 12, 6, 7, 8, 4, 3, 1, 9, 5, pak po zpracování sedmi políček budeme mít v poli uloženo druhé, páté, šesté a sedmé políčko. Povšimněte si, že výšky políček v pořadí, v jakém jsou uloženy v poli, tvoří vždy klesající posloupnost.
Popišme si, jak lze hodnoty v poli udržovat a jak je využít k určení silnic, které představují mosty. Dokud je výška aktuálního políčka větší než výška posledního políčka v poli, políčka z pole budeme odebírat. Pokud se nyní výšky shodují, nalezli jsme dvojici políček, která lze spojit mostem. Tento most přidáme jako silnici mezi odpovídajícími dvěma políčky (její délka bude cS+lcM, kde l je počet přemostěných políček) a poslední políčko v poli nahradíme aktuálním políčkem. Pokud je výška posledního políčka v poli vyšší, aktuální políčko do pole přidáme.
Je zřejmé, že výše uvedeným postupem nalezneme všechny možné mosty mezi políčky v jednom řádku. Protože každé políčko do pole jen jednou vložíme a jednou vyjmeme (a po porovnání buď políčka z pole vyjímáme, do pole přidáváme nebo měníme aktuální políčko), na zpracování jednoho řádku spotřebujeme čas O(S). Stejným způsobem pak můžeme určit silnice odpovídající tunelům.
Celkově tak na určení všech těchto silnic pro všechny řádky a sloupce je potřeba čas O(RS). Protože z každého políčka vede nejvýše osm silnic (čtyři na sousední políčka a čtyři tunely nebo mosty), je počet silnic lineární s počtem políček. Časová složitost Dijkstrova algoritmu aplikovaného na tento problém pak bude O(RSlogRS), a to je také časová složitost celého námi navrženého algoritmu. Paměťová složitost činí O(RS).
Pro zjednodušení nejdříve zkusíme vynechat požadavek, aby básnička začínala na stejný rým, kterým končí. Protože je pořadí slok pevně dané, lze takto zjednodušené zadání řešit pomocí dynamického programování. Můžeme totiž využít toho, že pokud máme množinu všech slok Ri, na které by báseň mohla končit, kdyby měla být dlouhá pouze i slok, pak jsme schopní snadno najít množinu všech slok Ri+1, na které může končit báseň dlouhá i+1 slok.
Postup je jednoduchý – ze všech variant sloky i+1, které označme jako Vi+1, vybereme ty, které začínají na stejný rým, kterým končí nějaká sloka v množině Ri. Množina takto vybraných slok pak tvoří množinu Ri+1. Pokud se na sloky budeme dívat jako na dvojice přirozených čísel, pak lze tento fakt zapsat matematicky například takto:
Ri+1 = { (a, b) | (a, b) ∈ Vi ∧ ∃x : (x, a) ∈ Ri }.
Z této myšlenky lze snadno odvodit řešení zjednodušené úlohy. Množinu R1 získáme přímo jako množinu všech variant první sloky. Báseň pak postupně prodlužujeme, až dostaneme množinu RN. Protože cílem úlohy je i vypsat vybrané varianty, musíme si zároveň s každou slokou s v Ri+1 pamatovat, díky které variantě i-té sloky byla sloka s vybrána do množiny Ri+1. Pokud je takových variant více, lze vybrat libovolnou z nich. S pomocí této dodatečné informace můžeme snadno odzadu zrekonstruovat některou z hledaných posloupností.
Požadavek na cykličnost rýmů nám situaci mírně zkomplikuje. Nestačí totiž najít sloku v množině RN takovou, že se rýmuje s některou první slokou. Jako příklad uvažme, že varianty první sloky jsou (1, 2) a (2, 3) a jediná varianta druhé sloky je (3, 1). V množině RN pak bude jediná sloka (3, 1), ale jako první sloku nemůžeme vzít sloku (1, 2), neboť pak báseň nebude cyklická.
Můžeme si ale např. s každou slokou s z množiny Ri navíc pamatovat, na které sloky báseň musí začínat, aby mohla končit slokou s. Jinou možností je pustit výpočet zvlášť pro všechny varianty první sloky a pokud některá sloka z RN končí na rým, kterým začíná aktuální první sloka, tak jsme našli řešení. Oba postupy mají stejnou časovou složitost. Liší se ale složitostí paměťovou, neboť v prvním případě si budeme muset ukládat až S1-krát více informací pro rekonstrukci básničky.
Výsledný algoritmus je nyní již snadný. Pro každou variantu první sloky vyrobíme množinu R1, což je jednoprvková množina obsahující vybranou první sloku. Použijeme výše popsaný algoritmus pro necyklickou báseň. Pokud se jímž v množině RN nachází sloka, která končí na rým, jímž začíná aktuální první sloka, tak jsme nalezli řešení, které snadno zrekonstruujeme, vypíšeme a skončíme. V opačném případě pokračujeme další variantou první sloky.
Jak algoritmus efektivně implementovat? Množinu Ri si budeme reprezentovat přímočaře booleovským polem. To bude pro každou variantu i-té sloky určovat, zda se nachází v množině Ri, nebo ne. Pro výpočet Ri+1 si pro každou variantu Vi+1 zjistíme, zda existuje sloka v Ri, se kterou se rýmuje. Pokud ano, vložíme variantu do Ri+1. Časová složitost toho postupu je Si ·Si+1 a výsledná složitost celé úlohy je tedy O(S1 ·N · (maxSi)2). Zkusme ji ale ještě trochu zlepšit.
První vylepšení spočívá v tom, že zkusíme jeden krok algoritmu zrychlit na O(Si + Si+1). To uděláme tak, že si v rámci předvýpočtu seskupíme sloky z Vi do skupin tak, aby v každé skupině byly pouze sloky končící na stejný rým. Nyní každou sloku s z Vi+1 propojíme se skupinou, která odpovídá rýmu, na který s začíná, případně si zapamatujeme, že taková skupina neexistuje.
Potom můžeme jedním průchodem přes Vi pro každou skupinu zjistit, zda se v ní nachází aspoň jedna sloka, která patří do Ri. Druhým průchodem přes Vi+1 pak snadno zjistíme, které sloky patří do Ri+1 a které ne. K tomu stačí podívat se na výsledek odpovídající skupiny z předchozího průchodu.
Předvýpočet provedeme tak, že si sloky z Vi setřídíme podle druhého rýmu a sloky z Vi+1 podle prvního rýmu. Poté lineárním průchodem očíslujeme skupiny čísly 0, 1, .., počet skupin a pro každou množinu Vi si např. v obyčejném poli zapamatujeme, do které skupiny jednotlivé varianty patří. Druhým lineárním průchodem pak pro sloky z Vi+1 určíme, se kterou skupinou jsou propojené.
Časová složitost se změní na O(N ·maxSi ·logmaxSi) na předzpracování vstupu a O(S1 ·N ·maxSi) pro samotný výpočet.
Druhé urychlení (které ale pro dosažení plného počtu bodů nebylo nutné implementovat), spočívá v myšlence, že ve skutečnosti nezáleží na tom, kterou slokou začínáme. Pokud tedy začneme hledat báseň od sloky, která má nejméně variant, snížíme časovou složitost výpočtu na O(minSi ·N · maxSi).