Čtvrtá 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-Z4-1: Sousední čísla
- 38-Z4-2: Efektivní záloha webu
- 38-Z4-3: Jarní malování
- 38-Z4-4: Kevin kuchařem
38-Z4-1 Sousední čísla (Zadání)
Nejdřív potřebujeme zjistit, kolikrát se každá stanice v seznamu vyskytuje. Protože čísla stanic mohou být velká, nemůžeme jimi indexovat pole, tak použijeme slovník, kde si pro každou stanici uložíme kolikrát se v seznamu vyskytuje.
Jakmile máme spočítané četnosti všech stanic, potřebujeme najít dvojici sousedních stanic s největším součtem četností. Na tohle stačí projít všechny stanice a zkontrolovat soused o 1 větší. Tímhle zkontrolujeme všechny dvojice (stanice, stanice + 1), což určitě obsahuje všechny dvojice, které existují ve vstupu.
Tedy pro každou dvojici spočítáme součet jejich četností a porovnáme ho s nejlepším výsledkem, který jsme zatím našli. Pokud je větší, uložíme si tuto dvojici jako novou nejlepší odpověď. Na konci už pouze vypíšeme nalezenou dvojici stanic a jejich jednotlivé četnosti.
Protože používáme slovník na uložení četností, časová složitost algoritmu je v průměru O(N), kde N je délka seznamu stanic. Paměťová složitost je také O(N). Alternativní řešení bez slovníku by bylo nejdříve seřadit seznam stanic, spočítat jejich četnosti a pak projít sousední dvojice, což by mělo časovou složitost O(N log N).
38-Z4-2 Efektivní záloha webu (Zadání)
Nejdříve si připravíme počáteční slovník. Podle zadání na začátku obsahuje malá písmena a-z s kódy 0 až 25.
Tyto kódy ale na výstupu nebudeme přímo vypisovat – výstup komprese se skládá z kódů od 26 výše.
Celý algoritmus probíhá tak, že čteme vstupní řetězec po jednotlivých písmenech a udržujeme si proměnnou w, která představuje zatím nalezenou nejdelší frázi obsaženou ve slovníku. Na začátku je w prázdná.
Pro každé další písmeno c zkusíme, jestli se w + c nachází ve slovníku.
- Pokud ano, jen rozšíříme w na w + c a pokračujeme.
- Pokud ne, vypíšeme kód pro w, přidáme w + c do slovníku s dalším volným číslem (začínáme od 26) a nastavíme w na c.
Po zpracování všech znaků ještě musíme vypsat kód pro poslední w, pokud není prázdná.
Pro jednoduchost si slovník ukládáme jako dictionary (slovník v Pythonu, map v jiných jazycích),
kde klíčem je fráze a hodnotou její kód. Na začátek do něj vložíme všechna jednopísmenná slova a-z s kódy 0-25.
Při výpisu slovníku potřebujeme vypsat jen fráze vzniklé během komprese, tedy ty s kódem 26 a vyšším.
Celková složitost algoritmu je O(N), kde N je délka vstupního řetězce, protože pro každý znak provedeme konstantní počet operací (kontrola přítomnosti ve slovníku, případně přidání do slovníku a výpis kódu). Ve slovníku bude nakonec nejvýše N + 26 položek, protože každé nové slovo vzniká z přidání jednoho znaku k již existujícímu slovu, tedy paměťová složitost je také O(N).
38-Z4-3 Jarní malování (Zadání)
Nejdřív načteme celý obrázek do dvourozměrného pole velikosti W ×H, abychom mohli indexovat jednotlivé pixely. Následující řádky s kyblíky můžeme jednotlivě zpracovat a rovnou vypisovat jejich výsledky.
Zpracování jednoho kyblíku zvládneme pomocí prohledávacího algoritmu, třeba prohledávání do šířky (BFS) nebo do hloubky (DFS). Prohledávání samotné začne na pozici kyblíku a postupuje do všech čtyř sousedních pozic (nahoru, dolů, doleva, doprava), které jsou v rozsahu barvy daného kyblíku, dokud už nezbývají žádné sousední pozice, které bychom mohli navštívit. Počet navštívených pozic nám dá výsledek pro daný kyblík.
V obou případech (BFS i DFS) potřebujeme nějakou strukturu, abychom věděli, které pozice jsme už navštívili, abychom je nenavštívili znovu. Jednou z možností je dvourozměrné pole, které bude ukládat informaci o tom, jestli jsme danou pozici navštívili, a k tomu nějaké pole, abychom věděli, které pozice na konci prohledávání vrátit do nenavštíveného stavu a kolik vůbec pozic jsme navštívili. Také lze použít nějakou množinu navštívených pozic (ideálně neuspořádanou množinu, aby byla rychlejší), do které přidáváme pozice, které jsme navštívili.
Když se koukneme na teoretickou složitost, tak pro každý kyblík můžeme potenciálně navštívit všechny pozice, takže celková složitost bude O(W*H + K*W*H), kde W a H jsou rozměry obrázku a K je počet kyblíků. Prakticky ale prohledáme mnohem menší prostor. Pokud jste zkusili otevřít vstup v aplikaci, který podporuje formát PGM, tak jste mohli vidět, že na obrázku jsou velmi malé oblasti velmi podobných barev, tedy pouze menšina kyblíků budou prohledávat velké oblasti, ale i tyto oblasti budou mnohem menší než W*H.
38-Z4-4 Kevin kuchařem (Zadání)
Zkusme problém vyřešit pomocí greedy algoritmu. Cílem je najít pořadí zpracování vrcholů, které minimalizuje počet přechodů ze „špinavého“ do „čistého“ stavu. Zadání si představíme jako plánování práce od listů (suroviny) ke kořeni (jídlo) stromu. Každý vrchol je buď čistý, nebo špinavý. Abychom vrchol zpracovali, musíme mít hotové všechny jeho podstromy. Práci na podstromech různých synů však můžeme libovolně prokládat. Kdykoliv Kevin přejde ze špinavého vrcholu na čistý, musí si umýt ruce. Ostatní přechody jsou zdarma.
Budeme postupovat od listů a v každém kroku se budeme snažit zpracovat všechny dostupné vrcholy stejné barvy najednou. Dostupný vrchol je takový, jehož všechny děti jsou již zpracovány. Vždy začínáme čistými vrcholy a střídáme barvy až tehdy, když už žádný dostupný vrchol aktuální barvy neexistuje. Tím sdružíme všechny přechody stejné barvy dohromady a minimalizujeme počet přechodů mezi barvami.
Zkusme si teď shrnout, jak to vlastně bude fungovat za použití obousměrné fronty (deque). Do fronty
na začátku vložíme všechny listy stromu tak, že ty čisté budeme přidávat z jednoho konce (např. zepředu) a špinavé
z druhého konce (např. zezadu). Nastavíme aktuální barvu na čistou.
- Pokud je aktuální barva čistá, odebíráme vrcholy ze začátku fronty. Pokud je špinavá, odebíráme je ze konce fronty. Tím zajistíme, že zpracováváme vždy celou vlnu stejné barvy.
- Po zpracování každého vrcholu zkontrolujeme jeho rodiče. Pokud jsou již všechny děti tohoto rodiče hotové, rodič se stává dostupným a vložíme ho do fronty podle jeho barvy – pokud je čistý, vložíme ho na začátek, pokud špinavý, vložíme ho na konec.
- Pokud na příslušném konci fronty už žádný dostupný vrchol aktuální barvy neexistuje, ale fronta ještě není prázdná, přepneme aktuální barvu. Pokud nová barva je čistá, připočteme 1 umytí (přechod ze špinavého na čistý).
- Cyklus opakujeme, dokud není zpracován kořen stromu.
Správnost algoritmu plyne z toho, že každý přechod mezi barvami zaplatíme nejvýše jednou za každou skupinu stejně barevných vrcholů. Kdykoliv bychom pořadí změnili a zpracovali vrcholy různých barev střídavě, počet přechodů by pouze vzrostl.
Až zpracujeme kořen, výsledkem je celkový počet umytí rukou potřebný k dokončení přípravy. Časová a paměťová složitost bude lineární vzhledem k počtu vrcholů, tedy O(N), protože každý vrchol zařadíme do fronty právě jednou a zpracujeme ho právě jednou v rámci příslušné skupiny stejné barvy.