Druhá série třicátého prvního ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Právě si prohlížíte komentáře k úlohám druhé série KSP-H (přesněji k těm, ke kterým jsme uznali, že se komentář hodí). Připomínáme, že od letoška jsou totiž řešení každé série rozdělena na dvě části: na samotná autorská řešení, která vydáváme brzy po termínu série, a komentáře k došlým řešením, která vydáváme až po opravení vašich řešení.
Pokud se vám cokoliv nezdá nebo máte nějaký dotaz, neváhejte se ozvat na našem fóru nebo emailem na známou adresu.
Komentáře k úlohám
31-2-1 Objednávka pily (Zadání) (Řešení)
Poměrně mnoho řešitelů se nenechalo odradit větším bodovým ohodnocením této úlohy a poslalo nějaké více či méně rychlé a funkční řešení. Plný počet bodů se ale podařilo získat jen Davidu Klementovi a Jiřímu Kalvodovi.
Někteří z vás se nechali nachytat následujícím hladovým algoritmem pro variantu za 10 bodů:
- Vstup: Řetězec s
- Nechť p značí délku aktuálního kandidáta na část B. Nastavíme p na 1.
- Postupně pro i = 0, … , N - 1:
- Pokud s[i] = s[i mod p], tedy znak není ve sporu s aktuální volbou B, pokračujeme dále. (i mod p zde označuje zbytek po dělení i / p)
- Jinak řetězec nemůže být periodický s periodou p a nastavíme p ← i.
Problém je v posledním kroku, protože řetězec sice nemůže být periodický s
periodou p, ale stále může být periodický s periodou p < i, kterou takto
přeskočíme. Stane se to například v řetězci abaab, kde je správné řešení
p = 3, B = aba, C = ab, ale my po načtení abaa s p
= 2 nastavíme p ←4.
Algoritmus spravíme tak, že místo p ← i nastavíme jen p ← p + 1 a pak řetězec s novým p zkontrolujeme znovu od začátku, to ovšem vede na kvadratickou časovou složitost.
31-2-3 Oprava střechy (Zadání) (Řešení)
K úloze se sešlo několik pěkných řešení, žádné ale nedosáhlo časové složitosti O(n log n) jako ve vzorovém řešení. Většina z vás úlohu řešila dvojitým zametáním zleva a shora. Ještě jednodušší (ale pomalejší – v O(n log n)) řešení je uvědomit si, že v alespoň jednom z optimálních umístění čtverce bude buď jeden bod ležet v jeho levém horním rohu, nebo jeden bod bude ležet na horní straně čtverce a jeden bod na levé. Pak stačí projít všechny dvojice bodů a spočítat, kolik bodů by v takovémto čtverci leželo.
Zajímavé je také zamyslet se, jak by se úloha změnila, kdyby byly díry hodně hustě rozmístěné. Stačilo by pak vyřešit úlohu na najití podmatice dané velikosti s největším součtem.
31-2-5 Zhasínání pecí (Zadání) (Řešení)
Většina odevzdaných řešení používala nějaký popis kvadratického řešení podobého tomu vzorovému, ale bohužel dost řešitelů nepopsalo jakým způsobem k té kvadratické složitosti došli, či nedodalo nějaké odůvodnění proč by jejich postup vůbec měl fungovat.
Pár z vás se tuto úlohu pokusilo vyřešit poměrně ezoterickým způsobem, a to tak, že se pokoušeli zjistit počet místností tím, že chodili stále jenom jedním směrem a při každém dalším kroku zhasli pec, zvětšili hodnotu v buňce o jedna a kontrolovali, jestli jim náhodou buňka nepřetekla. Ve chvíli, kdy jim buňka přetekla, tak prohlásili, že museli projít všechny místnosti.
Takový postup ale úplně nefunguje, protože jsme v úloze neměli definovaný žádný výpočetní model a tedy vůbec nevíme, co přetečení znamená a jestli k němu vůbec dojde (jestli nám náhodou počítač po přetečení třeba neshoří). Takové řešení bylo tedy spíše chápáno jako hack, než jako opravdové a platné řešení.