Druhá série třináctého ročníku KSP
Řešení úloh
13-2-1 Sirky (Zadání)
Tato úloha patřila k těm jednodušším a také za ni bylo uděleno docela dost bodů. Stačilo si uvědomit, že za podmínek v zadání není možné odebrat z hromádky počet sirek dělitelný sedmi a naopak každé z čísel 1…6 odebrat lze. Protože nula je násobkem sedmi, bude nám stačit udržovat soupeře na násobcích sedmi – soupeř bude muset odebrat na 7*k+x, 1≤ x≤ 6 a my v následujícím tahu odebereme x, čímž na hromádce zbyde 7*k sirek. Pokud budeme mít tu smůlu, že počet sirek na začátku našeho tahu bude dělitelný sedmi (musel by být i na začátku hry), odebereme jednu sirku a budeme tajně doufat, že soupeř udělá chybu.
Program je teď již jednoduchý, časová složitost je lineární, paměťová konstantní.
13-2-2 Přetlačovaná (Zadání)
Na začátek jedno jednoduché pozorování: „To se nedá zkazit.“
Nejdříve zjistíme, které kameny leží ve stejných řádcích a sloupcích. To můžeme snadno udělat buď pomocí třídění či pomocí hashování, které je v průměrném případě rychlejší. V každém řádku a sloupci pak rozdělíme kameny do dvojic (libovolně). Kameny ve dvojicích si pak představíme jakoby propojené hranou. Hrany budou dvou druhů – vertikální (spojují kameny ve stejném sloupci) a horizontální (spojují kameny ve stejném řádku). Získáme tak graf, kde z každého z vrcholů (kamenů) vedou nejvýše dvě hrany (z každého vrcholu totiž vede nejvýše jedna horizontální a jedna vertikální hrana).
Kameny, které nejsou v žádné dvojici, můžeme obarvit libovolně (máme dovolený rozdíl jedna v počtu kamenů různých barev). Pokud se nám tedy podaří obarvit kameny tak, že kameny ve dvojici budou mít různé barvy, je toto obarvení zřejmě i řešením pro původní úlohu.
Barvíme následujícím způsobem: Vybereme libovolný kámen a obarvíme ho červeně. V jaké komponentě grafu může ležet? Může ležet na cestě nebo na cyklu sudé délky. Cykly liché délky se nevyskytují, protože se v grafu pravidelně střídají vertikální a horizontální hrany a žádné další komponenty existovat nemohou, protože z každého vrcholu vedou nejvýše dvě hrany. Jak cesty, tak cykly sudé délky je možné obarvit jednoduše hladově. Obarvení jednoho kamene jednoznačně určuje obarvení komponenty grafu, ve které leží, a nemá žádný vliv mimo tuto komponentu, takže když jsme s komponentou hotovi, můžeme vybrat libovolný jiný kámen, a začít od začátku.
Protože zjišťování, které kameny leží na stejném řádku a sloupci pomocí hashování, je lineární k počtu kamenů a samotné procházení grafu a barvení též, má výsledný algoritmus lineární časovou složitost k počtu kamenů. Paměťová složitost je též lineární k počtu kamenů.
Program je přímou implementací algoritmu. Snad jediná odlišnost spočívá v tom, že ve skutečnosti žádné dvojice ani graf nekonstruujeme. Prostě vždy vezmeme první neobarvený vrchol v horizontálním či vertikálním směru, na který narazíme.
13-2-3 Kamiony (Zadání)
Nechť N je počet pump, D délka trasy a K velikost nádrže auta. Posloupnost a1,a2,… , aN určuje vzdálenost pump od startu a c1,c2,… ,cN jsou jim příslušné nezáporné ceny nafty. Pro zjednodušení si původní úlohu malinko pozměňme – auto nezačíná s plnou nádrží, ale na startu je pumpa s nulovou cenou nafty. Je zřejmé, že obě úlohy jsou si ekvivalentní.
Nyní už ale k řešení. Každého hned napadne, že by se úloha dala řešit za pomocí dynamického programování. To ale vede k algoritmu s časovou složitostí O(NK2) a paměťovou O(K). Ukážeme si ale hladový algoritmus, který má mnohem lepší časovou složitost.
Je zřejmé, že k projetí celé trasy je třeba natankovat alespoň D litrů nafty. Na druhou stranu je ale zbytečné tankovat víc. Tedy optimální řešení tankuje dohromady přesně D litrů. Dále je očividné, že jedno optimální řešení je takové, při kterém u nejlevnější pumpy natankujeme co nejvíce nafty, ale jen tolik, kolik potřebujeme na dojetí do konce. U druhé nejlevnější zase co nejvíce nafty, ale zase jen tolik, kolik potřebujeme – protože něco už nám mohlo zbýt od nejlevnější pumpy, pokud je před, nebo pokud je za, tak bychom po příjezdu k ní museli naftu „vylít“). Podobně můžeme uvažovat pro třetí, čtvrtou až N-tou nejlevnější. Označme toto jako princip minimality.
Uvažme nyní následující algoritmus, podle kterého budeme čerpat benzín:
- Pokud jsou v dojezdu pumpy s nižší cenou, nakupme jen tolik benzínu, abychom měli mohli dojet do nejbližší z nich.
- Jinak doplňme celou nádrž a zastavme se v nejbližší další pumpě.
- Pokud nejbližší další pumpa je dál, než je dojezd auta úloha nemá řešení.
Tento algoritmus splňuje princip minimality, budeme-li výše uvedený postup používat postupně u všech pump v pořadí vzrůstající vzdálenosti od startu. Následuje zcela neformální náhled, proč tomu tak je: Pokud nám po příjezdu k i-té pumpě zbylo t, t>0 litrů nafty v nádrži, musel nastat bod 2) u nějaké předchozí pumpy a je tedy logické, že jsme u té pumpy vzali více nafty (cena v ní je nižší). Podle bodů 1)–3) tedy v i-té pumpě nakoupíme, co nejvíce nafty, ale pouze tolik, abychom neomezili nákupy u levnějších pump. Výše uvedený hladový algoritmus tedy nalezne optimální řešení. (nepovažujte v žádném případě předchozí řádky za důkaz – ten, by byl poněkud komplikovanější).
Při provádění algoritmu tedy procházíme pumpy podle vzrůstající vzdálenosti od startu a rozhodujeme se podle pravidel 1)–3). Body 2) a 3) umíme rozhodnout v konstantním čase, bod 1) vyžaduje projití několika následujících pump. To by mohlo trvat v nejhorším případě O(N). Proto si pumpy, které jsou v dojezdu, vkládáme do haldy uspořádané podle cen nafty, a tedy vždy můžeme rychle ověřit bod 1). Vložení do haldy nám zabere čas nejvýše O(log N). Operace zjistění pumpy s minimální cenou čas O(1). Před touto operací, ale musíme vždy odebrat pumpy s nižší cenou, kterými jsme již projeli. Odebrání jedné pumpy nám v nejhorším případě zabere čas O(log N). Celkově tedy algoritmus potřebuje čas O(N log N). Paměťové nároky jsou O(N) – na implementaci haldy a uložení všech pump.
13-2-4 Mraveniště (Zadání)
Naším úkolem v této úloze je s málo pamětí nalézt nejkratší
cestu mezi dvěma komůrkami v mraveništi. Vytvořme si funkci cesta,
která bude ověřovat, zda mezi dvěma komůrkami vede cesta nejvýše zadané
délky. Tato funkce obdrží 3 parametry (A,B a d) a
vrátí true, pokud mezi A a B existuje
cesta délky d. Jak bude tato funkce fungovat? Pokud je
d rovné jedné, položí dotaz mravenci obsluhujícímu počítač.
Pokud je d větší než jedna, tak zkusí, zda existuje komůrka C
taková, že délka cesty z A do C je ⌊d/2⌋
a délka cesty z C do B je ⌈d/2⌉.
Jinými slovy pro všechna C od 1 do n (n je počet komůrek) se
tato funkce rekurzivně zavolá
nejprve s parametry A, C a ⌊d/2⌋ a
poté s parametry C, B a ⌈d/2⌉ –
pokud pro nějaké C uspěje, vrátí true, jinak false.
Správnost návratové hodnoty funkce plyne z jejího popisu. Samotný program
nejprve načte počet komůrek (n) a čísla komůrek (K,L), mezi kterými
je třeba najít nejkratší cestu. Pak zavolá funkci cesta s parametry
K, L a d, kde za d bude postupně dosazovat čísla od 1 do n.
Nejmenší d, pro které funkce cesta vrátí true, je délka
nejkratší cesty mezi K a L. Pokud pro žádné d tato funkce nevrátí
true, cesta mezi K a L neexistuje.
Paměťová složitost algoritmu je O(log n), neboť při každém rekurzivním
volání funkce cesta je velikost parametru d poloviční. Časová
složitost našeho algoritmu je O(n(2n)O(log n)) = nO(log n), neboť každé zavolání
funkce cesta
s d alespoň 2 vyústí v 2n dalších zavolání této funkce a hloubka
rekurze je O(log n). Samotný
program pak funkci cesta volá celkem nejvýše n-krát.
Zde by bylo možné dosáhnout (zanedbatelného) zrychlení, pokud bychom
nejmenší d, pro které funkce cesta uspěje, nehledali sekvenčně,
ale metodou půlení intervalu.
Ještě drobný komentář k řešením, která jsme obdrželi: Bohužel většina z nich nesplňovala zadání, neboť jejich paměťová složitost (měřeno nejhorším případem) byla lineární. V zásadě se objevili dva nesprávné postupy řešení: Postup založený na prohledávání do hloubky má paměťovou složitost úměrnou délce hledané cesty, ale její délka může být až počet komůrek! Navíc takovéto řešení je úděsně pomalé (časová složitost O(nn)). Postup založený na prohledávání do šířky (algoritmus vlny) může mít také paměťovou složitost lineární (např. každá komůrka je spojena s každou), ale jeho časová složitost je O(n2) a je tedy lepší než prohledávání do hloubky; zadání úlohy však též nesplňuje.
13-2-5 LISP (Zadání)
Jak si mnozí z vás správně povšimli, zadání úlohy si s námi opět trochu zažertovalo
– příklad uvedený v zadání sice ukazoval správnou činnost funkce cut, ale samotné
volání funkce muselo být zapsáno trochu jinak: strukturu s kódem stromu je potřeba
ochránit před vyhodnocováním (parametry každé funkce se automaticky vyhodnocují,
vzpomínáte?) použítím ' či quote. Pak se nám ovšem nebudou vyhodnocovat nily
a zůstanou ve struktuře v podobě symbolů, což také není dobré. Proto každý nil
nahradíme prázdným seznamem (), který se přečte přímo jako objekt nil,
nikoliv symbol nil. Výsledek ořezávání mohou některé interpretery (konec konců
i ten náš ukázkový) vypsat trochu jinak, protože se budou snažit vyložit si páry
jako části seznamu. To ale vůbec není na škodu, oba zápisy totiž popisují tytéž
lispovské objekty (viz ostatně funkce equal v první sérii).
Samotné oříznutí binárního stromu je velice jednoduché, těžší je již provést to efektivně. My si nejprve vyřešíme snazší problém, a to ořezávání stromu zleva, tedy odstranění všech čísel menších než zadaná hodnota l. Na tuto cestu je ideálním, i když trochu rozmarným společníkem rekurze:
- Pokud je strom prázdný, pak je výsledkem opět prázdný strom.
- Pokud hodnota x uložená v kořeni stromu je menší než l, jak kořen, tak celý levý podstrom jsou mimo rozsah a mají být odříznuty. Výsledkem je tedy pravý podstrom zleva oříznutý hodnotou l.
- Pokud je x≥ l, je jak kořen, tak celý pravý podstrom zaručeně v rozsahu, takže stačí vyměnit levý podstrom za jeho oříznutou verzi.
Zapsáno v Lispu:
(define (cutl tree l)
(if (pair? tree)
(let (
(root (geta tree)) ; kořen
(left (geta (getb tree))) ; levý syn
(right (getb (getb tree)))) ; pravý
(if (< root l)
(cutl right l)
(cons root (cons (cutl left l) right))
)
)
nil ; prázdný strom
)
)
(mimochodem, jelikož netestujeme, zda je strom prázdný, nýbrž
zda jeho kořen je či není pár, bude nám tento program fungovat i pokud
se ve stromě omylem objeví symboly nil).
Analogicky naprogramujeme oříznutí zprava cutr tak, že v celém programu
prohodíme levou a pravou stranu a menšítko nahradíme většítkem. Požadovanou
funkci cut pak získáme snadným složením obou jednostranných ořezání:
(define (cut tree l r) (cutr (cutl tree l) r))
Jelikož na každé hladině stromu provedeme pouze konstantní počet
operací, má naše funkce časovou složitost lineární s hloubkou stromu d
(ovšem pozor, to nemusí znamenat logaritmickou s počtem vrcholů, protože ne každý
vyhledávací strom je vyvážený). V lepší ani doufat nemůžeme,
snadno lze totiž sestrojit příklady, v nichž je nutné změnit některý z vrcholů
na nejnižší hladině a od kořene se k takovému vrcholu nemůžeme rychleji
dostat. Paměťová složitost je rovněž O(d) (pokud do ní nepočítáme vstup),
i když výsledkem naší funkce může být strom s daleko větším počtem vrcholů
– uvědomte si, že mnohé části zkonstruovaného stromu jsou sdílené se stromem
původním a že jsme opravdu přidali pouze O(d) nových objektů (mimochodem,
v Lispu můžeme v každém kroku výpočtu vytvořit nejvýše jeden objekt,
takže paměťová složitost našich programů nikdy nemůže být vyšší než
časová (z toho se na první pohled zdá vymykat primitivum list
(poznámky v tomto spisku už také začínají být poněkud lispovské, není-liž
pravda (dočetl vůbec někdo až sem (do páté úrovně vnoření?)?)?),
které ovšem není ničím než zkratkou za opakované volání cons, takže nepracuje
v konstantním čase)).