Druhá série začátečnické kategorie dvacátého šestého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 26-Z2-1: Had z domina
- 26-Z2-2: SADO
- 26-Z2-3: Šifrovaná zpráva
- 26-Z2-4: Životně důležitá úloha
- 26-Z2-5: Nedopité skleničky
- 26-Z2-6: Čtecí hlavy
26-Z2-1 Had z domina (Zadání)
Které kostky může Kevin otočit, aby součet čísel v obou řadách hada byl sudý? Nabízí se snadné dřevorubecké řešení: vyzkoušet všecky možnosti. To v tomto případě znamená zkoušet otáčet každou kostku a průběžně kontrolovat součty. Budou-li po otočení kostky součty teček v obou řadách sudé, přičteme k výsledku jedničku.
Takto jistě nalezneme správný výsledek, ale pro každou kostku musíme sečíst N čísel v horní i dolní řadě, a těch kostek je N. Asymptotická časová složitost je tedy O(N2).
Had v zadání měl největší délku 1000, takže bylo potřeba nanejvýš řádově milion výpočtů. I tímto postupem se dalo dosáhnout plného počtu bodů. S tím se ale nespokojíme.
Představte si, že by Zuzka měla milion kostek místo tisíce, pak by takový výpočet na běžném počítači trval určitě více než čtvrt hodiny. A s většími vstupy ještě déle. Souvisí to s rychlostí různých algoritmů, dočtete se o nich v naší kuchařce o složitosti.
Zkusme se na to podívat jinak. Zjistíme, že skácet celý les není potřeba, nemusíme počítat všechno. Úloha se dá řešit i rychleji.
Sudost nebo lichost čísla nazýváme stručně jedním slovem parita. Využijeme pozorování, že součet posloupnosti čísel má stejnou paritu jako součet jejich zbytků po dělení dvěma. Stačí nám tedy sečíst místo čísel ty zbytky a nakonec zjistit zbytek celého součtu po dělení dvěma. K tomu se hodí operace modulo. Výsledek bude ta parita. (Také můžeme modulit už během sčítání, při načtení sudého čísla paritu zachovat, při načtení lichého otočit, to je to samé.)
To také znamená, že když Kevin otočí kostku se dvěma sudými čísly, parity součtů sloupců se nezmění. Vymění se jenom nula za nulu. Stejně tak se dvěma lichými čísly. A naopak, když Kevin otočí kostku s jedním lichým a jedním sudým číslem, parity se otočí, protože v jedné řadě bude o jedničku míň a v druhé o jedničku víc. Sudé číslo plus nebo mínus jedna je vždy liché, z lichého se stane sudé.
Parity obou řad kostek si spočítáme jedním průchodem. Pokud mají obě řady na začátku sudou paritu (stručně řečeno parita řad je sudá-sudá), budeme otáčet kostky se stejnou paritou (říkejme jim „stejné“), aby se sudá-sudá zachovala. Jako výsledek tedy vypíšeme jejich počet. U lichá-lichá naopak budeme otáčet „různé“ kostky, tím nám vznikne sudá-sudá, a to přesně chceme.
Ještě může nastat možnost lichá-sudá a sudá-lichá. V takových případech nemáme co otáčet. Otáčením kostek umíme paritu buďto zachovat, nebo otočit. Z toho sudou-sudou nevyrobíme, proto vypíšeme jako výsledek nulu.
Kolik kostek je „stejných“ a kolik „různých“ si můžeme spočítat během jednoho průchodu vstupu zároveň s počítáním parit. Podle nich vypíšeme výsledek.
Vstup je na dvou řádcích. První řadu si tedy musíme uložit do paměti, abychom u čtení té druhé věděli, jaké bylo to první číslo na příslušné kostce. Paměťová složitost bude kvůli tomu lineární (stejně jako u dřevorubeckého řešení), časová ale jen O(N) místo O(N2). Stačí nám totiž jen jeden průchod.
26-Z2-2 SADO (Zadání)
Nejprve si připomeneme některé užitečné matematické pojmy. Nejmenší společný násobek čísel a a b je nejmenší číslo takové, že ho lze beze zbytku vydělit a i b. Největší společný dělitel je naopak největší číslo takové, které beze zbytku dělí obě čísla. Jak na ně ale v programu přijít? Na výpočet největšího společného dělitele se používá Euklidův algoritmus. Kdo jej nezná, nechť se podívá do ukázkového kódu k této úloze. Jak funguje a jak je rychlý, se můžete dočíst v kuchařce o teorii čísel.
Na výpočet nejmenšího společného násobku podobný algoritmus neexistuje, protože není potřeba. Platí totiž následující vztah:
Na nejmenší společný násobek tedy přijdeme vydělením součinu čísel x a y na vstupu jejich největším společným dělitelem.
Kdo ovšem Euklidův algoritmus neznal, mohl na nejmenší společný násobek přijít jednoduše postupným zkoušením násobků čísla x, zda náhodou nejsou dělitelné y. To pro rychlé řešení úlohy bohatě stačilo.
A jak to celé souvisí se zadanou úlohou? Všechna čísla dělitelná zároveň x a y musí být nějakým násobkem nejmenšího společného násobku. A kolik takových čísel nalezneme v intervalu [a, b] zjistíme třeba tak, že spočítáme počet násobků v intervalu [0, b] a odečteme jejich počet v [0, a - 1]. Obě hodnoty spočítáme jednoduchým dělením.
26-Z2-3 Šifrovaná zpráva (Zadání)
Ke zdárnému vyřešení úlohy si budeme muset zkonstruovat nějakou šifrovací
tabulku, která každému písmenu z rozsahu A-Z přiřadí odpovídající písmeno
v zašifrovaném dopisu. Technicky to můžeme lehce zrealizovat pomocí jednoho pole
o 26 prvcích – i-tý prvek bude vyjadřovat, na co se přeloží i-tý znak abecedy.
V ukázkovém programu využíváme toho, že písmena jsou v ASCII
tabulce umístěna za sebou a převod písmene
na nějaké číslo uděláme jednoduše (bez nutnosti vědět, jaké přesně číslo
v tabulce má) tím, že od něj odečteme hodnotu znaku A. Samotné A tak
dostane hodnotu 0, B hodnotu 1 a tak dále. Jinou metodou je například
použití asociativního pole, které nám poskytuje jazyk Python.
Když už máme technické detaily za sebou, stačí nám jen znak po znaku projít původní i zašifrovaný text a ke každému znaku původní zprávy uložit do šifrovací tabulky znak, na který je původní znak zašifrovaný. Toto by skvěle fungovalo, kdybychom měli slíbeno, že zpráva je vždy zašifrována správně. Jak však poznat chyby?
Důležité je uvědomit si, jaké chyby se nám mohou vyskytnout. Možné chyby jsou dvě. První z nich nastane, pokud stejné písmeno zašifrujeme dvakrát na písmena různá. To ale poznáme snadno, stačí nám přidat jednoduchou kontrolu u vyplňování naší šifrovací tabulky: Pokaždé, když budeme zpracovávat nějaký znak, se podíváme, jestli jsme mu už náhodou nepřiřadili nějaký znak dříve. Pokud ano a znaky jsou stejné, je vše v pořádku. Pokud se však znaky liší, zahlásíme chybu.
Druhá chyba nastane, pokud se dva různé znaky původní zprávy pokusíme zašifrovat na stejný znak zašifrované zprávy. V tomto místě nám pomůže další kontrola, ke které ale už budeme potřebovat druhou tabulku, říkejme jí třeba tabulka použitých znaků.
Vždy, když budeme přidávat nový záznam do šifrovací tabulky, poznačíme si do tabulky použitých znaků, že tento znak je již zabraný. Pokud pak narazíme na to, že námi chtěný znak již byl použit dříve, nezbude nám nic jiného, než také nahlásit chybu.
Mohlo by se zdát, že tím máme úlohu už zdárně vyřešenou a zašifrovanou zprávu zkontrolovanou. Ale ouha, zbývá nám ještě jedna drobnost na závěr – doplnit zbytek abecedy.
To je však už maličkost. Jen postupně projdeme šifrovací tabulku a u každého znaku, který doposud nemá přiřazený svůj zašifrovaný ekvivalent, najdeme první nepoužitý znak v tabulce použitých znaků. Ten přiřadíme a stejným způsobem doplníme celou abecedu.
Práce, kterou náš program musí udělat, je jednou projít původní i zašifrovaný text od začátku do konce a pak ještě celou abecedu. To, pokud si délku textu označíme jako N a velikost abecedy budeme brát jako malou konstantu, vede na celkovou časovou složitost O(N).
26-Z2-4 Životně důležitá úloha (Zadání)
Připomeňme, že zadáním úlohy bylo v zadané posloupnosti o N číslech A = a0, a1,…,aN-1 nalézt všechny prvky s aritmetickým výskytem. Výskyt prvku x je aritmetický, pokud je posloupnost pozic, na kterých se prvek x v posloupnosti A nachází, aritmetická.
Prvky s aritmetickým výskytem mají být vypsány ve vzestupném pořadí a má u nich být uvedena i diference příslušné aritmetické posloupnosti. (Pokud má prvek jediný výskyt v celé posloupnosti A, chápeme jej jako prvek s aritmetickým výskytem o diferenci 0.)
Zdá se přirozené pevně si zvolit jeden prvek posloupnosti a ověřit, zda je jeho výskyt aritmetický. Pokud si však posloupnost A nepředzpracujeme, můžeme pro každý prvek projít celou posloupnost A (nebo její významnou část), což povede k řešení se složitostí O(N2). S tou se nespokojíme.
Hodilo by se seskupit prvky posloupnosti A se stejnou hodnotou vedle sebe, abychom „aritmetičnost“ výskytů ověřovali rychle. Pokud ale posloupnost A rovnou setřídíme, ztratíme informaci o pozicích prvků a nebudeme schopni aritmetičnost výskytu ověřit.
Tento problém snadno obejdeme – nebudeme třídit pouhé prvky posloupnosti A, ale budeme třídit posloupnost dvojic. K tomu účelu si zaveďme posloupnost S = s0,…,sN-1, v níž si = (ai, i). Tedy i-tá dvojice udává hodnotu prvku na i-té pozici společně s touto pozicí.
Dvojice posloupnosti setřídíme podle slovníkového uspořádání (známé také pod cizojazyčným ekvivalentem lexikografické). Dvojice porovnáme podle první složky a v případě shody dále podle druhé. Například setříděním posloupnosti dvojic (1,2), (0,1), (1,0), (1,1) lexikograficky bychom získali posloupnost (0,1), (1,0), (1,1), (1,2).
Uvědomme si, že v okamžiku, kdy definujeme vlastní funkci pro porovnávání dvojic, neliší se třídění posloupnosti dvojic nijak od třídění posloupnosti čísel. Pokud s třídicími algoritmy nejste obeznámeni, nahlédněte do naší kuchařky.
Když je posloupnost S lexikograficky setříděna, máme už výskyty každého prvku hned za sebou a ve vzestupném pořadí. Přímým průchodem pak ověříme, zda jsou posloupnosti výskytů jednotlivých prvků aritmetické.
Časová složitost třídění je O(N log N), všechny ostatní části algoritmu už zvládneme v lineárním čase. Proto můžeme celkovou časovou složitost stanovit jako O(N log N). Krom několika proměnných si stačí pamatovat pouze posloupnost S, proto je prostorová složitost lineární.
Závěrem si dovolíme ještě jeden mírně odlišný náhled řešení. Místo třídění posloupnosti dvojic můžeme od počátku udržovat pro každou hodnotu ze vstupní posloupnosti přihrádku. Při průchodu posloupnosti pak pro každý prvek rovnou vložíme jeho pozici do příslušné přihrádky. Na závěr zkontrolujeme, které přihrádky obsahují aritmetickou posloupnost.
Čísla v posloupnosti mohou dalece převyšovat délku posloupnosti, proto by přístup k jednotlivým přihrádkám přes pole nemusel být efektivní. Jak k nim přistupovat efektivně? K těmto účelům lze použít některou z datových struktur, které se skrývají pod souhrnným označením „asociativní pole“.
26-Z2-5 Nedopité skleničky (Zadání)
Cílem úlohy bylo najít v setříděné posloupnosti dvě čísla (nemusí být nutně těsně za sebou), jejichž rozdíl se co nejvíce blíží číslu K. Nejjednodušším (ale pomalým) řešením tohoto problému by bylo projít každé dvě skleničky, odečíst jejich hladiny a porovnat velikost tohoto rozdílu s K.
Jak toto realizovat? Nejdřív se hodí si skleničky očíslovat. Ve většině programovacích jazyků má první prvek pole index 0, takže budeme skleničky stejně číslovat i my (od 0 do N-1). Dále si stačí pamatovat, jaký rozdíl mezi dvěma skleničkami byl nejblíže ke K (označme toto číslo min, na začátku nechť je v něm třeba ∞) a které dvě skleničky to byly (označme S1, S2). Pak pro každou skleničku vyzkoušíme všech N-1 dalších a při zkoušení každých takových dvou skleniček porovnáme, jestli je velikost rozdílu jejich obsahů ke K bližší než min. Pokud ano, aktualizujeme min i skleničky S1 a S2. Řekněme, že do S1 uložíme číslo skleničky s menším obsahem šampaňského. Až projdeme všechny dvojice skleniček, bude v S1 řešení, tedy číslo skleničky (počítáno od nulté), do které má Kevin nalít zbytek šampaňského.
Takové řešení prochází každou dvojici skleniček a provádí na nich porovnání. Proto má časovou složitost O(n2). Jak jej zrychlit? Můžeme využít seřazenosti skleniček. Všimneme si, že pokud porovnáme i-tou a j-tou skleničku a rozdíl je už moc velký, tak rozdíl mezi i-tou a (j+1)-ní skleničkou bude ještě větší. Nemá tedy smysl porovnávat i-tou s (j+1)-ní a jakoukoliv další a můžeme místo toho i posunout o jedna dál a porovnávat (i+1)-ní a j-tou. Obdobně, jen obráceně, to funguje i v případě, že rozdíl je menší než K.
K realizaci použijeme dvě čísla (řekněme A a B), která budou označovat dvě aktuální pozice v posloupnosti skleniček. Tyto dvě skleničky označené čísly budeme v každém kroku porovnávat. Pokud budou skleničky očíslované od 0 do N-1, bude na počátku A = 0 a B = 1. Posloupnost skleniček si označíme jako s, tedy si bude množství tekutiny v i-té skleničce. Nyní můžeme procházet posloupnost s a hledat, pro která A a B bude sB - sA co nejblíž ke K.
V každém kroku porovnáme sB - sA s K. Pokud je sB - sA > K, zvětšíme A o 1, jinak zvětšíme B o 1. Zároveň pro každou dvojici kontrolujeme, jestli není lepší než doposud nejlepší řešení a upravujeme min, S1 a S2 – úplně stejně jako v pomalém řešení. Pokud A = B, tedy A „dohnalo“ B, posuneme B o 1 doprava. Pokud B > (N-1), prošli jsme všechny vhodné dvojice skleniček a můžeme skončit. V S1 bude opět uloženo řešení.
Toto řešení v každém kroku posune A nebo B alespoň o 1, vždy platí B ≥ A a při B > (N-1) skončí. Maximálně tedy udělá 2N kroků. Když zanedbáme onu dvojku, už víme, že má lineární časovou složitost O(N). Co se paměti týče, ukládáme konstantní počet čísel: A, B, min, S1, S2, N. Připočteno k velikosti vstupu načteného do paměti nám tedy vychází lineární paměťová složitost O(N).
26-Z2-6 Čtecí hlavy (Zadání)
Řešení této úlohy se řídí myšlenkou: „Pokud existuje jen málo možností, tak je vyzkoušíme všechny a z nich vybereme tu nejlepší.“ To je v informatice poměrně častý postup. Při aplikaci tohoto pravidla si však musíme dát pozor, obecně totiž může být zkoušení všech možností velmi neefektivní. Když se nám ale povede nalézt jen málo možností, mezi kterými určitě bude i ta úplně nejlepší, máme vyhráno.
Při čtení pomocí jedné hlavy máme pouze dvě možnosti. Buď hlava nejdříve pojede směrem k nejlevějšímu segmentu a pak směrem k nejpravějšímu segmentu, a nebo naopak nejdřív k nejpravějšímu a pak k nejlevějšímu. Z těchto možností vybereme tu lepší a máme výsledek. Časová složitost tohoto výpočtu je konstantní, ale časová složitost celého algoritmu je lineární (konkrétně O(N), kde N je počet čtených segmentů), protože musíme načíst vstup a zjistit, který segment je nejlevější a který nejpravější.
Při čtení pomocí dvou hlav máme také jen málo možností. Všimneme si, že v optimálním řešení levá hlava přečte nějaký počáteční úsek vybraných segmentů a pravá hlava přečte zbytek vybraných segmentů, které zas tvoří nějaký koncový úsek vybraných segmentů. Tyto dva úseky pokrývají dohromady všechny vybrané segmenty a nekříží se.
Bude mezi takovými řešeními určitě i to optimální? Ano, bude! Pokud by se obě hlavy měly po cestě křížit, tak namísto toho budeme uvažovat situaci, kdy se od sebe hlavy odrazí a to, co původně měla jet jedna hlava, pojede druhá hlava a naopak. Není tedy výhodné, aby si hlavy vyměnily pozice – levá hlava tedy celou dobu zůstane levou a pravá hlava pravou.
A co úsek čtený levou hlavou a úsek čtený pravou hlavou? Může být výhodné jejich překrytí? Také ne, protože nemá smysl, abychom nějaký segment četli dvakrát.
Stačí nám tedy vyzkoušet všechny možnosti. Pro souřadnice segmentů s1 < s2 < ...< sN vyzkoušíme možnosti, kdy levá hlava bude číst segmenty s1, … , si a pravá hlava bude číst segmenty si+1, … , sN. Pozor, nesmíme zapomenout na možnosti, kdy levá resp. pravá hlava čte všechny segmenty.
Za jak dlouho hlava přečte konkrétní úsek segmentů zjistíme pomocí výpočtu pro jednu hlavu. Tedy hlava buď nejdříve pojede k nejlevějšímu a pak k nejpravějšímu segmentu čteného úseku, nebo naopak. Celý algoritmus má časovou složitost O(N), máme dohromady N+1 možností a výpočet každé z nich zabere konstantní čas. Pokud bychom souřadnice segmentů na vstupu nedostali setřízené, museli bychom je v čase O(N log N) setřídit.
Paměťová složitost varianty pro jednu hlavu je konstantní (značíme O(1)) – stačí nám si pamatovat pouze souřadnici nejlevějšího a nejpravějšího segmentu. Paměťová složitost varianty pro dvě hlavy je lineární (značíme O(N)) – pamatujeme si N souřadnic segmentů a pak několik málo (konstantně) dalších pomocných proměných.
Pro lepší představu řešení nahlédněte do okomentovaného zdrojového kódu. Zdrojový kód je v jazyce C++, jeho znalost by však neměla být nutná pro pochopení programu.