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

Právě si prohlížíte komentáře k úlohám poslední letošní 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-5-1 Písmenková polévka (Zadání) (Řešení)


Ukázalo se, že i jednodušší verze úlohy je docela obtížná. Kromě správných úvah o cyklech (podobných vzorovému řešení) se objevilo vícero částečných řešení, která fungovala jen pro některé typy permutací.

Za zmínku ještě stojí následující algoritmus. Použijeme terminologii ze vzorového řešení: zadaná permutace je π, hledáme její druhou odmocninu σ. Pokud π(1) = 1, stačí položit σ(1) = 1 a jsme s jedničkou hotovi. Jinak rozebereme všechny možnosti, kam se jednička zobrazí, tedy co je σ(1).

Pokud zvolíme σ(1)=i, musíme položit σ(i)=π(1), protože π(1) je podle definice rovno σ(σ(1)), a to je σ(i). A jakmile máme určeno σ(i), stejným způsobem dostaneme σ(σ(i)) = π(σ(i)). Můžeme pokračovat dále, až buďto dospějeme zpátky k jedničce, nebo se dostaneme ke sporu – pokusíme se použít číslo, které už jsme použili.

Jestliže jsme dospěli k jedničce, prohlásíme použité prvky za hotové a spustíme algoritmus znovu od libovolného nehotového prvku místo jedničky. Pokud jsme došli ke sporu, zvýšíme i o 1 a zkusíme to znovu.

Snadno dokážeme, že algoritmus běží v nejhůře kubickém čase: spouštíme ho postupně z nejvýše n počátků, pro každý z nich zkoušíme nejvýše n možností pro i a ověřit každou nám trvá O(n). Jako cvičení ponecháme dokázat, že pokud složitost počítáme přesněji, vyjde dokonce O(n2).

No dobrá, ale proč náš algoritmus funguje? To je opět snadno vidět z rozkladu na cykly. Pokud jednička leží na sudém cyklu, budou fungovat jen taková i, která leží na jiném, ale stejně dlouhém cyklu. Jakmile takové i najdeme, sezipovali jsme dva sudé cykly a pokračujeme se zbytkem permutace. Ze vzorového řešení víme, že tím jsme nezměnili, zda odmocnina existuje. A pro lichý cyklus fungují jak i na jiných stejně dlouhých cyklech, tak i na tomtéž cyklu, ale s opačnou paritou.

Toto řešení je tedy také správně, ač o něco pomalejší.

Martin „Medvěd“ Mareš


Teoretická úloha31-5-4 Otesánek ve vývařovně (Zadání) (Řešení)


Většina z vás na to při řešení této úlohy šla ze správného směru a uvědomili jste si, že odkaz na kuchařku vás navádí k tomu použít nějaké vyhledávací stromy, případně haldy. Takovýto odkaz vám také může napovědět, že cílená časová složitost na dotaz je O(log N).

Co bych chtěl vytknout více řešením, bylo ale zbytečné používání hešovací tabulky (asociativního pole nebo slovníku pod jinými názvy – zkrátka pole, které chcete indexovat nějakými jinými věcmi než čísly z malého rozsahu). Většinou jste je používali k věcem, k nimž by s lehkou úpravou vašeho řešení stačilo normální pole indexované čísly vesničanů od 0 do N.

Hešovací tabulky jsou mocná věc a mnoho vysokoúrovňovějších jazyků (jako třeba Python) už má podporu pro ně přímo v základní knihovně – ale jakkoliv je to mocná věc, tak fungují dobře jenom v průměrném případě, pro některé vstupy se mohou „rozbít“. A zrovna v této úloze bylo jejich použití ve všech případech zbytečné a jenom to přidávalo další složitost.

Takže bych jenom připomenul obecně známou poučku, že jednodušší a přímočařejší řešení bývají často ta lepší :)

Jirka Setnička


Teoretická úloha31-5-5 Přísady na pizze (Zadání) (Řešení)


Skoro všechna vaše řešení odpovídala pomalejšímu postupu ze vzorového řešení. Tedy na grafu s N vrcholy a M hranami používala přibližně N volání krabičky a celková časová a paměťová složitost byla O(N + M).

Někteří jste si správně všimli, že nemá smysl přesně řešit aditivní konstantu u počtu volání. Stačí si zvolit libovolné konstantní K a pro všechny grafy na méně vrcholech nahradit volání krabičky explicitním spočítáním nutného počtu přísad. Protože je toto K konstanta nezávislá na vstupu, můžeme dopočítání provést v konstantním čase. Tím dostaneme pro libovolné K řešení, které potřebuje jen N - K volání krabičky a má stále časovou složitost O(N + M).

Logaritmické řešení bohužel nikdo nevymyslel. Ale objevilo se jedno řešení, které potřebovalo N / 2 volání krabičky. Pro zajímavost nastíním jeho myšlenku:

Z grafu nejprve hladově odebereme dvojice vrcholů, které nejsou propojené hranou. Jakmile nemůžeme žádnou dvojici odebrat, znamená to, že nám na zbylých L vrcholech zůstal úplný graf. (Mohlo se klidně stát, že L = 0, ale to ničemu nevadí.) Pro tento graf známe potřebný počet přísad – je to právě L.

Nyní budeme postupně přidávat dvojice vrcholů zpět a po každém přidání dvojice zavoláme krabičku. Nyní již řešení funguje obdobně jako pomalejší vzorové. Jen je důležité si všimnout, že přidáním dvojice vrcholů vzroste nutný počet přísad maximálně o 1, protože na oba vrcholy můžeme použít stejnou přísadu. Protože je dvojic maximálně N / 2, je tímto omezený i celkový počet volání krabičky.

Jenda Hadrava