Úloha 1.u2: Třídění kotoučů (4 b)

Zadáno v čísle 23.1.

Řešeno v čísle 23.3.

Zadání

Příběh o Hanojských věžích nejspíše znáte. Málokdo ale ví, že existuje druhý podobný klášter. Na vysoké tyči je tam navléknuto 64 různě velkých kotoučů v náhodném pořadí. Mniši si každý den vyberou jeden z kotoučů, pak ten kotouč i s všemi nad ním vezmou, otočí jejich pořadí a vrátí je na tyč. Do kolika dnů zvládnou mniši tímto způsobem kotouče uspořádat tak, aby vespod byl největší kotouč a nikde neležel větší kotouč na menším? Zajímá nás horní odhad na potřebný počet dnů. Část bodů dostane i horší řešení. Naopak velice dobrá řešení mohou získat bonusové body navíc.

Řešení

Na první pohled si můžeme všimnout, že kotouče můžeme setřídit tak, že vždy dostaneme největší kotouč, který zatím není na správném místě, nahoru, a pak ho můžeme dalším otočením dostat na správné místo. Takto nad každým kotoučem strávíme nejvýše dva kroky a setřídit všechny kotouče nám tedy bude trvat nejdéle $2n$ kroků. S tímto postupem tedy budou mniši potřebovat na setřídění kotoučů 128 dní.

Většina z vás šla dál a všimli jste si, že když nám zbývá poslední nesetříděný kotouč, tak ho už není třeba třídit, čímž ušetříme dva kroky. To nám dává řešení v $2n-2$ krocích, tedy za $126$ dní. Dále si někteří z vás správně všimli, že poslední dva kotouče jdou vždy setřídit nejvýše jedním krokem. Tím dostaneme řešení v $2n-3$ krocích, tedy za $125$ dní. Rozborem případů jsme mohli obdobně zjistit optimální řešení pro posledních $k$ kotoučů. Pokud $\mathrm{OPT}(k)$ je počet kroků použitých optimálním řešením pro $k$ kotoučů, tak můžeme dostat řešení používající $2(n-k)+\mathrm{OPT}(k)$ kroků tak, že nejdříve setřídíme $n-k$ největších kotoučů algoritmem, který jsme si popsali, a na posledních $k$ kotoučů použijeme optimální řešení. Plný počet bodů jste mohli získat už pro $k=5$, tedy pokud vaše řešení vyžadovalo $123$ dní.

Zlepšit se dá i multiplikativní konstanta. Kdyby vás zajímalo jak, tak si můžete přečíst článek jménem „Bounds for Sorting by Prefix Reversal“1 od Billa Gatese. Pokud by vás zajímalo optimální řešení pro konkrétní instanci problému a ne pouze omezení shora, tak vězte, že tento problém je NP-těžký. Důkaz si můžete přečíst v článku jménem „Pancake Flipping Is Hard“2.

Kuba


1) https://people.eecs.berkeley.edu/ christos/papers/GP79.pdf

2) https://arxiv.org/abs/1111.0434