Druhá série začátečnické kategorie dvacátého devátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 29-Z2-1: Krocení zlé želvy
- 29-Z2-2: Sářina volba
- 29-Z2-3: Petr v říši divů
- 29-Z2-4: Zuzka: Cesta tam a zase zpátky
- 29-Z2-5: Dva roky bez prázdnin
- 29-Z2-6: Devět trpaslíků
29-Z2-1 Krocení zlé želvy (Zadání)
Naším úkolem bylo ze zadané posloupnosti příkazů zjistit, kde skončí Kevinova želva, až všechny tyto příkazy vykoná. Jako první je dobré si uvědomit, že úlohu můžeme řešit bez toho, abychom si vytvářeli velké pole a pohyb želvy po něm simulovali.
Tedy, abychom použili analogovou analogii, není potřeba vzít do ruky (velký) čtverečkovaný papír a postupně si kreslit kterými políčky želva projde. Namísto toho si stačí pamatovat vždy jen aktuální pozici a směr želvy.
Jakmile totiž zjistíme, jak ji posouvat, můžeme namísto simulace na velkém
poli či po čtverečkovém papíře, prostě jen aplikovat změnu na zapamatovanou
pozici či směr. V případě pokynu A konkrétně změnit pozici a při pokynech
< a > otočení.
Pozice se skládá ze dvou souřadnic. Můžeme si představit třeba čtverečkovaný papír se čtverečkem (0, 0) někde uprostřed.
Směr je ještě jednodušší, stačí si pamatovat, zda jsme otočení na sever, západ, jih nebo východ. Prakticky tedy postačí libovolná číselná proměnná. Na začátku je želva otočená nahoru.
Pro pořádky indexace si směry otočení seřadíme jak jsou napsané výše. Otočení s indexem 0 (přeci jen většina programovacích jazyků indexuje od 0, tak buďme konzistentní) bude na sever, s indexem 1 na západ a dále logicky proti směru hodinových ručiček.
Jakmile si vytvoříme takovouto reprezentaci, můžeme si všimnout, že otočení doleva je vždy zvýšení čísla otočení a doprava snížení. Problém jsou jen krajní hodnoty – když máme směr s indexem 3 (tj. na východ) a otočíme se doleva, dostaneme se na otočení na sever, tedy index 0.
Naštěstí ale nemusíme tyto krajní případy řešit separátně. Stačí místo upraveného indexu otočení vzít jeho zbytek po dělení čtyřmi, tj. např. ((i + 1) mod 4), a dostaneme přesně to, co chceme.
Otáčení máme vyřešeno. Stačí už jen vymyslet, jak aktuální směr aplikovat
v případě příkazu A, tedy posunu želvy dopředu. Nejjednodušší řešení je
připravit si dvě pole o čtyřech prvcích. Jedno pro změnu souřadnice v x-ové
a druhé v y-ové ose pro každý možný směr otočení.
Pro osu x může dané pole vypadat třeba takto: [0, -1, 0, 1]. Při otočení nahoru se při pohybu vpřed naše x-ová souřadnice nezmění. Při otočení doleva se zmenší o jedna a obdobně dál.
Při provádění příkazu A se pak jen podíváme do obou polí na hodnotu
indexovanou otočením a danou hodnotu přičteme k odpovídající souřadnici
aktuální pozice.
Časová složitost algoritmu je lineární s počtem příkazů, na každém totiž strávíme konstantně času. Paměťová je konstantní, pokud nepočítáme, že si je třeba pamatovat vstup. V průběhu algoritmu si totiž pamatujeme nezávisle na velikosti vstupu jen dvě pomocné proměnné.
29-Z2-2 Sářina volba (Zadání)
Abychom se dozvěděli, kdo rozhodne o plánech na víkend, stačí spočítat počet Sářiných a Kevinových vítězství. Na vstupu dostaneme řetězce Sářiných a poté Kevinových tahů. Načteme si je odděleně do dvou proměnných. Zároveň si budeme pamatovat aktuální počet vítězství každého.
Pak již jen stačí procházet
jednotlivé hry. Nejdříve vyhodnotíme první hru (tj. na indexu 0 v obou
řetězcích), pak hru na indexu 1 až k poslední n-1. K tomu nám poslouží
například cyklus for, v jehož každém průchodu vítězi přičteme jedno vítězství.
Při procházení potřebujeme rozhodnout, kdo danou hru vyhrál. Uvědomíme si, že hra může skončit pouze devíti stavy (každý má tři možnosti jak zahrát), které můžeme snadno otestovat podmínkami.
Pokud oba zahráli stejně, nevyhrál nikdo a přeskočíme rovnou na další hru.
Pokud Sára hrála kámen a Kevin nůžky, pak vyhrála Sára a připočteme ji jedno vítězství. Stejně tak v případě Sára nůžky + Kevin papír a Sára papír + Kevin kámen.
Pokud nenastala ani jedna z předchozích kombinací, pak nutně vyhrál Kevin, a proto mu připočteme jedno vítězství.
29-Z2-3 Petr v říši divů (Zadání)
V této úloze se ptáme, do kolika dalších políček lze v mřížce docestovat, pokud vyjdeme z jednoho konkrétního – Petrovy pozice. Na to se nejlépe hodí nějaké prohledávání. Chtěli bychom prohledávat od Petrovy pozice a každé políčko, na které dojdeme, si započítat a označit (nechceme některá políčka započítat vícekrát).
Prohledávat budeme následovně: vytvoříme si frontu, ve které budeme skladovat všechna políčka, která ještě chceme projít. Na začátku do ní přidáme jen políčko, na kterém stojí Petr. Pokaždé z fronty vytáhneme prvního kandidáta a podíváme se na jeho sousední políčka. Do fronty potom přidáme všechna políčka, která jsme ještě nenavštívili a nejsou to zdi.
Sousední políčka poznáme tak, že se jejich souřadnice liší o ±1 od aktuálního políčka (například políčko napravo má souřadnici x větší o 1, a y stejnou). Každé políčko, které jsme do fronty přidali, započteme, označíme a potom vytáhneme další.
Jakmile bude fronta prázdná, tak jsme dokončili procházení z Petrovy pozice a nikam jinam se už nedostaneme. Zbývá tedy vypsat číslo, které jsme napočítali a skončit.
Poslední malý problém k vyřešení je, jak najít pozici, na které se
nachází Petr a Sára. Protože mohou být kdekoliv v mapě, nepomůže nám žádný
chytrý algoritmus a musíme zkontrolovat všechna políčka. Budeme procházet od
začátku jedno po druhém, dokud nenarazíme na znak P a jeho pozici si
zapamatujeme.
Zbývá si rozmyslet, zda se nemůže stát, že v lese existuje políčko, na které by se Petr a Sára mohli dostat, ale my jsme ho nezapočítali. To se nestalo, protože do fronty se během prohledávání dostalo každé dostupné políčko. Naopak, nezapočetli jsme náhodou nějaká navíc? Protože jsme přičítali pouze volná políčka, na která jsme se mohli dostat, nezapočetli jsme nic navíc.
Jak je to celé rychlé a kolik to žere paměti v počítači? Nalezení Petra se Sárou trvá O(R ·S), prohledávání trvalo také O(R ·S), protože každé políčko se do fronty dostalo maximálně jedenkrát. Celý program je tedy lineární a dokonce trvá pouze O(R ·S + R ·S) = O(R ·S)
Paměťová složitost je také lineární O(R ·S), protože jediné, co si potřebujeme pamatovat je mapa, která má R ·S políček, a fronta, ve které se nikdy více políček než jich je v mapě neobjeví. Pokud si nejsi jistý v tom, co v tomto odstavci řešíme, můžeš si přečíst kuchařku o složitosti.
Na závěr podotkněme, že program se určitě zastaví, protože hledání Petra skončí po maximálně N krocích a naše prohledávání se zastaví, neboť každé políčko dáme do fronty maximálně jednou.
Jako třešničku na dortu přidáme, že algoritmus, který jsme použili při řešení je ve světě informatiky tak rozšířený, že má své vlastní jméno. Jmenuje se BFS – prohledávání do šířky a dá se použít na různé grafové problémy. Pokud nevíš, co graf je, mohla by tě zajímat naše kuchařka o grafech. Pokud už grafy znáš, tak si můžeš rozmyslet, že čtverečková síť, jako naše mapa ze zadání, je vlastně graf. Stačí každé políčko prohlásit za vrchol a spojit ho čtyřmi hranami s jeho sousedy.
29-Z2-4 Zuzka: Cesta tam a zase zpátky (Zadání)
Zadání po nás chtělo, abychom Zuzce nalezli nejdelší úsek, ve kterém půjdeme nejvýše K sekund do kopce. Nejprve vyzkoušíme jednoduché řešení.
Pro každé místo v posloupnosti vyzkoušíme, jestli náhodou ta nejdelší podposloupnost nezačíná zrovna tam. Tedy si naprogramujeme funkci, které řekneme začátek, a ona od něj najde nejdelší možný úsek, ve kterém půjde maximálně K sekund do kopce.
To je přeci jednoduché – pořídíme si energetickou kasičku, do které vložíme K penízků, a postavíme Kevina na začátek. Poté necháme Kevina jít co nejdále to půjde. Z kopce a po rovině půjde zadarmo, ale do kopce bude chtít penízek z kasičky. Jakmile bude chtít Kevin penízek, ale kasička bude prázdná, skončíme. Stejně tak pokud dojde Kevin na úplný konec trasy.
Z takto nalezených posloupností už jen snadno vybereme tu nejdelší. Jak to celé bude rychlé? Představte si dlouhou cestu, která bude ovšem celá z kopce. Naše funkce tedy pokaždé dojde až na konec cesty a celkem vykoná N + (N-1) + …+ 1 kroků, což je ovšem součet aritmetické posloupnosti, který vyjde v O(N2).
Chudák Kevin musí totiž pořád chodit tu samou trasu znovu a znovu. Proveďme jednoduché pozorování: pokud posuneme začátek doprava, Kevin může dojít jen dál – konec se nemůže posunout vlevo. Kevin se tedy nemusí vůbec vracet!
Na začátku algoritmu postavíme jak Zuzku tak Kevina na začátek trasy. Kevina pošleme kupředu, aby došel co nejdále, ale maximálně K sekund šel do kopce. Od této chvíle bude platit následující invariant (tvrzení, jehož platnost se v průběhu algoritmu nemění): mezi Kevinem a Zuzkou bude právě K sekund chůze do kopce.
Teď přijde řada na Zuzka. Ta půjde dopředu, ale pouze z kopce či po rovině. Kdykoli by měla jít do kopce, zavolá Kevinovi, a sekundu do kopce půjdou společně. Poté si Zuzka může odpočinout a Kevin utéct Zuzce co nejdále z kopce.
Zajímá nás chvíle, kdy budou Kevin se Zuzkou nejdále od sebe. To je totiž díky invariantu chvíle, kdy Kevin se Zuzkou vymezují nejdelší podposloupnost podle zadání.
Jakmile Kevin dojde na konec trasy, můžeme rovnou skončit, protože Zuzka už se bude jen přibližovat.
Teď už víme, že algoritmem vydané řešení bude vždy správné, ale ještě nám zbývá ukázat, že pokud řešení existuje, algoritmus ho najde. To je naštěstí jednoduché, protože každé řešení musí někde začínat a přes to místo musí Zuzka někdy přejít.
Algoritmicky samozřejmě nebudeme posílat Zuzce a Kevinovi itinerář cesty, ale budeme si posouvat dva ukazatele nad polem. Když si uvědomíte, že oba ukazatele posouváte pouze vpravo, vyjde z toho optimální časová složitost O(N).
Paměťovou složitost máme ovšem zatím také lineární. Pokud bychom chtěli ušetřit, musíme se vydat ještě o krůček dál. Než si ale přečtete další odstavce, načíst celý soubor se vstupem do paměti k řešení většinou bohatě stačí. Následující informace tedy berte jako teoretický bonus.
Všimněte si, že v celém algoritmu nás vlastně vůbec nezajímaly konkrétní hodnoty nadmořských výšek. Místo nich nám stačí uvažovat, kdy cesta vedla do kopce a kdy z kopce. Dokonce ani nepotřebujeme mít jednotlivé sekundy v paměti rozdělené – stačí nám koukat na to, jak dlouhé jsou úseky z kopce mezi jednotlivými sekundami do kopce.
Mohli bychom tedy algoritmus pozměnit tak, že by načítal jednotlivá čísla s tím, jak přesouvá Kevina, a pro Zuzku už by si pamatoval jen délku dalších K úseků z kopce. Tím bychom srazili paměťovou složitost na O(K).
29-Z2-5 Dva roky bez prázdnin (Zadání)
Od Šklíby jsme dostali úkol najít původce řetězu putování spamu mezi bytostmi. Nejprve si můžeme rozmyslet, že řetěz rozesílání e-mailu nám tvoří nějaký orientovaný graf. Seznam dvojic, jenž Šklíba získal, není nic jiného, než seznam hran, avšak neorientovaných, v tomto grafu. Vrcholy potom reprezentují jednotlivé bytosti, které se dostaly do styku se spamem.
Dále víme, že každé bytosti spam přišel nejvýše jednou a možná jej odeslala dalším K bytostem. V řeči grafů to znamená, že nejvýše jedna hrana do vrcholu (bytost) vstupuje a vystupuje z něj buď K hran, nebo žádná.
Stupněm vrcholu budeme značit počet hran, které vedou do nebo z daného vrcholu. Podívejme se tedy na možnosti, jaký může být stupeň vrcholu bytosti:
- Pokud bytosti spam přišel, do jejího vrcholu vede právě jedna hrana, stupeň se tedy zvýší o 1.
- Pokud bytost spam odeslala dalším K bytostem, stupeň jejího vrcholu se zvýší o K.
Pojďme z toho prozkoumat, jakého tvaru tento graf nabývá. Již víme, že každý vrchol má nejvýše jednoho předchůdce. Také má každý vrchol právě 0 nebo K potomků. Takový graf nápadně připomíná strom.
Kdybychom se nezabývali orientací hran, opravdu o strom jde. Kořenem je v tomto případě původce spamu a listy jsou doručitelé, kteří dále spam nerozeslali. Dále si můžeme všimnout, že je tento strom k-ární, jelikož každý vrchol, jenž není list, má právě k potomků.
Stupně vrcholů v našem grafu tedy můžou být 1 pro „listy“, K pro „kořen“, nebo K+1 pro ostatní. Z toho můžeme usoudit, že chceme-li najít původce spamu, stačí nám najít kořen v pomyslném stromě, který má stupeň právě K. Žádný jiný vrchol stejný stupeň už mít nebude, původce je jen jeden.
Ten můžeme najít takto: Postupně projdeme jednotlivé dvojice a budeme si poznamenávat pro každou bytost, kolikrát se vyskytla v nějaké z dvojic. Všimněme si, že tento počet odpovídá právě stupni jejího vrcholu. Potom stačí vyhlásit bytost s právě K výskyty jako původce spamu.
Jak dlouho nám hledání původce potrvá a kolik při tom spotřebujeme paměti? Každou z M dvojic musíme projít právě jednou. Celkově nad tímto procházením strávíme O(M) času. Potom projdeme každou z N bytostí a zkoumáme počet výskytů. Časová složitost je tedy O(N+M). Dále si musíme pro každou bytost něco málo pamatovat, paměti tak spotřebujeme O(N).
Kolik dvojic ale může být celkem? Jelikož každému, až na jediného původce, přišel spam právě jednou, bude těchto dvojic právě N-1. Časová složitost nám tedy ve skutečnosti sejde na O(N).
29-Z2-6 Devět trpaslíků (Zadání)
Kevin a Zuzka dostanou řadu N čísel v určitém pořadí a u ní mají za úkol rychle odpovídat na určité dotazy. Ty se týkají součtů čísel mezi a-tým a b-tým číslem řady.
Zjevné řešení je pro každý dotaz posloupnost znovu projít a od a-tého do b-tého indexu čísla sčítat. Pokud by se trpaslíci ptali pořád na součet celé řady, procházeli bychom vždy všech N čísel znovu. Kvůli tomu je časová složitost na jeden dotaz O(N).
Zkusíme zvolit úplně jiný postup. Budeme na něj sice potřebovat více času na přípravu, ale budeme doufat, že se nám to vyplatí. Naším cílem je odpovídat co nejrychleji. Využijeme toho, že sčítání má dobré vlastnosti (například pro násobení by naše řešení nefungovalo), a předpočítáme si čísla, ze kterých budeme schopni rychle vykoukat řešení.
V dalších odstavcích budeme součet čísel mezi a-tým a b-tým indexem značit s(a, b + 1). Následujeme tedy běžné programátorské pojetí intervalů, kdy s(a, b) značí součet takového úseku, do kterého a patří ale b už ne.
Představme si, že známe součty na dvou úsecích, které mají společný začátek: s(a, b) a s(a, c). Z těchto čísel jsme schopni odvodit s(b, c) – ten je roven s(a, c) - s(a, b). Rozepište si to. Uvidíte, že se čísla na začátku odečtou a zůstanou jen ta správná.
Tohoto faktu využijeme a spočítáme si součet s(0, x) pro každé x. Úsek začínající na začátku posloupnosti se nazývá prefix posloupnosti, a proto se posloupnosti jejich součtů obvykle říká prefixové součty.
Uvedeme příklad. Máme řadu čísel 1, 5, 4, 3, 6 a chceme k ní znát všechny prefixové součty. Ty budou vypadat následovně: 0, 1, 6, 10, 13, 19. Spočítat všechny prefixové součty můžeme průběžně při načítání – každé číslo stačí přičíst k předchozímu, už sečtenému, prefixu, a máme součet o jedna delšího prefixu. Díky tomu nám počítání zabere pouze O(N).
součty[0] = 0
for i in range(N+1):
součty[i] = součty[i - 1] + čísla[i - 1]
Abychom mohli počítat s celou řadou na vstupu, přidáme si na konec součtů ještě jeden prvek navíc, součet celé řady (proto N+1). Všimněte si ale, že čas na přípravu nás vlastně moc nezdržuje – pokud nechceme čísla číst rovnou ze souboru, nevyhneme se načtení do paměti. To už ale trvá stejně dlouho, jako počítání prefixových součtů.
A když už máme pole prefixových součtů připravené, dotazy se zodpovídají velmi
snadno. Hodnota součtu čísel mezi a-tým a b-tým je rovna součty[b + 1]
- součty[a]. Na dotazy tedy umíme odpovídat v konstantním čase, ale potřebujeme
O(N) času na přípravu. Paměťová složitost je O(N). Pokud se chcete
o prefixových součtech a jejich využití dozvědět více, podívejte se na
kapitolu kuchařky o intervalových stromech.