Třetí série začátečnické kategorie třicátého pátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 35-Z3-1: Vánoční ozdoby
- 35-Z3-2: Padající piškvorky
- 35-Z3-3: Substituční šifra
- 35-Z3-4: Vánoční stromek
35-Z3-1 Vánoční ozdoby (Zadání)
Na začátek je dobré si uvědomit, jak bychom řešili tuto úlohu pro jednu ozdobu. Máme 3 typy zdrojů, které nám poskytují napětí, a ozdobu, která má rozpětí napětí, ve kterém bude svítit. Koukneme se tedy na každý ze 3 zdrojů, jestli bychom daný zdroj mohli použít, a pokud ano, odložíme si ho vedle. Následně z odložených zdrojů vybereme ten nejlevnější a je hotovo. Navíc máme zaručeno, že vždy aspoň jeden správný zdroj existovat bude.
Jak to udělat pro N ozdob? Vlastně úplně stejně, protože využijeme faktu, že zdroje jsou pouze tři. Stačí nám tedy udělat výše popsaný postup pro každou ozdobu.
Časová složitost je lineární vzhledem k počtu ozdob, tedy O(N). Pro každou ozdobu děláme pouze konstantní počet kroků kontroly zdrojů. (Kdyby zdrojů bylo K, už jsme na složitosti O(N·K).) Pokud načítáme do paměti celý vstup naráz, je paměťová složitost také lineární. Načítáním ozdob po jedné však můžeme dosáhnout konstantní paměťové složitosti. Potom bychom si pamatovali pouze finální cenu, informace o 3 zdrojích a informace o právě načtené ozdobě.
35-Z3-2 Padající piškvorky (Zadání)
Novú hru začína hráč, ktorý prehral tú predošlú. Vyhrať môže hráč iba vo svojom ťahu. Preto sa hráči v ťahoch stále striedajú, a to bez ohľadu na to, kedy končia jednotlivé hry. Počas celej hry si teda budeme pamätať, či je na ťahu prvý hráč, alebo druhý, a v každom ťahu to vymeníme.
Kevin vyhral poslednú hru, ale nevieme, kto vyhral prvú. Hráčov si teda vieme označiť A a B. Nech A je ten, ktorý ťahal prvý. Vždy, keď jeden z nich vyhrá, zapamätáme si, že je zatiaľ posledný, kto vyhral. Nakoniec zistíme, či je Kevin A alebo B, podľa toho, kto vyhral poslednú hru. Všetky výhry si dovtedy musíme pamätať.
Keďže nevieme maximálnu výšku stĺpcov, budeme ich reprezentovať ako dynamické polia. Pri vhadzovaní piškvorky do stĺpca ju pridáme na koniec poľa. Ak sa chceme pozrieť na nejaké miesto v tabuľke, naskôr si overíme, či má jeho stĺpec potrebný počet prvkov, teda či je dĺžka daného poľa dostatočne veľká. Ak nie, vieme, že dané miesto je prázdne.
Keď jeden z hráčov vyhrá, polia vyprázdnime a uložíme si číslo ťahu a hráča, ktorý vyhral (A alebo B). Na konci vypíšeme čísla ťahov a to, či vyhral Kevin, alebo Sára (keďže už sme zistili, kto bol Kevin). Výhry sme ukladali v poradí, ako nastávali, takže už sú utriedené. Zároveň si sčítavame, koľkokrát kto vyhral, a tak zistíme celkového víťaza.
A ako detekovať výhru? Mohli by sme v každom ťahu prejsť celú plochu, ale to by viedlo na kvadratické riešenie a pri veľkom počte stĺpcov a dlhých hrách by nebolo dostatočne rýchle. Opäť pomôže poriadne sa zamyslieť:
Vyhrať môže hráč len piškvorkou, ktorú práve položil, teda nám v každom ťahu stačí otestovať, či aktuálne položená piškvorka nie je ľavá, stredná alebo pravá vrchná vo štvorci 3×3. Prejdeme teda tri štvorce (jeden pre každú polohu poslednej piškvorky), a ak sa v niektorom z nich nachádza celých 9 piškvoriek daného hráča, vyhral aktuálnu hru.
Takto sa nám časová zložitosť zredukuje na O(N + S·V), kde V je počet výhier, pretože pre každú pridanú piškvorku prehľadávame konštantný počet políčok, a pri každej výhre resetujeme S stĺpcov. (Keby sme chceli optimalizovať na krátke hry, mohli by sme si pre každú hru pamätať pôvodne poradie ťahov, a na konci postupne resetovať len použité stĺpce. Potom by časová zložitosť bola len O(N)). Pamäťová zložitosť môže byť až O(N + S), N informácií si musíme pamätať, pokiaľ by celý vstup tvorila jedna hra, a S je počet stĺpcov, tie si musíme pamätať, aj keď v nich nie sú vhodené žiadne piškvorky. Okrem toho si potrebujeme pamätať až V výhier, ale tých je určite menej, než N, preto sa to v zložitosti schová.
35-Z3-3 Substituční šifra (Zadání)
Pokud bychom úlohu řešili ručně, nejdříve bychom si nejspíše spočítali počet výskytů každého písmene v zašifrovaném textu, abychom si z toho mohli vytvořit mapování mezi zdrojovými písmeny a zašifrovanými písmeny. Máme zaručeno, že takové mapování bude existovat, protože počet výskytů každého písmena je unikátní.
Stejně tak bude postupovat náš program. Nejdříve si načteme celý vstup. Poté si spočteme výskyty jednotlivých písmen v zašifrovaném textu. Pak nějakým způsobem vytvoříme mapování mezi zdrojovými písmeny a zašifrovanými písmeny (detaily níže), takže nakonec budeme schopni text znovu projít a přeložit písmeno po písmenu.
Počet výskytů jednotlivých písmen budeme počítat v poli, přičemž i-tý
prvek pole bude odpovídat počtu výskytů písmene, které je v pořadí i-té
v anglické abecedě (například pokud na třetí pozici pole bude číslo 5, tak
se písmeno c, které je třetí v abecedě, vyskytlo celkem pětkrát).
Nejtěžší je vytvořit mapování mezi zdrojovými písmeny a zašifrovanými písmeny.
Pokud bychom úlohu řešili ručně, nejspíše bychom se podívali na písmeno,
které bychom chtěli přeložit (například g), zjistili bychom si počet jeho
výskytů (například 6), a našli bychom si písmeno ve zdrojové abecedě,
které se použilo přesně 6krát. To by bylo například písmeno h. Takže bychom
přeložili písmeno g na písmeno h. Tímto způsobem bychom si postupně
přeložili všechna písmena, celkem by nám to zabralo O(A2) času, kde A je
velikost abecedy (26), neboť pro každé šifrované písmeno hledáme jeho zdrojové
tím, že projedeme (až) všechna písmena.
Můžeme si trochu ulehčit práci tím, že si obě pole (s počty výskytů písmen)
seřadíme právě podle počtu výskytů. Pak budeme mít hezky „vedle sebe“
všechny písmena, která se vyskytla stejný počet krát. To je přesně
mapování, které jsme hledali. Při praktické implementaci si ale musíme
u hodnoty zapamatovat, kterýmu písmenu odpovídá.
Seřazení totiž pořadí prvků promíchá, takže c již nebude třetí.
Ať už si ulehčíme práci nebo ne, vlastně to bude celkem jedno. Výpočetně nejnáročnější operace bude překlad samotného textu, písmeno po písmenu. To už ze znalosti mapování uděláme jednoduše.
Časová složitost vzhledem ke konstantní velikosti abecedy (26) závisí pouze na délce textu, a to lineárně.
Paměťová složitost spočívá opět v tom, že si celý text načteme do paměti. Je tedy lineární. Avšak pokud bychom měli opravdu dlouhý text, mohli bychom klidně text načítat po částech, čímž bychom mohli ušetřit nějakou paměť (ovšem za předpokladu, že smíme vstup číst vícekrát).
35-Z3-4 Vánoční stromek (Zadání)
Jelikož zapojené prodlužky a ozdoby tvoří strom, můžeme využít pojmy z teorie grafů. Ze zadání víme, že prodlužky jsou vnitřní vrcholy a ozdoby jsou listy. Proud, který protéká prodlužkou, nazvěme odběr. O prodlužkách s odběrem větším než jejich maximální proud budeme mluvit jako přetížených.
Nejprve se zaměřme na otázku, jak pro každý vnitřní vrchol spočítat jeho odběr. To je právě součet odběrů jeho potomků. Pokud je potomek list, jeho odběr známe. Jde-li o vnitřní vrchol, můžeme jeho odběr spočítat rekurzivně. To není nic jiného, než prohledávání do hloubky.
Nyní, když umíme pro všechny prodlužky spočítat odběry, rozmysleme si, které prodlužky dává smysl vyprázdnit. Pokud není žádná prodlužka přetížená, nemusíme nic dělat. Jinak uvažme libovolnou přetíženou prodlužku p. Aby přestala být přetížená, musíme vyprázdnit některé prodlužky nacházející se v podstromě T(p) prodlužky p, a tak snížit odběr p pod maximum.
Mají-li všechny prodlužky T(p) kromě p odběr pod maximem, chceme vyprázdnit p. Vyprázdnění libovolné jiné prodlužky q ∈ T(p) totiž sníží odběr všech vrcholů na cestě z kořene do p stejně nebo méně. Mohlo by se pak stát, že kvůli tomuto rozdílu jiná přetížená prodlužka na této cestě, jejíž odběr bychom odpojením p dostali pod maximum, zůstane přetížená. Tudíž bychom pak potřebovali provést zbytečné vyprázdnění navíc.
Jinak mějme přetíženou prodlužku q ∈ T(p). Vyprázdnění p samo o sobě nepomůže, q zůstane stále přetížená! Musíme tedy nejprve vyřešit q. Tím snížíme odběr p, který může i klesnout pod maximum.
Dohromady dostáváme, že chceme vždy vyprázdnit takovou přetíženou prodlužku, která v jejím podstromu nemá žádnou jinou přetíženou prodlužku. Můžeme tedy opakovat nalezení takové prodlužky a její vyprázdnění, dokud nějaká prodlužka je přetížená. Jak to udělat rychle?
Podobně jako pro výpočet odběrů prodlužek využijeme prohledávání do hloubky. Po celou dobu však budeme udržovat invariant, že při uzavírání vrcholu žádný vrchol v jeho podstromu není přetížená prodlužka. Jak toho dosáhnout? Pro listy tento invariant platí triviálně. Pokud při uzavírání vnitřního vrcholu zjistíme, že jde o přetíženou prodlužku, vyprázdníme ji (tím přestane být přetížená) a z rekurze vrátíme nulový odběr. Tím už zajistíme, že invariant vždy platí.
Jaká bude časová složitost tohoto algoritmu? Stačí nám jedno prohledávání do hloubky, které trvá O(N) času, kde N je počet vrcholů stromu. Paměťová složitost bude stejná.