Pátá série začátečnické kategorie třicátého osmého ročníku KSP
Celý leták v PDF.
Řešení úloh
38-Z5-1 Hroší-LZW dekomprese (Zadání)
Slovník se při dekompresi buduje stejným způsobem jako při kompresi. Když přečteme kód K, vypíšeme jemu odpovídající slovo w. Následně se snažíme přidat nové slovo do slovníku jako w + c, kde c je první znak slova odpovídajícího dalšímu kódu.
Na začátku si vytvoříme slovník tak, aby obsahoval všechna jednopísmenná slova a-z s kódy 0 až 25. Dále si udržujeme proměnnou w, která
reprezentuje slovo odpovídající poslednímu přečtenému kódu.
Algoritmus postupuje takto:
- Přečteme první kód a pomocí slovníku ho převedeme na odpovídající slovo. Toto slovo vypíšeme a uložíme do w.
- Pro každý následující kód K:
- Pokud je kód již ve slovníku, převedeme ho na slovo s.
- Pokud kód ještě není ve slovníku (jedná se o právě přidávaný kód), pak se slovo s rovná w + c, kde c je první znak slova w.
- Vypíšeme slovo s.
- Do slovníku přidáme nové slovo w + c', kde c' je první znak slova s, s dalším volným kódem (počínaje od 26).
- Nastavíme w := s.
Zvláštní případ
Při dekompresi se může stát, že narazíme na kód, který ještě není ve slovníku. To se stane, když komprese přidala nový kód a hned jej použila v následujícím kroku. V takovém případě musíme slovo rekonstruovat jako w + c, kde c je první znak slova w (které jsme právě vypsali).
Vezměme si vstup 2 1 0 28 3 28 z příkladu v zadání:
- Kód 2 →
c, vypíšemec, w :=c - Kód 1 →
b, přidáme 26 :=cb, vypíšemeb, w :=b - Kód 0 →
a, přidáme 27 :=ba, vypíšemea, w :=a - Kód 28 není ve slovníku, slovo je w+c =
aa, přidáme 28 :=aa, vypíšemeaa, w :=aa - Kód 3 →
d, přidáme 29 :=aad, vypíšemed, w :=d - Kód 28 →
aa, přidáme 30 :=da, vypíšemeaa
Výstup je: cbaaadaa
Časová složitost algoritmu je O(M), kde M je součet délek všech slov v dekomprimovaném textu. Protože při dekompresi vytváříme také výstupní text, všechna slova musíme tak či onak vypsat, takže toto je asymptoticky optimální.
Paměťová složitost je O(N), kde N je počet kódů na vstupu, protože ve slovníku bude nejvýše N + 25 položek.
38-Z5-2 Rovnice (Zadání)
Každou soustavu rovnic budeme řešit zvlášť.
Nejdřív načteme tři rovnice a z každé z nich získáme koeficienty jednotlivých proměnných a pravou stranu rovnice. Protože proměnné nemusí být vždy pojmenované stejně ani být ve stejném pořadí, nejprve si zapamatujeme, které tři proměnné se v soustavě vyskytují, a všechny rovnice převedeme do stejného pořadí proměnných. Takto získáme soustavu tří rovnic o třech neznámých v obecném tvaru.
Řešit ji budeme následovně:
Vezmi první a druhou rovnici a zbav se v nich jedné proměnné: vynásob je vhodně a pak je sečti nebo odečti. Totéž udělej s první a třetí rovnicí. Teď máš dvě rovnice se dvěma neznámými.
V těchto dvou rovnicích se zbav další proměnné stejným způsobem. Zůstane ti jedna rovnice s jednou neznámou – vyřeš ji. Pak postupně dosazuj výsledek zpátky a najdi zbylé neznámé.
Gaussova eliminace
Existuje elegantnější způsob, jak soustavu vyřešit – Gaussova eliminace. Je trochu složitější, ale je univerzální a lze ji použít pro libovolný počet rovnic a proměnných.
Po základní úpravě soustavy rovnic do obecného tvaru, kdy jsou všechny proměnné ve stejném pořadí, můžeme soustavu zapsat jako matici o třech řádcích a třech sloupcích, kde každý řádek odpovídá jedné rovnici a každý sloupec jedné proměnné. K tomuto zápisu přidáme ještě čtvrtý sloupec, který bude obsahovat pravé strany rovnic. Takto vznikne tzv. rozšířená matice soustavy.
Postupně upravujeme řádky tak, aby pod hlavní diagonálou vznikly samé nuly. Pokud je potřeba, můžeme dva řádky prohodit, aby byl na diagonále nenulový koeficient.
Jakmile dostaneme matici do trojúhelníkového tvaru, spočítáme hodnoty proměnných zpětným dosazováním. Nejdříve určíme poslední proměnnou z poslední rovnice, potom prostřední proměnnou z druhé rovnice a nakonec první proměnnou z první rovnice.
Popsaný postup najdete ve vzorovém programu. S menší úpravou by šel použít i pro libovolný počet rovnic a proměnných (pokud má soustava právě jedno řešení). Vzhledem k tomu, že se v této úloze řeší pouze soustavy o třech rovnicích a třech neznámých, je ale také možné místo obecného maticového řešení napsat přímo výpočty pro tento konkrétní případ, i když je to o něco méně elegantní.
Když budeme považovat velikost matice za konstantní, tak načtení a zpracování jedné soustavy zabere konstantní čas, tudíž celková časová složitost je O(N), kde N je počet soustav na vstupu. Paměťová složitost je O(1), protože během výpočtu ukládáme pouze jednu matici.
38-Z5-3 Už žádné zbytečné kopce! (Zadání)
Úlohu snadno převedeme do řeči grafů: za každé políčko vytvoříme vrchol, za každou dvojici sousedních políček neorientovanou hranu a každý vrchol v ohodnotíme jeho nadmořskou výškou h(v). Tak získáme graf s n = RS vrcholy a m≤ 4n hranami. Ptáme se, zda je graf monotónní, tedy zda pro každou dvojici vrcholů u, v splňující h(u) < h(v) platí, že z u do v vede cesta, která jen stoupá. (Původní úloha se ptá na všechny dvojice u a v a požaduje cestu, která buď celá stoupá, nebo celá klesá, ale snadno nahlédneme, že to je totéž.)
Samozřejmě můžeme vyzkoušet všech Θ(n2) dvojic vrcholů a pro každou z nich v čase Θ(n + m) = Θ(n) prohledáváním zjistit, zda mezi nimi vede stoupající cesta. To je ale ukrutně pomalé. Naštěstí máme v zásobě dva triky:
Nejprve si všimneme, že není potřeba zkoušet Θ(n2) dvojic, ale jen Θ(n). Máme-li totiž vrcholy a, b, c s h(a) < h(b) < h(c), stačí ověřit existenci stoupající cesty z a do b a z b do c. Jejich sjednocení pak dává stoupající cestu z a do c. Obecně, seřadíme-li si vrcholy podle jejich nadmořské výšky a označíme je od nejnižšího jako v1, … , vn, pak stačí ověřit existenci stoupající cesty z v1 do v2, z v2 do v3, a tak dále. Pokud nějaká z těchto cest neexistuje, tak graf není monotónní, a pokud všechny existují, pak umíme libovolnou jinou stoupací cestu z těchto menších cest poskládat.
Tím jsme složitost snížili z Θ(n3) na Θ(n2). Teď můžeme vytáhnout ještě druhé pozorování:
Mějme nějaké dva vrcholy vi, vi+1 sousedící v poli seřazených nadmořských výšek. Chceme otestovat, zda mezi nimi existuje stoupající cesta. Jak ale taková cesta může vypadat? Musí to být hrana! To proto, že libovolná cesta z vi do vi+1 navštěvující libovolný jiný vrchol w nemůže být stoupající, neboť mezi h(vi) a h(vi+1) žádná jiná nadmořská výška není, a tedy nemůže platit h(vi) < h(w) < h(vi+1). Abychom tedy ověřili, že mezi vi a vi+1 vede stoupající cesta, stačí ověřit, že spolu sousedí, což zvládneme v konstantním čase.
Celý algoritmus je tedy následující: seřadíme si políčka podle jejich nadmořské výšky a pak pro každou dvojici políček s po sobě jdoucí nadmořskou výškou zkontrolujeme, že spolu sousedí, a pokud ne, tuto dvojici vypíšeme. Výsledná časová složitost je O(n log n) = O(RS log(RS)), paměťová je lineární.
Poznámka na závěr: v řešení jsme hojně využívali poněkud nevinně vypadající předpoklad, a to, že nadmořské výšky jsou unikátní. Bez něj je úloha stále řešitelná v čase O(RS log(RS)), ale detaily jsou trochu chlupatější. Můžete si je zkusit rozmyslet.
38-Z5-4 Gramofon (Zadání)
Představme si, že procházíme nahrávku o délce N zleva doprava. Kdykoliv narazíme na číslici na indexu i, kterou jsme již viděli na indexu prev, museli bychom úsek od prev do i zopakovat. Tento přístup má dva zásadní problémy – nahrávka se může astronomicky nafouknout a indexy se neustále posouvají.
Místo reálného natahování nahrávky budeme pro každé políčko i zjišťovat celkový počet přehrání Pi. Pokud bychom ale simulovali průchod směrem dopředu a pole P upravovali za běhu, pro každé opakování bychom museli přičíst jedničku ke všem políčkům v rozsahu od prev do i. To by vedlo k obrovskému nárůstu počtu operací a kvadratické časové složitosti O(N2).
Zkusme se na problém podívat zprava doleva. Každé přehrání políčka i znamená, že jehla odskočí zpět na index prev a znovu projde celý úsek až k i-1. Celkový počet přehrání Pi se tedy musí kompletně připočítat ke všem políčkům od prev do i-1. Políčko i přímo ovlivňuje své předchůdce.
Protože se opakuje související úsek, informaci o počtu přehrání můžeme nechat téct jako vlnu od konce nahrávky k začátku. Každé políčko i předá svůj nastřádaný počet přehrání sousedovi vlevo (i-1). Vlnu vyvolanou políčkem i je však potřeba zastavit za indexem prev. Vlna projde políčkem prev, ale na prev-1 už dospět nesmí, proto zde hodnotu Pi odečteme.
Tak zkusme si napsat algoritmus. Nejdříve si připravíme pole prev, které pro každé políčko i uchovává index jeho předchozího výskytu. V prvním průchodu (zleva doprava) zjistíme pro každé políčko i index jeho předchozího výskytu prev. Využijeme k tomu pomocné pole o velikosti K (počet různých číslic), kam ukládáme poslední viděný index každé číslice. Pokud se číslice objevuje poprvé, nastavíme prev = -1. Na konci průchodu inicializujeme základní hodnoty Pi = 1.
Ve druhém průchodu (zprava doleva) jde jehla od indexu N dolů k 1. Každé políčko i přičte svůj aktuální počet přehrání Pi k sousedovi Pi-1. Pokud existuje předchozí výskyt (prev ≥ 0), připravíme zarážku a od hodnoty na indexu prev-1 odečteme Pi. Hodnotu na indexu prev-1 odečítáme, protože vlna z políčka i by měla zastavit na indexu prev, ale nesmí pokračovat na prev-1. Když ji tedy odečteme, vlna se zastaví přesně na prev. Během tohoto couvání hodnoty na aktuálním indexu i definitivně zamrzají, takže je rovnou přičítáme do výsledného globálního počítadla pro danou číslici.
Časová složitost algoritmu je O(N), protože nahrávku projdeme pouze dvakrát a práce na každém políčku vyžaduje konstantní množství operací O(1). Paměťová složitost je O(N + K), což odpovídá polím délky N pro uložení indexů a frekvencí a poli o velikosti K pro sledování posledních výskytů číslic.