Čtvrtá série patnáctého ročníku KSP

Řešení úloh

• 15-4-1: Archiv
• 15-4-2: Permutace podruhé
• 15-4-3: Koberec
• 15-4-4: Písaři
• 15-4-5: Haskell

15-4-1 Archiv (Zadání)

Nejdříve vyvraťme několik mýtů, jimiž byla některá z vašich řešení obestřena:

• Časová složitost bublinkového třídění (tj. algoritmů typu „najdu dvojici po sobě jdoucích prvků, která je ve špatném pořadí, prohodím je; to dělám tak dlouho, než je posloupnost setříděná“) není logaritmická (to by znamenalo O(log n)), ani není O(n log n), je totiž kvadratická – O(n²).
• Ani QuickSort (alespoň ve formě, ve které se běžně programuje) nemá složitost O(n log n) – v nejhorším případě (někdy to dokonce bývají setříděné nebo opačně setříděné posloupnosti) dosahuje O(n²); hezkou časovou složitost O(n log n) má pouze v průměrném případě.
• Špatně zatříděné prvky nejsou nutně ty, které jsou menší než předchozí prvek – například pro posloupnost typu 1, N, 2, 3, … , N-2, N-1 bychom totiž za špatně zatříděné prohlásili prvky 2… N-1, i když ve skutečnosti je špatně zatříděn pouze prvek N.

Tak to by bylo, s čistou myslí se teď pustíme do našeho vlastního řešení. Nejdříve si všimněme, že kdybychom věděli, kterých k spisů jsou ty špatně zatříděné, stačilo by je z posloupnosti odstranit (takže by zbyla setříděná posloupnost), zvlášť si je setřídit (to zvládneme v čase O(k· log k) například tříděním sléváním čili MergeSortem) a poté obě setříděné posloupnosti slít dohromady (to dokážeme v lineárním čase, vlastně to je dokonce podprogram MergeSortu).

Jak jen ale ty potvorky toulavé špatně zatříděné najít? Inu, příklad v úvodu naznačuje, že to nebude jednoduché. Proto to vyřešíme drobným úskokem: jakmile narazíme na dvojici sousedních prvků ve špatném pořadí (budeme jí říkat špatná dvojice), tak ji odstraníme a budeme to opakovat tak dlouho, dokud takové dvojice existují. Tím určitě v lineárním čase odstraníme všechny špatně prvky a možná i některé dobré, ale těch nebude mnoho: z každé špatné dvojice je alespoň jeden prvek špatný (protože každé dva dobré prvky jsou určitě ve správném pořadí), celkově tedy odstraníme maximálně 2k prvků a původní odhad časové složitosti bude nadále platit.

Časová složitost tedy bude O(n+k· log k) a prostorová O(n). A asymptoticky lépe to určitě vyřešit nelze, protože oněch k zatříděných prvků potřebujeme najít (to nelze rychleji než lineárně k n) a rovněž setřídit, což pro změnu nelze rychleji než pomocí k log k operací.

Jako zákusek servírujeme ještě program v Céčku umíchaný přesně podle našeho algoritmického receptu.

Program

Martin Mareš

15-4-2 Permutace podruhé (Zadání)

Nejdříve si definujme k-tou mocninu permutace P, a to rekurzivně následujícím předpisem: P¹[i]=P[i] a P^k+1[i]=P^k[i]. Cyklem permutace P nazveme takovou posloupnost i, P¹[i], P²[i], … , P^k-1[i], že P^k[i]=i a k je nejmenší číslo s touto vlastností. Číslo k je pak délka cyklu i, P¹[i], P²[i], … , P^k-1[i]. Zřejmě každý index i leží v právě jednom cyklu permutace P.

Podívejme se nyní, jak vypadá druhá mocnina permutace P. Cyklus i₁,i₂,… ,i_k permutace P, který má lichou délku, bude odpovídat cyklu i₁,i₃,i₅,… ,i_k,i₂,… ,i_k-1 v permutaci P². Na druhou stranu, z cyklu i₁,i₂,… ,i_k permutace P sudé délky vzniknou umocněním dva cykly poloviční délky: i₁,i₃,… ,i_k-1 a i₂,i₄,… ,i_k. Obecně tedy, pokud Q je druhou mocninou nějaké permutace P, pak počet jejích cyklů sudé délky je sudý (sudé cykly mohou vznikat jen štěpením cyklů dvojnásobné délky).

Je-li k liché, je situace o něco složitější, neboť kromě toho, že cyklus liché délky může vzniknout rozpadem cyklu dvojnásobné délky, může také vzniknout z jednoho cyklu téže délky. Označme si nyní μ_k(K) počet konfigurací, ze kterých může vzniknout K zadaných cyklů délky k. Zřejmě, μ_k(1)=1 a μ_k(2)=k+1 (buď oba cykly vznikly rozpadem většího cyklu, to nám dává k způsobů, anebo ze dvou cyklů téže délky, tu máme jediný způsob). Obecně pak máme následující rekurzivní vztah pro K≥ 2:

Buď uvažovaný cyklus nevznikl rozpadem z většího cyklu (první sčítanec) anebo vznikl a v tom případě je K-1 možnosti, který jiný cyklus vznikl z téhož velkého cyklu, a k možností, jak byly tyto dva cykly do sebe „zakousnuty“. Mimochodem, obdobně můžeme pro k sudé psát: μ_k(1)=0, μ_k(2)=k a μ_k(K)=k(K-1)μ_k(K-2) pro K≥ 2.

Počet permutací P takových, že P² je permutace Q, se určí vynásobením počtu konfigurací pro všechny možné délky cyklů.

Navrhnout algoritmus pracující v čase O(N), kde N je velikost permutace, je nyní již snadné. Nejprve spočítáme počet cyklů jednotlivých délek: Nejdříve všechny indexy 1 až N označíme. Pak procházíme postupně indexy od 1 do N. Pokud narazíme na označený index, určíme délku jeho cyklu a všechny prvky tohoto cyklu odznačíme. Časová složitost této fáze algoritmu je úměrná součtu délek všech cyklů permutace a délce permutace, tedy je lineární. V druhé fázi pak spočítáme čísla μ_k(K) pro všechny délky k cyklů zadané permutace a jejich součin. Výpočet čísla μ_k(K) lze provést rekurzivně v čase O(K), a tedy časovou složitost druhé fáze algoritmu lze odhadnout počtem cyklů permutace a tedy je opět O(N). Paměťová složitost algoritmu je též O(N), neboť potřebujeme pole na uložení permutace.

Program

Dan Kráľ

15-4-3 Koberec (Zadání)

Naisrep seděl na balkóně své vily a znuděně pozoroval cvrkot městečka pod sebou. Od doby poslední molové kalamity v dílně ho šití koberců značně stravovalo – občas jsou prostě roky, kdy se vám nechce nic dělat. Nápad na nový vzor se vzkázal býti triviálně řešitelným pomocí rekurze a krom maličkého detailu představovala četba návrhů na řešení vzoru koberců cvičení v gramatice rodného jazyka. Z letargie snícího odpoledne ho probudila až želva maně užírající nohu židle, v níž trůnil. Ve vědomí se mu objevil obraz Achilea nemilosrdně stíhajícího požíračku, jenž briskním způsobem vyřešil i ten poslední detail – šlo totiž o to, zda-li postupně rostoucí rohy vnořených čtverců nemohou přesáhnout kvadrant, v němž sídlili jeho předchůdci. Klíčem mu byl vzorec pro součet geometrické řady – podobně jako želva, jíž se nikdy nepovede půlením vzdáleností dostat až na konec dráhy, čtverce nikdy nepřesáhnou svůj kvadrant (^*) (v tomto případě se v nekonečnu přesně dotknou jedné z os).

A jak tedy vypadá rekurze v prvním plánu ?

1. Situace: Počátek souřadného systému je uprostřed největšího čtverce. Začínáme s délkou (strany) čtverce n a rekurzí hloubky 0.
2. V i-tém rekurzivním zanoření ověříme, jestli bod leží uvnitř čtverce délky n/2ⁱ. Pak lyže nikoliv, jdeme rovnou do další rekurze, bez inkrementace čverců obsahujících bod.
3. Zjistíme, ve kterém kvadrantu se nachází zkoumaný bod a rekurzivně se pustíme do tohoto kvadrantu s tím, že posuneme počátek souřadného systému doprostřed centrálního čtverce daného kvadrantu. Tím jsme v situaci analogické k 0.

Pozorování: Díky (^*) vím, že žádný z vnořených čtverců sousedního kvadrantu nezasáhne do zkoumaného, a tedy jednoznačnou volbou v 2) nepřijdu o další řešení. Dále si všimněme, že volbou pouze jediného z kvadrantů, o který se kdy budu zajímat, je možné místo rekurze s paměťovou složitostí O(log n) použít while cyklus, mající paměť O(1).

Druhé pozorování – struktura rozmístění čtverců je symetrická podle obou os. Místo složitého rozhodování, ve kterém kvadrantu se zrovna šťourat, překlopíme hledaný bod vždy do prvního kvadrantu. Tím jsme se vyhnuli i diskusi, kam s bodem o souřadnicích [0,0] – šlo by případně v tomto okamžiku výpočet zarazit (žádný další čtverec se do nuly nedostane).

Časová složitost odpovídá hloubce zanoření rekurze neboli počtu vydělení, kterým se dostanu ke dvojkovému čtverci, neboli logaritmu n. Některým z vás činilo obtíž určení paměťové složitosti v případě rekurze – neuvědomili si totiž, každé nové zanoření do rekurzivní fce vezme dalších O(1) na proměnné uvnitř zásobníku.

Kvůli další skupině řešitelů se neodpustím osvětovou poznámku, že log(c₁·n) = log c₁ + log n = c₂ + log n a log_a n = log n / log a = c· log n – tj. ve všech těchto případech lze psát O(log n) bez diskusí, co s konstantami.

Psychologický postřeh dí, že fanatazie není v rukou lidí, ale lidé jsou v rukou fantazie; pročež mi bylo dáno neudržet se a pro otrlejší nadšence napsat trojřádkovou verzi zdrojáku, za jejíž údernost zaplatíme právě nešťastným logaritmem v paměti.

Program

Pavel Šanda

15-4-4 Písaři (Zadání)

Naše úloha je trochu podobná zadání úlohy o knihovně z MO-P. Je tu však jeden rozdíl – zde není počet stran scénáře omezený, může jich být klidně 2²ⁿ. Řešení „vezmi všechny kapacity jednoho písaře od 0 do součtu všech stran a zkus, jestli to tak půjde rozdělit“ tudíž bude pomalé i při metodě půlení intervalu. (Argument, že na zápis takového čísla bychom potřebovali tak jako tak 2ⁿ bitů, ponechme stranou, pracujeme v ideálním modelu.)

My na to půjdeme dynamickým programováním. Budeme počítat dvojrozměrné pole P velikosti K×N, kde hodnota P_i,j znamená nejmenší možný počet stran, zpracovávaný nejvytíženějším z písařů 1,…,i, kteří mají za úkol přepsat scénáře 1,…,j. Pole budeme plnit po řádcích, tj. pro počet písařů i spočítáme hodnoty P_i,j postupně pro j=i,…,N. Na konci výpočtu bude hledaná hodnota v P_K,N a když už ji známe, jedním průchodem seznamem stran a hladovým přidělováním scénářů jednotlivým písařům vypíšeme rozdělení.

Zbývá vyřešit, jak najít rychle číslo P_i,j. Zřejmě P_0,*=∞ (0 písařů potřebuje nekonečně mnoho času) a P_*,0=0 (0 scénářů lze opsat za nulový čas). Když máme k dispozici i písařů na j stran, vyzkoušíme nechat i-tému písaři postupně scénáře l až j pro všechny l=i,…,j (pro i-1 písařů a scénáře 1,…,l už to máme spočítané), a vybereme tu nejlepší variantu. Formálně zapsáno

A ejhle – my pracujeme jen s hodnotami pro i-1 a i písařů. Z celé tabulky si stačí pamatovat pouhé dva řádky a rázem máme paměťovou složitost O(N). Čas bude O(N²·K), vyplňujeme tabulku K·N a na jednom čísle strávíme O(N) času. Zkusíme ale zlepšit i tohle. Všimneme si následujících dvou skutečností:

• S přidáváním dalších scénářů současná optimální hodnota nikdy neklesne.
• Když v optimálním řešení pro j-1 scénářů poslední písař začíná scénářem číslo l, v optimálním řešení pro j scénářů stačí zkoumat takové varianty, kdy poslední písař začíná nějakým scénářem číslo l'≥ l.

Při výpočtu P_i,j tedy začneme zkoumat jen od místa, kde skončilo číslo l pro j-1 scénářů a zkoumat přestaneme, když optimální hodnota pro konfiguraci s posledním písařem l+1,…,j přestane klesat. Jinými slovy – jakmile optimální hodnota pro písaře 1,…,i-1 začne přerůstat velikost i-tého písaře, nemá význam dále pokračovat.

Při vyplňování celého řádku tedy postupně index l proběhne hodnoty 1,…,N, strávíme tak nad řádkem zhruba N+N operací a celková časová složitost bude O(N·K). V programu jsou pak pole indexována od jedničky, to aby se co nejvíce podobal našemu popisu.

Program

Tomáš Valla

15-4-5 Haskell (Zadání)

Do zadání této úlohy se bohužel vloudilo pár nepřesností a naopak se do ní několik podstatných detailů nedostalo, takže úloha byla o dost obtížnější, než jsem původně zamýšlel, a navíc v řešení bylo potřeba použít několik netriviálních triků.

Základní myšlenka je jednoduchá – pro každou funkci vytvoříme sekvenci instrukcí, která ji vyhodnotí, tj. provádí operace dané funkcí tak dlouho, dokud není výsledek buď číslo, nebo thunk s příliš málo parametry na to, abychom ho mohli vyhodnocovat dál. Pro každou konstrukci, kterou potřebujeme vyhodnocovat, máme k dispozici nějaké instrukce – IExecute a IReturn pro volání funkcí, ICExecute pro case, …

Problémy nastanou, když chceme, aby vše fungovalo jako v Haskellu, tj. abychom měli zajištěnu línost vyhodnocování a sdílení. U volání funkce nemůžeme nechat vyhodnotit její parametry a pak s nimi zavolat funkci; například f x y = y, f (error "chyba") 1 má mít jako výsledek 1, ne skončit s chybou. Obdobný problém máme pro výrazy ve větvích case výrazu. Proto ve všech těchto případech musíme vytvořit thunky, které budou vyhodnoceny, až budou-li potřeba. Bylo by poměrně obtížné to dělat přímo při kompilaci, proto nejprve program zjednodušíme tak, že všechny argumenty funkcí a výrazy ve větvích ifů jsou buď číselné konstanty, nebo proměnné (to můžeme vždy udělat vytvořením pomocných funkcí a definic nových proměnných v let-výrazech (této operaci se říká flattening – „zplošťování“)).

Obdobným trikem se zbavíme i lokálních funkcí – uděláme z nich globální; tady je potřeba dát pozor na to, že lokální funkce mohou přistupovat k lokálním definicím v dané funkci, tedy je potřeba je nově vytvořeným globálním funkcím poslat jako konstanty. Lokální definice tedy budou pouze tvaru d = f x y z, kde f je globální funkce, případně d = x nebo d = 5.

Například funkce

f x y = let a z = fa (x + y) z b
            b t = fb (x - y) t a
         in g (a x) (b y)

f x y = let a = fa' xpy b
            b = fb' xmy a
            xpy = plus x y
            xmy = minus x y
            p1 = a' a x
            p2 = b' b y
         in g p1 p2
plus x y = x + y
minus x y = x - y
a' a x = a x
b' b y = b y
fa' xpy b z = fa xpy z b
fb' xmy a t = fb xmy t a

Nyní se již můžeme odvážně pustit do překladu jednotlivých příkazů. Kromě drobné technické komplikace u case způsobené tím, že ICExecute je poměrně nešikovně navrženo, narazíme na problémy až u našeho oblíbeného příkazu let. Podívejme se na volání fa' a fb' ve výše uvedeném příkladu. Abychom vytvořili thunk pro fa', potřebujeme mu jako argument dát odkaz na thunk pro fb' a naopak – vypadá to, že jsme se zacyklili. Našťestí máme instrukci IRewrite; my si tedy nejprve vytvoříme místa v paměti, kde budeme mít uloženy tyto thunky, pak si je vytvoříme tak, aby se jejich parametry odkazovaly na tato místa a nakonec je pomocí IRewrite na tato místa nakopírujeme.

Druhý problém je zajištění sdílení. Pro lokální proměnné je to jednoduché – stačí za každé volání IExecute přidat volání IRewrite, které původní thunk nahradí novou hodnotou; vzhledem k tomu, že jak v registrech, tak v thuncích máme pouze ukazatele na data, nahradíme tímto tuto hodnotu všude, kam byla zkopírována. My bychom toto ovšem chtěli zajistit i pro globální proměnné; to uděláme snadno tak, že celý program obalíme do jednoho velkého letu.

No a s těmito poznatky je již sepsání kompilátoru záležitost tří odpolední a 600 řádek kódu.

Program

Zdeněk Dvořák