Třetí 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 třetí 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-3-4 Dláždění sálu (Zadání) (Řešení)
Většina řešení, které jste nám poslali, převáděla dlaždičkování na existenci sledu dané délky ve vhodném grafu. (Sled je podobně jako cesta nějaká posloupnost na sebe navazujících hran, ovšem vrcholy a hrany se v ní mohou opakovat.)
Graf můžeme vytvořit třeba tak, že vrcholy budou všechny K-tice barev pod sebou a orientované hrany natáhneme mezi těmi K-ticemi, mezi které se dá vložit sloupeček K dlaždiček tak, aby barvy navazovaly. Pak stačí zjistit, zda existuje sled délky právě N z obarvení levé stěny do obarvení pravé stěny. To jde provést podobně jako ve vzorovém řešení v čase O(N). Vylepšení na O(log N) pomocí zdvojování nikoho nenapadlo.
Zato hned několik řešitelů vymyslelo, že úlohu jde vyřešit v konstantním čase, protože stačí zjistit, zda se délka nějaké cesty spolu s násobky délek vhodných cyklů mohou poskládat na N. Žádné z těchto řešení nebylo správně, většinou přehlížela to, že cykly lze vlepovat nejen do cest, ale také do jiných cyklů. Tyto problémy je nicméně možno opravit. To vede k následujícímu poněkud divokému řešení, které má opravdu konstantní časovou složitost. Děkujeme za inspiraci jak jim, tak kolegovi Vladanovi Majerechovi.
Máme nějaký konstantně velký orientovaný graf s vrcholy u a v a chceme umět pro libovolné N zjistit, zda existuje sled délky přesně N z u do v.
Budeme konstruovat množiny Si (i=0,… ,N) všech vrcholů, do kterých se jde dostat z u sledem délky i. Množina S0 tedy obsahuje jen u, v množině S1 jsou následníci vrcholu u (tak říkáme vrcholům, do nichž z u přímo vede hrana), v množině S2 jsou následníci všech vrcholů z S1 atd. Obecně v Si jsou všechny vrcholy y, do kterých vede hrana z nějakého x∈Si-1. Až sestrojíme množinu SN, stačí se podívat, jestli v ní leží vrchol v.
Jelikož každou množinu můžeme získat z té předchozí v konstantním čase, tento postup vede na řešení v čase O(N). To není nic nového, tak rychlé je i vzorové řešení, a dokonce se v něm konstruují množiny Si velmi podobného významu.
Teď si ale všimneme důležité věci: možností, jak může množina Si vypadat, je jen konečně mnoho. Proto je-li N hodně velké, nějaké dvě množiny se musí rovnat. Jenže každá množina je jednoznačně určená tou předchozí, takže jakmile se množina zopakuje, bude se od tohoto místa opakovat celá posloupnost množin.
Můžeme to modelovat dalším grafem. Jeho vrcholy budou odpovídat všem podmnožinám množiny všech vrcholů (takže speciálně každá Si odpovídá nějakému vrcholu). Jako U označíme vrchol odpovídající množině {u}. Černou barvou označíme vrcholy, jejichž množina obsahuje vrchol v; zbylé vrcholy budou bílé. Hrana povede z X do Y, pokud by z X=Si plynulo Y=Si+1. Původní úloha je tedy ekvivalentní s tím, zda v novém grafu existuje sled délky N z U do jakéhokoliv černého vrcholu.
Nový graf má ovšem velmi speciální strukturu: z každého vrcholu vede právě jedna hrana. Část dosažitelná z U tedy musí mít tvar cesty, která se napojuje na kružnici (takovým grafům se říká „lízátka“). Jakmile známe délku cesty D a délku kružnice K, umíme říci, do kterého vrcholu lízatka se dostaneme po právě N krocích: pokud N<D, je to N-tý vrchol cesty; pokud N≥ D, jedná se o ((N-D) mod K)-tý vrchol kružnice.
Postačí tedy sestrojit nový graf, spočítat D a K a zapamatovat si, které vrcholy lízátka jsou černé. Výpočet těchto věcí nezávisí na N, takže pro potřeby naší úlohy proběhne v konstantním čase. Pak spočítáme, do kterého vrcholu lízátka nás zavede N-tý krok, a odpovíme podle toho, zda je tento vrchol černý nebo bílý. Zde už N používáme, ale provádíme pouze konstantní množství operací.
Upozorňujeme ovšem, že konstanty v tomto řešení jsou gigantické: počet vrcholů prvního grafu je exponenciální ve velikosti vstupu a počet vrcholů druhého grafu je exponenciální v počtu vrcholů prvního grafu. Naše původní řešení v čase O(log N) je tedy velmi pravděpodobně rychlejší pro všechna N, která se vejdou do našeho Vesmíru.