Druhá série třicátého prvního ročníku KSP

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


Teoretická úloha31-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ů:

  1. Vstup: Řetězec s
  2. Nechť p značí délku aktuálního kandidáta na část B. Nastavíme p na 1.
  3. Postupně pro i = 0, … , N - 1:
  4. 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)
  5. 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í abaap = 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.

Ríša Hladík


Teoretická úloha31-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.

Zuzka Urbanová


Teoretická úloha31-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í.

Jirka Beneš


Teoretická úloha31-2-6 Hroznýš v událostech (Zadání) (Řešení)


Komentář k vašim řešením brzy dodáme.

Maria Matějka