Třetí série začátečnické kategorie třicátého čtvrtého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 34-Z3-1: Otočená morseovka
- 34-Z3-2: Tečkový displej
- 34-Z3-3: Tabulky a olympiáda
- 34-Z3-4: Velikost plachet
34-Z3-1 Otočená morseovka (Zadání)
Začneme tím, že si text převedeme do morseovky. Pro každé písmeno v textu známe jeho odpovídající kód a tyto kódy pro jednotlivá slova spojíme za sebe, kde mezi kódy pro jednotlivá písmena připíšeme
/, jak bývá v morseovce zvykem. Tak dostaneme kód pro celou zprávu.
Nyní nás zajímá, zda je tento kód palindrom, tedy zda se čte zepředu stejně jako zezadu. Pokud tomu tak je, pak budeme-li zprávu číst zezadu, interpretujeme ji stejně jako popředu. Zjistit, zda je řetězec palindrom, můžeme například tak, že jej zkopírujeme, otočíme a následně porovnáme s původním řetězcem.
Jelikož počet znaků v morseovce je pro každý znak abecedy nejvýše 5, celková velikost zprávy v morseovce je O(L), kde L je délka původní zprávy. Otáčení a porovnávání řetězců je lineární vzhledem k délce řetězce, tedy časová složitost je pro každý příklad O(L) a celková složitost přes všechny zprávy je lineární se součtem délek zpráv. Jelikož můžeme zprávy zpracovávat postupně, celková paměťová složitost je lineární vzhledem k nejdelší zprávě.
Ukažme ještě, že převádět zprávy do morseovky vůbec není potřeba. Protože písmena
oddělujeme /, můžeme palindrom kontrolovat po celých písmenách.
Kód prvního písmene musí být otočením kódu posledního písmene,
kód druhého písmene otočením předposledního atd. Tudíž si stačí pro každé písmeno
zapamatovat, jaké písmeno odpovídá jeho obrácenému kódu. Například otočením kódu
B dostaneme kód V a naopak. Otočenému kódu C žádný kód
neodpovídá, pokud se tedy ve zprávě vyskytuje, zpráva určitě není palindrom.
Stačí tedy, když projdeme zprávu a pro i-té písmeno zepředu zkontrolujeme, že i-té písmeno zezadu je jeho protějšek. Časová i paměťová složitost zůstává stejná, ale s lepšími konstantami, protože zpráva zapsaná písmeny je kratší než zpráva v morseovce.
34-Z3-2 Tečkový displej (Zadání)
Začneme načtením všech zastávek a porouchaných displejů. Potom každý porouchaný
displej porovnáme se všemi zastávkami a spočítáme, kolik zastávek odpovídá
danému porouchanému displeji. Pokud odpovídá právě jedna zastávka, pak je
jednoznačné, jaká zastávka následuje, takže vypíšeme ANO.
V opačném případě vypíšeme NE.
Samotné porovnání, jestli zastávka odpovídá porouchanému displeji, je jednoduché. Stačí zkontrolovat, jestli jsou všechny rozsvícené pixely na porouchaném displeji rozsvícené i na displeji zastávky.
Časová složitost je O(RSMN). Máme totiž M porouchaných displejů a každý porovnáváme s N zastávkami. Zároveň má každý displej R ×S pixelů, které musíme v nejhorším případě projít.
34-Z3-3 Tabulky a olympiáda (Zadání)
Využijeme každý vzoreček, na který narazíme a jehož vstupy známe a výsledek nikoliv. Až spočítáme výslednou veličinu, tak můžeme program ukončit.
Budeme opakovaně procházet seznam vzorečků. U každého vzorečku budeme zjišťovat, zda je použitelný, tedy jeho vstupní veličiny jsou známé a výstupní veličina není. U takového vzorečku si jeho výslednou veličinu označíme jako známou a daný vzoreček vypíšeme na výstup. Procházení ukončíme, pokud prohlásíme za známou veličinu X, nebo jsme při posledním průchodu nevypsali žádný vzorec. Do té doby procházíme vzorečky pořád dokola.
Již spočítané veličiny si můžeme ukládat do nějaké množiny, například hashovací tabulky nebo vyvažovaného vyhledávacího stromu.
Jelikož po nás zadání nechce nejkratší možný výpočet, je toto řešení korektní. Když vypočítáme něco navíc, tak to rozhodně nevadí a je jedno, jak ke spočítání každé veličiny dojdeme. Kdybychom se zastavili, aniž bychom znali veličinu X, zbytek vzorců, včetně vzorců s výstupem X, nejde spočítat se zadanými veličinami. Tento případ však nenastane – zadání zaručuje, že řešení vždy existuje.
Jak je naše řešení rychlé? Označme N počet na začátku známých veličin a M počet vzorečků. Na začátku musíme vložit známé veličiny do množiny. Každým průchodem seznamu vzorečků spočítáme alespoň jednu novou veličinu, průchodů tedy bude nejvýše M. V každém průchodu vyhodnocujeme M vzorečků, každý pomocí konstantně mnoha operacemi s množinou (vložení či dotazů). Celkem je tedy potřeba O(N + M2) množinových operací.
Časová složitost operace s množinou je O(1) průměrně (pro hashovací tabulku) resp. O(log(N+M)) v nejhorším případě (vyhledávací strom). Celková složitost tedy je O(N+M2) resp. O((N+M2) log(N+M)). Kdyby byly vzorečky na vstupu seřazené v opačném pořadí, než by bylo potřeba, tak náš algoritmus skutečně v každém průchodu použije jen jeden a tedy uvedené odhady nelze zlepšit.
Tedy budeme muset zlepšit algoritmus! Všimneme si, že v každém průchodu má smysl dívat se jen na vzorečky, u kterých jsme alespoň jednu veličinu spočítali v minulém průchodu. Tím sice vzorečky, které bychom spočítali ve stejném průchodu jako poslední z jejich vstupu, odložíme na další průchod, ale to nevadí. Jinak se nic nezmění. Jen vynecháme vzorečky, které již mají oba dva vstupy dávno spočítané (a tedy i jejich výstup je již taky spočítaný) a vzorečky, které ještě nemají spočítané oba dva vstupy.
Na začátku algoritmu si tedy jen připravíme pro každou veličinu seznam vzorečků, které ji využívají. Jedním průchodem vzorečků tyto seznamy naplníme. Pak si vždy budeme pamatovat veličiny spočtené v minulém kole a vždy projdeme jen jejich příslušné seznamy. Na začátku projdeme seznamy známých veličin.
Každý seznam projdeme jen jednou, protože každou veličinu spočítáme jen jednou. Každý vzoreček tedy uvidíme nanejvýš dvakrát. Celková časová složitost tedy bude O(N+M) resp. O((N+M) log(N+M)) v závislosti na implementaci množiny.
Poznámka: V odhadech složitosti byla pro jednoduchost délka názvů veličin považovaná za konstantní. Pro přesnější odhad složitosti by bylo nutně uvažovat délku veličin v množinových operacích a kontrole vzorců.
34-Z3-4 Velikost plachet (Zadání)
Možností, jak rozvěsit plachty, je až faktoriál počtu ráhen, tedy i počtu stěžňů. Budeme tedy muset přijít s chytřejším řešením i za cenu složitějšího důkazu správnosti.
Intuitivně se nabízí párovat nejdelší ráhna s nejdelšími stěžni. Čím větší konstanta a, tím rychleji lineární funkce ax roste. Dává tedy smysl z největšího možného a vytěžit co nejvíce, a pak teprve řešit pomaleji rostoucí funkce. Myšlenku máme, pojďme ji tedy přetavit ve formální důkaz.
Nechť R je délka nejdelšího ráhna a S délka nejdelšího stěžně. Ukážeme, že mezi optimálními řešeními určitě existuje takové, kde R a S jsou v páru. Podívejme se na jedno z optimálních řešení: V něm existují páry Rs a rS pro nějaký stěžeň s a nějaké ráhno r. Ukážeme si, že nahrazením těchto párů za RS a rs se řešení nezhorší. Tedy, že platí:
To můžeme dále upravovat:
Ekvivalentními úpravami jsme dospěli k pravdivé rovnici, protože R≥ r a S≥ s, tedy levá strana je součinem nezáporných závorek.
Teď víme, že R a S jsou určitě spolu v páru. Proto je můžeme odebrat a se zbytkem řešit úlohu identicky.
Na závěr poznamenejme, že opakované hledání nejdelších součástí se dá usnadnit tím, že si stěžně i ráhna na začátku seřadíme. Na to nám bude stačit čas O(n · log n) a paměť O(n), kde n je počet plachet. Do stejné složitosti se vejdeme i s lineárním průchodem přes seřazené součásti a jejich párováním.