První série desátého ročníku KSP
Řešení úloh
10-1-1 Hanojské věže (Zadání)
Tato úloha nepatřila mezi problémové. Buď jste ji řešili metodou "Rozděl a panuj" nebo analýzou možných tahů, což bylo komplikovanější, a téměř nikdo jste nenapsali důkaz správnosti algoritmu. Zajímavé nám přišlo, že téměř polovina lidí řešících úlohu rekurzí napsala chybně, že paměťová složitost je exponenciální.
My použijeme metodu "Rozděl a panuj". Naši úlohu rozdělíme na menší části, které následně vyřešíme. K tomu, abychom mohli přenést libovolný disk D z tyče A na tyč B, potřebujeme, aby byly všechny disky menší než D na pomocném disku C, jinak by to bylo proti pravidlům. (†) Pokud tedy budeme přemisťovat disk D, nemusíme se zabývat většími disky než D, neboť ty nemohou dle pravidel ovlivnit přemisťování.
Algoritmus: (N>0 … počet disků na tyči A; chceme je přenést na tyč B)
- Přeneseme N-1 disků z A na C.
- Přeneseme 1 disk z A na B (v této úrovni největší disk).
- Přeneseme N-1 disků z C na B.
To je celý algoritmus. Kroky 1 a 3 se vyřeší stejně. Algoritmus je konečný, neboť se rozkládá na menší úlohy nejvíce do hloubky N (parametr N pro podúlohu je vždy o 1 menší). Algoritmus je korektní, neboť jednotlivé kroky algoritmu jsou v souladu s pravidly (to jsme již ukázali výše). Algoritmus je tedy správný.
Zbývá dokázat, že neexistuje algoritmus, který by úlohu vyřešil rychleji. Kdyby ano, potom bychom buď (a) museli použít jiný algoritmus, nebo (b) bychom mohli zlepšit jednu z jeho částí. Každý algoritmus však musí dodržovat (†), tedy musí obsahovat náš algoritmus. (b): krok 2 už zlepšit nelze, neboť v něm přenášíme disk z A na B přímo jedním tahem. Kroky 1 a 3 se řeší stejným algoritmem. Tedy všechny části jsou nejrychlejší možné a tedy náš algoritmus je nejrychlejší možný.
Časová složitost: z algoritmu plyne rekurentní vztah pro počet kroků: T(N)=T(N-1) +1 +T(N-1). Triviálně platí T(1)=1, T(2)=T(1) +1 +T(1)=2*T(1) +1=2*1 +1=3, T(3)=2*T(2)+1=2*(2*T(1)+1)+1=22 + 21 +20=7 … T(N)=2N-1 +2N-2 +… +20=2N -1. Časová složitost je tedy exponenciální, O(2N).
Paměťová složitost: Algoritmus a program potřebuje v jedné úrovni vnoření paměť pro 4 proměnné, přičemž počet úrovní vnoření (rekurze) je N. Tedy paměťová složitost je lineární, O(N).
Program realizuje rozdělení na podúlohy pomocí rekurze. Je přímým přepsáním algoritmu.
10-1-2 Bílá paní (Zadání)
Zadání této úlohy bylo zformulováno dost nešťasťně, nicméně i tak přišlo mnoho řešení. Někteří řešili onu triviální úlohu, jiní si zadání přeformulovali, a pokud jejich úloha měla nějaký smysl, uznával jsem tato řešení také.
Ze zadání plynulo, že Bílá paní se umí pohybovat pouze po přímce před sebe (po odrazu opačným směrem), a tedy přímku nemůže opustit. Někteří řešitelé se zamýšleli nad možností, že stěny hradu nejsou rovnoběžné se světovými stranami, a tím pádem bílá paní začínající svůj pohyb například na sever nemusí projít (resp. narazit) dveřmi, ale může se odrážet v jedné místnosti z rohu do rohu po věky věků. S našimi informacemi o hradě ale nemůžeme takovouto situaci simulovat, takže mlčky předpokládejme, že Bílá paní chodí jen a pouze rovnoběžně se stěnami hradu.
Dosažitelnost kocoura Bílou paní pak přechází na určení, zda se kocour a Bílá paní nachází na stejném sloupci/řádku a zda mezi nimi nejsou zavřené dveře (tj. mezi kocourem a Bílou paní jsou samé nuly). Pokud jsou tyto podmínky splněny, Bílá paní nalezne kocoura v konečném počtu kroků. Toto můžeme rozhodnout v kvadratickém čase a s konstantními časovými nároky.
K určení počtu kroků potřebujeme znát polohu omezujících dveří (tj. dveří, které omezují pohyb Bílé paní ve sloupci/řádku) pro případ, kde dojde nejprve k odražení Bílé paní od dveří a pak teprve najde kocoura. Nalezení omezujících dveří v řádku je triviální, ve sloupci je hledání horních omezujících dveří ztíženo tím, že nevíme, ve kterém sloupci se kocour a Bílá paní nacházejí, a proto musíme hledat omezující dveře ve všech sloupcích, což zvyšuje konstantní paměťové nároky na lineární. To by se dalo eliminovat dvojitým přečtením dat ze vstupu, ale to podle mého názoru není vůbec elegantní. Samotné spočtení kroků z těchto údajů je zřejmé.
Celkově má algoritmus kvadratickou časovou složitost, tj. O(M2) a lineární paměťovou složitost, tj. O(M), kde M je počet místností v sloupci/řádku.
10-1-3 Bermudský trojúhelník (Zadání)
Přestože tato úloha byla poměrně jednoduchá, objevila se ve vašich řešeních celá řada nešvarů naprosto typických pro řešení prvních sérií seminářů. Konkrétně:
- Chybějící popis algoritmu – nestačí uvést program, je též nutné zmínit se o tom, jak vlastně funguje.
- Chybějící důkaz správnosti algoritmu – nestačí algoritmus vysvětlit, je též záhodno uvést, proč zadaný problém řeší (pokud to není zjevné z principu jeho konstrukce, což zde obvykle nebylo).
- Chybějící, případně nesprávný odhad časové a paměťové složitosti algoritmu – doporučuji přečíst si úvodní text o časové složitosti v zadání první série.
- "Bells and whistles" – v seminářových programech opravdu není nutné zabrat většinu papíru mazáním obrazovky, čekáním na stisk klávesy, barvičkami, zvuky a pazvuky, prompty při zadávání, kontrolami korektnosti vstupních dat (nejsou-li explicitně vyžadovány v zadání) atd.
Nuže dobrá, nyní již k tomu, jak úlohu opravdu vyřešit. Označme si čísla v pyramidě ai,j, kde i je řádek a j pozice na řádku. Při tomto očíslování jistě platí, že z prvku ai,j můžeme pokračovat buďto do ai+1,j nebo do ai+1,j+1.
Povšimněme si nyní triviálního, leč velice důležitého faktu: maximální cesta (tak budeme říkat cestám vedoucím z daného bodu až k základně a majícím ze všech takových cest největší součet čísel na ní ležících) z prvku ai,j se skládá z odbočky doleva resp. doprava následované opět maximální cestou z bodu ai+1,j resp. ai+1,j+1 (kdyby pokračovala cestou horší než je cesta maximální, mohli bychom tuto cestu nahradit cestou maximální, čímž bychom získali cestu z ai,j lepší než byla původní maximální, což by byl spor).
Nyní budeme konstruovat maximální cesty z jednotlivých bodů, a to postupně po jednotlivých hladinách počínaje základnou. Pro každý bod spočteme délku maximální cesty ci,j. Pro body základny je to triviální: cn,j = an,j (cesty tam končí). Nyní známe-li již všechna ci,j pro dané i, snadno dopočítáme i pro hladinu bezprostředně výše: cesta z ci-1,j buďto začíná odbočkou doleva a má součet ai-1,j + ci,j nebo odbočkou doprava se součtem ai-1,j + ci,j+1. Jelikož hledáme cestu maximální, vybereme z těchto dvou možností tu s větším součtem (viz úvaha v předchozím odstavci), pokud jich je více, použijeme libovolnou z nich.
A jak vypíšeme to, co se po nás chce (to jest maximální cestu z a1,1)? Inu, snadno: začneme v a1,1 a pokračujeme do a2,1 nebo a2,2 podle toho, zda je větší c2,1 nebo c2,2. Obecně z bodu ai,j pokračujeme do toho z bodů ai+1,j, ai+1,j+1, pro nějž je hodnota c větší. Takto vybereme přesně tu cestu, jejíž délku jsme vypočetli výše uvedeným postupem.
Časová složitost algoritmu je O(N2), jelikož každý prvek trojúhelníka zpracujeme maximálně dvakrát (asymptoticky rychlejší algoritmus ani nemůže existovat, ježto každý prvek musíme nutně otestovat), paměťová složitost rovněž O(N2).
Program postupuje přesně dle tohoto algoritmu, přičemž délkami maximálních cest přímo nahrazuje jednotlivé prvky trojúhelníka.
10-1-4 No to snad ne! (Zadání)
Minusdvojková soustava vám příliš hlavu nezamotala, což je potěšující. Jen si někteří z vás nevšimli, že číslo může mít miliony cifer – a tedy že je nejlepší je zpracovávat přímo při vstupu. Je totiž možné, že se číslo nevejde do paměti.
Nejjednoduší samozřejmě je využít přímo definice, to ale právě vynutí uložení celého minusdvojkového čísla do paměti. Výhodnější je uvědomit si jednu zákonistost, na které řešení založíme:
Když totiž nějaké číslo a má při dělení číslem k zbytek z, pak číslo a0 bude mít stejný zbytek po dělení číslem k, jaký bude mít číslo z0. Skutečně, například v desítkové soustavě 313 mod 3=1 a při tom 3130 mod 3=1 stejně jako 10 mod 3=1.
Platí to skutečně vždycky? Pokud a mod k=b, pak musí pro nějaké c platit a=k·c+b a tedy a·s=k·s·c+b·s odkud už vyplyne, že a·s mod k=b·s mod k.
Toho teď využijeme k jednoduchému algoritmu: Postupně budeme načítat jednotlivé cifry (bude to vždy jednička nebo nula), přičteme k (-2)-násobku stávajícího zbytku a "vymodulíme" k. Když takhle zpracujeme celé číslo, dostaneme zbytek po dělení minusdvojkového čísla číslem k. Je-li to nula, bylo číslo dělitelné.