Pátá série devatenáctého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 19-5-1: Útěk
- 19-5-2: Nesnadné dělení
- 19-5-3: Hamtyhamtyhamty
- 19-5-4: Lodní mrazáky
- 19-5-5: Praktická úložka
- 19-5-6: Prolog
19-5-1 Útěk (Zadání)
Na začátek jedna metoda jak neutíkat: Je pravda, že síť MHD připomíná graf, ale udělat co stanici, to uzel a co spoj, to hranu opravdu nejde. Pokud bychom nebyli limitováni penězi (nebo nebyli limitováni časem), Dijkstrův algoritmus by fungoval. Jenže my jsme limitováni obojím – a ani „projdeme všechny cesty“, ani „když dojdou peníze, zkusíme to jinak“ k řešení v polynomiálním čase nevedou.
Je možné stvořit jakýsi „časoprostorový“ graf, ve kterém každá zastávka bude zastoupena tolika vrcholy, kolik z ní odjíždí spojů, a hrany budou reprezentovat autobusy (s váhou ohodnocenou dolárky) a čekání (s váhou nulovou). Na časoprostorovém grafu již Dijkstrův algoritmus najde potřebné spojení, a to i v rozumném čase. (Ano, mohli bychom stvořit i „dolaroprostorový“ graf.)
Programovat Dijkstrův algoritmus se všemi optimalizacemi je ovšem dost práce, a navíc je náš časoprostorový graf poměrně speciálního tvaru. Nabízí se proto jednodušší řešení:
Události buďtež odjezdy autobusů a jejich příjezdy. Setřídíme je podle času vzestupně (umíme to v konstantním čase, protože minut ve dni je 1440). U každé linky a každé stanice si budeme pamatovat, jestli je dostupná v tomto čase, a případně za jakou cenu. Nedostupným linkám-stanicím můžeme prostě přiřadit nekonečno dolárků.
Výpočet bude probíhat tak, že půjdeme s časem od půlnoci dopředu, a v každém kroku zpracujeme všechny události. Pokud autobus odjíždí z dostupné stanice, zkontrolujeme, jestli cena linky náhodou není vyšší, než kdybychom zaplatili při nástupu z této stanice. Pokud je vyšší, snížíme cenu linky.
Při příjezdu zkontrolujeme, jestli cena linky plus cena, kterou musíme zaplatit za cestu, není nižší než cena stanice. Pokud ano, snížíme cenu stanice.
Ve chvíli, kdy se cena cíle stane nižší než limit v dolárcích, máme hledané spojení a můžeme ukončit výpočet. Jdeme s časem dopředu, takže spojení určitě bude nejrychlejší.
Časová složitost bude lineární s velikostí vstupu, protože událostí je tolik jako součet zastávek na všech linkách (to je velikost vstupu) a každou zvládneme zpracovat v konstantním čase. Pokud by časy byly zadány reálnými čísly, časová složitost by kvůli třídění událostí stoupne na O(Z log Z), kde Z je součet zastávek na všech linkách, tj. velikost vstupu.
19-5-2 Nesnadné dělení (Zadání)
Většina řešitelů nenechala Isabelu s Přesprstem na holičkách, a pokud to bylo možné, tak peníze na přesné poloviny rozdělila. Ať už dynamicky s pomocí kuchařky nebo exponenciálně. Algoritmy, které nejdříve bankovky setřídily a pak se je snažily hladově rozdělit jedním průchodem na dvě části, bankovky rovněž sem tam rozdělily na dvě poloviny. Bohužel, občas jedna z nich byla větší než ta druhá :–) No, a jak mělo vypadat správné řešení?
Nejdříve si úlohu přeformulujeme trochu obecněji. Máme posloupnost čísel S (hodnot bankovek) a chceme z ní vybrat podposloupnost, která bude mít nějaký konkrétní součet s (v našem případě je s rovno polovině celkového součtu S).
Jako první každého určitě napadne jednoduchý algoritmus: Vyzkoušíme všechny možné podposloupnosti, každou zkusíme sečíst a podíváme se, jestli má „správný“ součet. Pokud má součet s, tak jsme rovnou našli jednu z vhodných podposloupností a tím i vhodné rozdělení bankovek. Pokud žádná podposloupnost nemá součet s, máme jistotu, že bankovky rozdělit nepůjdou.
Tento algoritmus má jednu vadu. Každý prvek ve vybrané podposloupnosti buď je, nebo není, takže nepotřebujeme tým matematiků, abychom viděli, že časová složitost bude exponenciální, tj. O(2N).
Teď se připravte na to, že přijde špatná zpráva: Problém výběru podposloupnosti s daným součtem je NP-úplný, takže pro obecně zadaná čísla je výše uvedený algoritmus to nejlepší, co umíme. Avšak nezoufejte – záchrana se blíží.
Náš problém naštěstí není tak úplně obecný. Využijeme faktu, že velikosti bankovek (a tedy i čísla z našich posloupností) jsou omezena nějakým relativně malým číslem M. Z toho vyplývá, že náš hledaný součet s bude nejvýše O(M ·N), takže můžeme nasadit rafinovanou metodu, které se říká dynamické programování (viz kuchařka).
V první fázi algoritmu nejprve sečteme všechny prvky (resp. bankovky) a proměnnou s položíme rovnou polovině tohoto součtu. Pokud je součet lichý, můžeme rovnou skončit a oznámit nedočkavému uživateli, že tyto bankovky opravdu rozdělit na polovinu nejdou. Dále si připravíme pole V indexované od 1 do s, které je na počátku celé inicializované na samé nuly. Postupně si do něho budeme ukládat bankovky následujícím způsobem:
Nyní budeme brát bankovky jednu po druhé a s každou provedeme následující. Projedeme celé pole V, a pokaždé když narazíme na nenulový prvek, vezmeme jeho index i (přesně tak – index představuje vlastně celkový dosažený součet), přičteme k němu hodnotu aktuální bankovky b a na pozici s nově získaným indexem (i + b) uložíme naši bankovku (třeba jako její index v posloupnosti S). Co jsme tím vlastně udělali? Nalezený nenulový index i nám říká, že existuje výběr z bankovek (z těch, které předchází b), které mají součet i. Když k nim přidáme bankovku b, tak umíme poskládat i součet i + b, takže si na tento index uložíme poslední bankovku, která tento součet tvoří. Pokud je součet i + b ≥ s, pak jej do pole neuložíme, protože už nás nezajímá (je příliš velký). Stejně tak pokud na pozici i + b už je zapsaná jiná bankovka, necháme ji tam (abychom si neničili, co už máme spočítáno).
Při výše popsaném průchodu polem V musíme postupovat vždy odshora dolů, jinak by mohl nastat zajímavý efekt. Představte si, co by se stalo, kdybychom postupovali opačně a přidávali např. bankovku s hodnotou 1 do prázdného pole. Na první pozici bychom zapsali 1. Následně bychom se podívali na 1. pozici, přičetli hodnotu bankovky (tedy 1) a zapsali ji – na pozici 2. Takto bychom krásně vyplnili celé pole, tj. bankovku 1 bychom vlastně použili opakovaně.
Poslední, co zbývá popsat, je jak ze získaných hodnot pole V zjistit rozdělení bankovek. Nejprve se podíváme na položku V[s]. Pokud je nulová (není tam uložena žádná bankovka), tak víme, že neumíme vybrat podposloupnost se součtem s. Dále postupujeme jednoduše. Bankovku na pozici V[s] vypíšeme a podíváme se, jak složit podposloupnost se součtem i = s - V[s]. Ale poslední bankovka, která do takové podposloupnosti patří, se přece nachází na pozici V[i]. Tak ji vypíšeme a opět si položíme i = i - V[i]. Takto pokračujeme, dokud nevypíšeme všechny prvky (tj. i nám neklesne na nulu).
Jak již bylo naznačeno, časová složitost algoritmu bude O(N ·s), kde N je počet bankovek a s jejich součet. Paměťová složitost je o trochu menší, a to sice O(N + s). Dá se nahlédnout, že pokud bychom neměli žádné omezení na velikost součtu s, byla by časová složitost exponenciální k velikosti vstupu. Na to, abychom zakódovali číslo s, potřebujeme B = log2s bitů, proto by časová složitost byla O(s) = O(2B), tedy exponenciální.
Snad se vám z toho příliš nezamotala hlava, a pokud ano, tak vyražte někam ven – třeba k vodě nebo na zmrzlinu a nezapomeňte si vzít s sebou „správný“ obnos bankovek :o))
19-5-3 Hamtyhamtyhamty (Zadání)
Nejdříve si předvedeme jednoduchou neprohrávající strategii, tedy takovou, se kterou pokaždé buď vyhrajeme, nebo aspoň remízujeme. Obarvíme si 2n čísel, o která hrajeme, střídavě černě a bíle. Všimneme si, že pokud začínáme černým (bílým) číslem, musí soupeř vždy sebrat bílé (černé) a my dostaneme opět pozici, která má na jednom kraji černé a na druhém bílé číslo. Můžeme tedy snadno soupeře donutit k tomu, aby posbíral všechna bílá nebo všechna černá a my ta druhá. My se samozřejmě rozhodneme podle toho, která mají větší součet, a tím vyhrajeme. Pokud se nám stane, že obě skupiny čísel mají součet stejný, vede naše strategie alespoň k remíze.
Zadání úlohy po nás ovšem chce, aby naše strategie vyhrála, kdykoliv je to možné. Je to opravdu tak, že kdykoliv černobílá strategie remízuje, je remíza nevyhnutelná? Bohužel nikoliv – například pro čísla 1,2,4,2,1,2 můžeme odebráním dvojky dostat soupeře do stavu 1,2,4,2,1, ze kterého musí odebrat jedničku (teď vedeme o jedna), a pokud spustíme černobílou strategii až teď, určitě o svůj náskok nepřijdeme. Tento problém se mnozí z vás pokoušeli obejít tím, že po každém tahu testovali, jestli nezačal být součet černých a bílých různý (to v našem příkladu nepomůže, protože rozhodující je už první tah), nebo třeba při rovnosti odebírali větší číslo (tedy je o něco těžší přijít s protipříkladem, ale 4,2,1,6,8,5 zabere). Takových fíglů se dá vymyslet spousta, ale neznám žádný, který opravdu funguje.
Půjdeme na to tedy trochu jinak: Nebudeme se snažit jenom vyhrát, ale dokonce soupeře obrat o co nejvíce, zkrátka co nejvíce nahamtat – chceme tedy, aby rozdíl mezi tím, co získáme my a co získá soupeř, byl co největší. Když si označíme zadaná čísla A0,… ,AN-1, budou všechny pozice v průběhu hry vždy nějaké intervaly Ai,… ,Ai+ℓ-1. Pro každý takový interval si spočítáme hodnotu Hi,ℓ, která nám řekne, kolik je do konce hry schopen nahamtat ten, kdo je v tomto okamžiku na tahu. (Ti zkušenější už samozřejmě správně větří dynamické programování.)
Všimneme si, že Hi,1=Ai (pokud už je ve hře jen jediné číslo, co zbývá, než ho sebrat). Pokud je interval delší, máme dvě možnosti, jak hrát:
- Buďto sebereme Ai a soupeři předáme Ai+1,… ,Ai+ℓ-1. Tehdy soupeř, pokud bude hrát nejlépe, jak může, nahamtá Hi+1,ℓ-1, pročež my můžeme celkově nahamtat Ai-Hi+1,ℓ-1.
- Nebo sebereme Ai+ℓ-1 a předáme Ai,… ,Ai+ℓ-2, a proto nahamtáme Ai+ℓ-1-Hi,ℓ-1.
Z těchto dvou možností si samozřejmě vybereme tu, ve které nahamtáme víc. Platí tedy:
Navíc hodnoty pro úseky délky ℓ počítáme z hodnot pro úseky délky ℓ-1, takže stačí postupovat indukcí od nejmenšího ℓ k největšímu. Podle H0,n pak okamžitě poznáme, jestli je pro nás hra vyhraná nebo prohraná, a v každém stavu hry snadno zjistíme, zda máme odebrat levé nebo pravé číslo podle toho, která z možností nám dala hodnotu Hi,ℓ. Přesně na tomto principu je založen následující program, který v čase a paměti O(n2) pro všechny intervaly spočítá jak Hi,ℓ, tak optimální tah Ti,ℓ.
Ostatně, k témuž výsledku bychom se také mohli dobrat tak, že bychom si napsali rekurzivní funkci, která by počítala Hi,ℓ podle našich vzorečků. Přímočaře naprogramovaná by běžela v exponenciálním čase, ale mohli bychom si v nějakém pomocném poli pamatovat, které hodnoty jsme už spočítali, a nepočítat je znovu. Tak bychom se dostali opět na kvadratickou časovou a paměťovou složitost.
Nechci tedy nikterak podceňovat naši milou Izabelu, ale tipoval bych, že v jejím úspěchu byla přeci jen trocha začátečnického štěstí, a to jí přineslo posloupnosti, na kterých funguje černobílá strategie snadno spočítatelná zpaměti. Konec konců, není divu, náhodný vstup toto s velkou pravděpodobností splňuje. Ať tedy takové máte i vy :-)
Finta na závěr: Kdybychom se na naši úložku dívali jako na programátorskou
úlohu místo původně zamýšlené jednoduché logické hádanky, mohli bychom se ještě pokusit
snížit nepříjemně vysokou paměťovou náročnost. Na co tu paměť vlastně potřebujeme?
Samotný výpočet hodnot hodnot Hi,ℓ si vystačí s hodnotami Hj,ℓ-1
a na všechny menší délky můžeme zapomenout. Ovšem potřebujeme si zapamatovat,
který tah byl ve které pozici optimální, abychom pak dokázali při libovolném
vývoji hry zjistit, jak máme hrát. Jak ušetřit tady? Místo toho, abychom si
pamatovali všechny stavy hry, můžeme si třeba uložit jen stavy s délkou
úseku dělitelnou nějakým k, a jakmile se dostaneme do intervalu délek mezi
ki a k(i+1), spočítáme z uložených výsledků pro délku ki výsledky pro
všechny mezilehlé délky. Tak algoritmus příliš nezpomalíme (každou pozici
počítáme jen dvakrát) a paměť zredukujeme na O(kn+(n/k)n), tedy při volbě
k=√n na O(n√n) = O(n3/2). Mezilehlé délky ale můžeme
podrozdělovat stejným způsobem a pokud do sebe zasunutých podrozdělení
bude p, vyjde, že optimální je podrozdělování na n1/p částí, časová
složitost O(n2p) a prostorová O(n1+1/p). Mezním případem je
podrozdělení na dvě části, které nám dá hloubku O(log n), čas O(n2 log n) a paměť O(n log n). To je poměrně univerzální trik, kterým jde u mnoha
úloh ušetřit spousta paměti za cenu mírného (obvykle logaritmického) zpomalení.
19-5-4 Lodní mrazáky (Zadání)
Nejprve si všimněme, že jeden mrazák nám stačit nebude. Kdybychom použili pouze jeden, věci by se do něj nastrkaly, ty nejstarší by skončily vespod a už by se k nim nikdo nedostal.
Proto použijeme mrazáky dva, a aby se nám to nepletlo, stanovíme si jistá pravidla na uspořádání potravin.
- V prvním mrazáku, říkejme mu třeba příchozí, budou potraviny seřazeny tak, že čím hlouběji v mrazáku budeme, tím starší budou.
- Druhý mrazák, budiž nazýván odchozí, bude seřazen přesně naopak, tedy čím hlouběji, tím novější potraviny.
- Libovolná potravina v odchozím mrazáku bude starší, než libovolná v příchozím.
Teď zbývá vytvořit operace ulož a sněz tak, aby žádnou z předchozích podmínek neporušily. Operace ulož je jednoduchá, prostě vložíme potravinu do příchozího mrazáku. Tím určitě neporušíme podmínku 1) - tato potravina je určitě novější, než vše, co bylo v mrazáku předtím a přišlo to nahoru, ani podmínku 2) - odchozího mrazáku se vůbec nedotkneme, ani podmínku 3), protože tato potravina je určitě novější, než cokoliv v odchozím mrazáku.
Pokud bude v odchozím mrazáku alespoň jedna potravina, je operace sněz také triviální. Potravina navrchu tohoto mrazáku je nejstarší, protože je starší než cokoliv pod ní a je starší než cokoliv v příchozím mrazáku. Tudíž ji stačí jen vzít. Toto samozřejmě neporuší žádnou z podmínek, odebráním libovolné potraviny se nic zkazit nedá.
Co ale v případě, že odchozí mrazák zeje prázdnotou? Předpokládejme, že je alespoň jedna potravina v příchozím mrazáku, protože jinak by na lodi panoval hladomor a nebylo by možné provést operaci sněz. Celkově nejstarší potravinou je tedy nejstarší potravina v příchozím mrazáku, která je dle podmínky 1) vespod. Proto přeházíme všechny potraviny z příchozího do odchozího mrazáku. Tím se otočí pořadí potravin, takže nejstarší bude navrchu a postupně budou novější a novější. Tím je splněna třetí podmínka a zařízeno, že lze provést operaci sněz tak, jak byla popsána výše. První a druhá jsou splněny také, protože příchozí mrazák je prázdný.
Nyní, kolik se provede operací, tedy jaká je časová složitost? Každou potravinu, která projde úschovou v podpalubí, čeká uložení a vyndání z každého ze dvou mrazáků. Celkem tedy 4 operace. Pro zpracování N potravin bude potřeba 4N operací, z nichž právě 2N budou pomocné. Splnili jsme tedy kapitánovu žádost, aby pomocných operací bylo O(N).
Paměťovou složitost můžeme brát buď dle počtu mrazáků, které potřebujeme 2, nebo podle počtu obsazených mrazících pozic, ale protože každá potravina může být v jeden okamžik uložena nejvýše jednou, je paměťová složitost lineární.
19-5-5 Praktická úložka (Zadání)
Jak už to tak v životě bývá, způsobů řešení této úlohy je více. Zde si popíšeme jeden velice jednoduchý a naznačíme některé další možné. Posaďte se, prosím, na svá místa, připoutejte se a během startu nekuřte.
Náš postup je založen na známém třídícím algoritmu merge-sort, neboli třídění pomocí slévání. Tento algoritmus pracuje na principu rozděl a panuj. Tříděnou posloupnost rozdělí na dvě poloviny (tedy podúlohy menšího rozsahu), které setřídí rekurzivním použitím stejného algoritmu. Setříděné poloviny následně slije do jedné posloupnosti.
Pro lepší pochopení našeho algoritmu si ještě raději zopakujeme průběh slévání. Řekněme, že máme dvě vzestupně setříděné posloupnosti (uložené jako pole) A a B a chceme je slít do jedné opět vzestupně setříděné posloupnosti C. Vytvoříme si indexy a, b a c, které inicializujeme tak, aby ukazovaly na první prvky jednotlivých posloupností (tj. a ukazuje na první prvek A atd.). Dokud se index a, nebo b nedostane mimo rozsah jeho posloupnosti, budeme provádět následující krok: Porovnáme prvky A[a] a B[b], menší z nich zkopírujeme do C[c] a posuneme index v poli s menším prvkem na další prvek v posloupnosti. Rovněž posuneme c na další volné místo ve výsledné posloupnosti. Když některý z indexů (a, nebo b) dojede za konec své posloupnosti, algoritmus končí, avšak ještě je třeba dokopírovat zbývající prvky z druhé posloupnosti (z té, která ještě nebyla zpracována celá). Např. pokud a dojede za konec A, musí se ještě zpracovat zbytek posloupnosti B.
Nyní zbývá rozmyslet, jak nám tento algoritmus pomůže při počítání inverzí. Celkový počet inverzí v posloupnosti lze spočítat jako součet počtu inverzí v obou polovinách (tj. v obou menších podproblémech) plus počet inverzí, které objevíme při slévání těchto polovin. Z principu fungování algoritmu je jasné, že nám stačí počítat pouze inverze objevené sléváním (o ostatní se postará rekurze).
Máme tedy algoritmus na slévání dvou posloupností popsaný výše. Jako A si označíme první polovinu tříděné posloupnosti a jako B polovinu druhou. Pokud by bylo uspořádání správné (tj. neobsahovalo by žádné inverze), budou všechny prvky z A menší než prvky B. V každém kroku algoritmu nastává právě jedna z možností:
- A[a] ≤ B[b] – prvek v první posloupnosti je menší nebo roven prvku ve druhé posloupnosti, takže je vše v pořádku a žádnou inverzi jsme neobjevili.
- A[a] > B[b] – prvek v první posloupnosti je větší než prvek ve druhé posloupnosti. To znamená, že B[b] bude ve výsledku zařazen před všechny zbývající prvky v A, což je rozhodně porucha v uspořádání. Každý zbývající prvek v A je tím pádem v inverzi s prvkem B[b], takže nám stačí přičíst k celkovému počtu inverzí počet zbývajících prvků v A.
Časová složitost tohoto algoritmu je stejná jako časová složitost merge-sortu, tzn. O(N · log2N). Paměťová složitost je při vhodné implementaci pouze O(N), neboť nám stačí jedno pole na načtené prvky a jedno pomocné pole na slévání.
Paměťové limity pro jednotlivé testy byly nastaveny tak, abyste mohli použít i staticky alokované pole (jak je to ve vzorovém programu). Na toto pohodlí si ovšem příliš nezvykejte, neboť v dalších praktických úlohách již budete muset alokovat paměť dynamicky podle toho, kolik jí skutečně budete potřebovat.
Závěrem bych ještě zmínil další možné způsoby řešení. Prvním způsobem je použít jiné třídící algoritmy místo merge-sortu. Problém je v tom, že ne každý algoritmus nám bude vyhovovat. Např. quick-sort použít nemůžeme, neboť přehazuje prvky mezi oběma polovinami tříděných dat, a tak nám může během třídění vytvářet inverze, které v původní posloupnosti nebyly. Druhou možností je použít vhodně upravené binární vyhledávací stromy, avšak detailnější popis by si vyžádal poměrně velké množství dalšího textu, a tak si jej dovolím vynechat (kdyby se časem našlo větší množství zájemců o toto řešení, tak jej nějakou formou doplním).
Tímto vám děkuji, že jste se zúčastnili testování praktické úložky. CodEx i já se na vás těšíme v příštím ročníku. CodEx teď zůstane ještě nějakou dobu funkční (pravděpodobně do konce školního roku), takže si ještě můžete vyzkoušet odevzdat nějaká řešení jen tak, nebo si zacvičit v posilovně.
19-5-6 Prolog (Zadání)
1. Nejkratší program
Ukázalo se, že není problém vytvořit krátký program, ale vytvořit funkční program. Řešení, která cyklí při hledání neexistujícího prvku, prostě nemohou získat víc než půl bodu. Při tvoření krátkého programu jste mohli zvolit několik cest, záleželo na tom, jak moc jste chtěli používat vestavěné predikáty Prologu. Všeobecně ale platilo, že nejkratší programy bylo možné napsat na jeden predikát (na jeden řádek).
2. Fronta
Toto cvičení vás mělo navést na řešení pomocí rozdílových seznamů, což většina řešitelů pochopila. Správných řešení ale bylo málo. Prohlédněte si tedy autorské řešení.
3. Expertní systém
Protože se jedná o větší program, ve kterém je potřeba si pořádně rozmyslet datové struktury, spolupráci s uživatelem a jiné záludnosti, a protože se našlo jenom několik odvážlivců, rozhodla jsem se nešťourat do syntaktických chyb a jiných nedostatků. Pokud myšlenka vypadala alespoň trochu použitelně, pokud autor působil dojmem, že ví, co dělá, a pokud se zdálo, že by se nakonec program dal odladit, připsala jsem plný počet bodů. V této úloze nelze žádné řešení prohlásit za jediné optimální. V autorském řešení najdete jedno z nejjednodušších a nejvíce srozumitelných řešení vytvořené pomocí stromu otázek.