Vzhledem k omezení na počet N měst uvedenému v zadání úlohy, není možné si vstup reprezentovat maticí velikosti N×N. Uložíme si tedy raději vstup tak, že pro každé z měst vytvoříme seznam nejvýše 100 měst, do kterých z tohoto města vedou trasy. Pro jednoduchost budeme nazývat města, mezi kterými vede trasa, sousední.
Nejjednodušším řešením úlohy je zvolit každé z N měst jako počátek Tiborovy trasy, pak zvolit každé z nejvýše 100 sousedních měst jako druhé město trasy, každé z nejvýše 100 sousedních měst druhého města jako třetí město trasy a nakonec každé ze 100 sousedních měst třetího města jako čtvrté město trasy a pak ověřit, že mezi prvním a čtvrtým městem vede trasa. Toto řešení má sice lineární časovou složitost O(N), ale konstanta schovaná do „velkého O” je 1004 (vyzkoušení 1003 možností volby druhého, třetího a čtvrtého města a kontrola, že první a čtvrté město jsou sousední), takže toto řešení nemůže splnit časový limit pro tuto úlohu.
Rychlejší řešení bude založeno na následující myšlence. Pokud ABCDA je čtyřdenní plán výletu, pak ABC a ADC jsou dvě dvojice na sebe navazujících tras. Jestliže je navíc plán ABCDA nejdelší možný, musí ABC a ADC tvořit nejdelší a druhou nejdelší ze všech dvojic tras, které začínají v A a končí v C. Kdyby tomu tak nebylo, bylo by možné plán výletu ještě zlepšit.
Naše řešení tedy bude vypadat následovně. Nejdříve zafixujeme město A. Poté pro každé z měst sousedících s A projdeme všechny jeho sousedy C a pokud nalezená dvojice (na sebe navazujících tras) z A do C je největší nebo druhá největší dosud nalezená, uložíme její hodnotu do pomocného pole. V průběhu výpočtu navíc kontrolujeme, zda jsme nenalezli dvě dvojice na sebe navazujících tras z A do C, jejichž součet ohodnocení by byl lepší než součet ohodnocení dosud nejlepšího nalezeného plánu pro výlet. Pokud tomu tak je, nahradíme plán výletu těmito trasami.
Toto řešení vyžaduje pro každé z N měst prozkoumání nejvýše 1002 dvojic (na sebe navazujících) tras, které z něj vedou. Je tedy rychlejší než první námi navrhované řešení. Na závěr si ještě vysvětleme, jak se vyhnout inicializaci pomocného pole pro ukládání dvojic tras mezi A a C (toto pole má velikost O(N)) – spolu s hodnotou dvojic na sebe navazujících tras si do pole též uložíme číslo města A a pak snadno poznáme, zda hodnoty uložené v poli odpovídají právě zafixovanému městu A nebo městu A z některé z předchozích iterací.
Časová složitost námi navrženého řešení je O(D2N), kde D je maximální počet sousedů města. Paměťová složitost je pak O(DN).
Na této myšlence jsou založeny následující dva programy: první v C++, druhý v Pascalu.
V popisu řešení bude L vždy značit délku posloupnosti příkazů, S šířku a V výšku mapy skladiště. Stavem robota budeme označovat čtveřici <X, Y, P, Směr>, kde X, Y je robotova pozice ve skladišti, 1≤P≤L je pozice následujícího příkazu v zadané sekvenci a Směr je směr natočení robota.
Počet stavů, ve kterých se robot může nacházet, je nanejvýš 4 S V L. Všimněte si, že jeho poloha ve skladišti, pozice v sekvenci příkazů a natočení jednoznačně určují, co bude robot dělat dál. Jakmile se robot ocitne v některém stavu podruhé, je jisté, že se zachová stejně jako po poslední návštěvě, a tedy se „zacyklí”. Ještě si všimněte, že robot se může dostat i do cyklu, který neobsahuje jeho výchozí stav, a že to, že se robot vrátil do stejné pozice ve skladišti při jiné pozici v sekvenci příkazů, ještě nemusí znamenat zacyklení.
Jistě vás napadlo, že nejjednodušší by bylo pro každé volné pole plánu simulovat chování robota začínajícího na tomto poli až k cíli nebo do zacyklení. Zacyklení je možné detekovat několika způsoby: poznamenáváním prošlých stavů cesty, simulováním 4 S V L příkazů, či simulováním dvou robotů různých rychlostí. Takovéto programy ale mají složitost O(S2V2L), protože nevylučují možnost, že robot pro velkou část startovních polí projde téměř každé pole řádově L-krát.*Autoři znají konstrukci mapy N×N a posloupnosti příkazů délky N, kde výše uvedené programy běží v čase řádově N4. S chytře napsaným zjišťováním cyklů může ale i toto řešení získat část bodů i za některé velké vstupy (jako například náhodně a hustě rozmístěné překážky).
Snadná pomoc, řeknete si, stačí si pro každý ze 4 S V L stavů pamatovat, jak dlouho trvá dostat se z něj mimo mapu, či zda se z něj robot zacyklí. Ať už si tabulku hodnot stavů budeme počítat „od konce” od stavů těsně před opuštěním mapy nebo rekurzivní funkcí z počátečních stavů, platí, že celkově na každý ze stavů provedeme pouze jeden výpočet. To nám dá algoritmy s časovou složitostí O(S V L), ale stejně vysoká bude i paměťová složitost – tabulka mezivýpočtů bude mít velikost až 4 S V L, což je pro daná omezení až 5·108 položek.
V právě popsaném řešení jsme si pamatovali hodnoty pro každý stav – což takhle ušetřit a pamatovat si pouze některé stavy? Zkusme se omezit na stavy, ve kterých je robot před provedením prvního příkazu programu (tedy stavy <X, Y, P=1, Směr>). Vybraných stavů je nanejvýš 4 S V a následující vybraný stav lze z aktuálního vybraného stavu zjistit odsimulováním L příkazů.
Nejprve si popíšeme řešení pomocí rekurzivní funkce, která bude simulovat procházku ze zadaného stavu až k opuštění mapy či zacyklení, a zjištěné hodnoty pro vybrané stavy si zapamatuje. V tabulce Kroku[X, Y, Směr] bude pro každý vybraný stav uloženo, zda je ještě neznámý, zda jsme jej již navštívili během aktuální procházky, zda se z něj robot zacyklí, nebo po kolika krocích z něj robot opustí mapu.
Funkce KolikKroků(X, Y, Směr) vrátí buď počet kroků nutný k opuštění mapy, nebo -1, pokud zjistí cyklus. Po zavolání funkce se podíváme do tabulky Kroků a pokud je hodnota již známa, vrátíme ji. Pokud je v tabulce uvedeno, že jsme tento stav již navštívili, vrátíme informaci o tom, že tato procházka vede do cyklu. Pokud není hodnota pro stav známa, poznamenáme do Kroků, že jsme skrz tento stav na této procházce šli, odsimulujeme L příkazů k dalšímu vybranému stavu <X', Y', P'=1, Směr'> (nebo k okamžiku opuštění mapy) a zavoláme k := KolikKroků(X', Y', Směr'). Je-li vrácené k počet příkazů, uložíme součet k+L do Kroků[X, Y, Směr] a vrátíme tuto hodnotu; je-li to informace o zacyklení, uložíme ji a vrátíme.
První zavolání funkce KolikKroků na konkrétní stav spotřebuje čas nanejvýš O(L) a paměť O(1). Každé další zavolání stojí čas pouze O(1) a již nic nevolá, takže tento čas můžeme „naúčtovat” při analýze časové složitosti volající funkci. Vzhledem k tomu, že prvních volání KolikKroků bude nanejvýš tolik, kolik je vybraných stavů, máme algoritmus s časovou složitostí O(S V L) a paměťovou složitostí O(S V). Jeho implementace v Pascalu je uvedena níže.
Navržený rekurzivní algoritmus je správně, ale používá příliš velký zásobník. Ukázková implementace proto používá vlastní zásobník na vybrané stavy navštívené během procházky a celá procedura KolikKroků je nerekurzivní. V programu níže jsme si ještě ušetřili práci sjednocením informace o tom, že stav je už navštívený v aktuální procházce, s informací, že stav vede do cyklu. V situaci, kdy narazíme na cyklus nebo navštívený stav, by se program měl chovat stejně a takto ušetříme vybírání zásobníku.