První série dvacátého druhého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Řešení úloh

• 22-1-1: Alčina interpretace
• 22-1-2: Sad
• 22-1-3: Sazba
• 22-1-4: Bludiště
• 22-1-5: Šachovnice na pneumatice
• 22-1-6: Náhradní
• 22-1-7: Když telefony pekly jazyk

22-1-1 Alčina interpretace (Zadání)

Úlohou bylo najít cestu P = (s = v₀, v₁, … , v_n = c ), na které se nejméně mění značky na hranách.

Pro řešení je třeba modifikace algoritmu pro hledání nejkratší cesty. Chtěli bychom, aby se algoritmus ve fázi i rozlil do všech vrcholů, které jsou od počátečního vrcholu vzdáleny přesně i změn. To nám samotný algoritmus procházení do šířky nezaručí. Pokud ale v každé fázi provedeme procházení do hloubky po hranách se stejnou značkou, projdeme graf přesně tak, jak chceme.

Uděláme menší trik a rozdělíme si každý vrchol na dva, podle toho, kterou hranou jsme do něj přišli. U každého vrcholu si budeme pamatovat značku hrany, která do něj vedla, a jeho předka. Jako datová struktura pro naše prohledávání nám bude sloužit obousměrný seznam. Pokud budeme přidávat na hlavu seznamu, tak bude sloužit jako zásobník, pokud přidáme vrchol na konec seznamu, tak budeme mít frontu. Díky tomu nejprve projdeme všechny hrany se stejnou značkou a až pak teprve ty s jinou. Na začátku přidáme do fronty oba počáteční vrcholy +s i -s. Nyní odebíráme vrcholy z hlavy seznamu, dokud není prázdný. Pro každý vrchol v se podíváme na všechny jeho sousedy, pokud jsme v nich ještě nebyli, tak jim nastavíme v jako předka, označíme je jako prošlé a zařadíme do seznamu podle toho, jestli jsme se do nich dostali po hraně stejné nebo různé značky jako do v. Ve chvíli, kdy ze seznamu vytáhneme cílový vrchol, známe nejkratší cestu k němu.

Nakonec už zbývá jen zrekonstruovat cestu. Tady nám hodně pomůže, že jsme si vrcholy rozdělili, protože tak jsou jejich předci jednoznačně určeni. Stačí jen postupovat od cílového vrcholu rekurzí po předcích, dokud nedorazíme do počátečního.

Vrcholů máme kvůli rozdělení dvakrát více, ale to nám složitost nepokazí. Každý z nich přidáme do seznamu jen jednou. Časová složitost našeho prohledávání bude tedy O(n+m). Paměťová složitost bude lineární. Kromě zadaného grafu potřebujeme v paměti jen frontu na ukládání vrcholů.

Bylo by možné použít i jiné algoritmy, např. Dijkstrův algoritmus. Ten jsme ovšem v podstatě použili, jen nepotřebujeme prioritní frontu, protože si dovedeme vrcholy uspořádat sami.

Program

David Marek

22-1-2 Sad (Zadání)

Fareyovy posloupnosti

"Však se podívej na druhou úlohu – Catalanova čísla a nic jiného!"

My, organizátoři, máme pro Alčino mladistvé nadšení slabost a většinou se snažíme jednat tak, abychom její ideály nepoškodili svým stařeckým pragmatismem. Ale vymýšlet kvůli tomu úplně nové a nikým jiným netušené úlohy? Tůdle. Druhá úloha byla na Fareyovy posloupnosti a nic jiného.

Naštěstí to nikdo z vás nerozpoznal: nejčastějším vaším obratem bylo nagenerovat si všechny rozumné zlomky, očistit je a uspořádat. To může a nemusí být dobrý nápad! Počet generovaých zlomků je evidentně v O(N²), takže užijete-li takové metody, nebude váš algoritmus běžet v čase lepším – co když ale existuje sofistikovaný lineární algoritmus? Nebudete se mu moci rovnat.

Číselná teorie

Následuje složitý matematický důkaz, proč nelze Fareyovy posloupnosti zkonstruovat rychleji než v Ω(N²). Pokud se na to necítíte, raději ho nečtěte, a pokračujte nadpisem Implementace.

Potřebujeme zjistit, jak dlouhá taková Fareyova posloupnost pro dané N vlastně je. Pokud by se stalo, že je její délka také v Ω(N²), byla by výše uvedená obava lichá a vaše postupy stále mohly být optimální.

Slyšeli jste už někdy o Riemannově hypotéze, a jak skvělá matematikům přijde? Teď se k ní přiblížíme tak blízko, jak se středoškolskému informatikovi málokdy naskytne – užijeme Riemannovy funkce zeta!

Členy Fareyovy posloupnosti řádu N jsou takové členy množiny všech zlomků s přirozeným číslem menším nebo rovným N ve jmenovateli, které jsou v intervalu ⟨0, 1⟩ a které nemají soudělný čitatel a jmenovatel. Takže abychom odhadli jejich počet, uděláme jedinou logickou věc: vezmeme do ruky dvě kostky s N stěnami a hodíme je na stůl. Větší číslo budeme interpretovat jako jmenovatel, menší jako čitatel; padnou-li kostky stejně, pokus nepočítáme a zkusíme to znovu. Tak nikdy nedostaneme 0, ani 1, leč význam této chyby se bude s rostoucím N umenšovat k nerozpoznatelnu. To je přesně to, co budeme dělat: zvětšovat N nade všechny meze. Přitom budeme počítat pravděpodobnost, s jakou nám padnou nesoudělná čísla.

Pokud se tato bude blížit k nějakému pevnému nenulovému číslu, bude počet členů Fareyovy posloupnosti v Ω(N²). Proč? Neformálně: pravděpodobnost nějakého jevu je přeci počet přiznivých situací ku počtu všech situací. Pokud spočítáme tento poměr v závislosti na N a pokud ani pro neomezeně rostoucí N nedojde k nule, ale naopak k nějaké konstantě větší než nula, pak je určitě počet příznivých situací nezanedbatelný v porovnání s počtem všech a můžeme poměr schovat do Ω – je to přece konstanta jako každá jiná.

Hm, dejme tomu – jak tu pravděpodobnost spočítáme? No, jaká je šance, že nám na obou kostkách nepadlo číslo dělitelné dvěma? 3/4, samozřejmě, protože pravděpodobnost, že padlo, je 1/4. Číslo dělitelné třemi? 8/9. Pěti? 24/25. A tak dál. Jaká je tedy pravděpodobnost, že nejenom že nám nepadla čísla dělitelná dvěma (3/4), ale ani třemi (3/4 ·8/9), nadto ani pěti (3/4 ·8/9 ·24/25), …? (Bereme jenom prvočísla, protože čísla složená už jsme odfiltrovali s výskytem nejmenšího jejich prvočinitele.) Kolik je číslo vyjádřené následujícím produktem, nekonečným součinem?

Pozn.: P je množina všech prvočísel (P = {2, 3, 5, 7, 11, …})

Tohle vypadá obtížně, viďte? Musíme na to oklikou.

V roce 1644 se jistý italský matematik ptal po nekonečném součtu převrácených hodnot kvadrátů přirozených čísel, tedy po ∑_n∈N1/n². O sto let později se našel jiný matematik jménem Euler, který otázku zodpověděl: je to π²/6. Pí je, jak vidno, číslo užitečné nejenom při poměřování kružnic, důkaz tohoto tvrzení jde však nad rámec našeho textu.

Riemannova funkce zeta je pro dané s definována takto: ζ(s) = ∑_n∈N1/n^s, takže Eulerova odpověď spočítala hodnotu této funkce pro s=2. Euler ale přišel na ještě zajímavější věc: ∑_n∈N1/n^s=∏_p∈P1/1-p^-s. Platí tedy konkrétně pro s = 2 toto:

To na pravé straně je to, co jsme toužili spočítat, to na levé straně je suma, kterou nám spočetl hodný pan Euler. Kýžená pravděpodobost je proto 1/ζ(2)=6/π² = 0,6079… – nenulová! Délka posloupnosti je Ω(N²)!

Vaše algoritmy byly vesměs dosti správně, jen jste to nejspíš neuměli dokázat. Však jsme za to žádné body nestrhávali. V jednodušších případech je však zhodnocení kvality vymyšlených postupů důležité: už jenom proto, abyste zbytečně neztráceli na sebevědomí. Jeden z vás označil své řešení tohoto problému v čase O(N log N) za trapné :-) – kdyby si uměl odhadnout velikost výstupu, zjistil by, že nejen špatně spočítal složitost, ale že i dokázat něco spočítat v Ω(N²) může být výhra.

Implementace

Takže: rozhodli jsme se nagenerovat všechny zlomky tvaru i/j, kde j ∈{1,2,…,N} a i∈{1,2,j-1}. Je jich N(N-1)/2, takže O(N²). Nyní potřebujeme ověřit, které jsou v základním tvaru, a všechny setřídit.

Máme-li rozhodnout, zda můžeme krátit či nekrátit, naskočí nám většinou vzpomínka na pojem největšího společného dělitele. Ti informatičtěji vzdělaní z nás navíc vědí, že se k jeho hledání hodí Euklidův algoritmus: pokud však podlehnou pokušení užít ho při řešení této úlohy, padli do další léčky. My si totiž zlomky nejdříve uspořádáme, čímž se nám ty o stejné hodnotě (tj. nějaké takové, které zkrátit jdou, a onen jeden, který ne) dostanou k sobě a my je pak budeme moci eliminovat lokálně, prostým porovnáním při posledním průchodu seřazeným polem. Narozdíl od Euklida k tomu nebudeme potřebovat žádný další čas.

Tím se nám úloha redukuje na jediný problém: seřadit co nejrychleji vygenerované zlomky. Použijeme k tomu přihrádkové třídění: vytvoříme si N² přihrádek a každý zlomek tvaru a/b vložíme do přihrádky ⌊N²·a/b⌋. Bylo by pěkné, kdyby nám tak do jedné přihrádky nemohly spadnout dva zlomky o rozdílné hodnotě: a vskutku, nemůže se tak stát, protože rozdíl dvou zlomků se jmenovatelem menším nebo rovným N nemůže mít ve jmenovateli číslo větší než N², takže jakmile nám při zaplňování přihrádek jeden spadne do nějaké přihrádky i, dalšímu se to už nemůže stát – musí odskočit alespoň do (i+1).

Většina z vás použila obecný třídicí algoritmus se složitostí O(N log N). Nenechávejte se tolik ukolébat tím, že v obecném případě nic lepšího nejde! Máte-li pod rukou hromadu dosti speciálních zlomků, pravděpodobně to zvládnete i lineárně.

Sláva! Máme algoritmus mající časovou i prostorovou složitost O(N²), který generuje Ω(N²) hodnot, takže je nejspíš docela optimální …

I když! Potřebujeme tolik paměti? Řešení několika z vás si vystačila s paměťovou složitostí O(N), i když pak zpravidla vedla na čas v O(N² log N). V zásadě postupovali tak, že si nagenerovali nejmenšího kandidáta na dalšího člena posloupnosti od každé třídy zlomků se stejným jmenovatelem (tj. toho s jedničkou v čitateli), vhodili ho do řadící datové struktury (třeba haldy) a odebírali minimum. No a kdykoliv vyhodili prvek c/j, přihodili do struktury (haldy) další ve tvaru (c+1)/j.

Jaké si z toho vzít poučení do našeho přístupu, aniž bychom museli platit zhoršenou časovou složitostí? Rozdělíme si činnost našeho programu do N kroků, v i-tém z nich budeme zpracovávat zlomky větší než i/N a menší než (i+1)/N. Jak je najdeme? Budeme si v paměti držet pole, které nám pro každého jmenovatele řekne, s jakým čitatelem jsme ho naposled použili. Takže ho v i-tém kroku projdeme, zjistíme, jestli s o jednotku větším čitatelem spadá daný zlomek do našeho intervalu, pokud ano, vhodíme ho do přihrádkového třídění (které teď pracuje s podstatně menším univerzem, takže mu stačí malá paměť) a patřičně upravíme pole. No a pak už jenom z přihrádek vytiskneme setřízené zlomky.

Pěkné, ne? Otázkou je, jestli má cenu klást při návrhu algoritmů důraz na paměťovou složitost menší, než je velikost výstupu. Ale to samozřejmě má! Z teoretického hlediska je dobrá jakákoliv další optimalizace, která nás donutí přemýšlet, z praktického hlediska se nám už jen kvůli rozdílným rychlostem přístupu do různě velkých počítačových keší a pamětí hodí mít malou pracovní množinu.

Závěrem

Pokud vás úloha zaujala, vřele vám doporučuji otevřít si na Wikipedii heslo „Farey sequence“ a začíst se. Objevíte spoustu dalších hezkých vlastností Fareyových posloupností. Máte-li raději knihy než hesla, určitě neprohloupíte, přečtete-li si Conwayovu „The Book of Numbers“, kde se podává popularizační úvod do mnoha koutů všemožných číselných oborů.

Program

Lukáš Lánský

Jednodušší algoritmus

Existuje i jiný algoritmus, který je daleko jednodušší a jeho časová složitost je na první pohled optimální. Ale něco za něco – zase budeme muset trochu přemýšlet nad tím, proč opravdu vypíše to, co má.

Představme si, že máme dva zlomky a/b < c/d. Za jejich mediant prohlásíme zlomek (a+c)/(b+d) [to je takové „divné sčítání zlomků“]. Všimněte si, že mediant leží mezi a/b a c/d. To snadno ověříme: a/b < (a+c)/(b+d) je totéž jako a(b+d) < b(a+c), po roznásobení ab+ad < ab + bc, čili ad<bc. To ale není nic jiného než a/b<c/d. Podobně ukážeme (a+c)/(b+d) < c/d.

Nyní začneme vytvářet posloupnost zlomků takto: začneme s 0/1 a 1/1, pak mezi tyto dva zlomky vložíme jejich mediant 1/2, pak zase mezi každé dva zlomky vložíme jejich mediant a tak dále. Kdekoliv by jmenovatel překročil dané N, přestaneme na příslušném místě vkládat. Z toho získáme snadný rekurzivní algoritmus, zapíšeme si ho třeba v Pythonu následovně:

   def sb(a,b,c,d,N):
      (x,y) = (a+c,b+d)
      if y <= N:
         sb(a,b,x,y,N)
         print x,"/",y
         sb(x,y,c,d,N)
 
   def farey(N):
      print "0 / 1"
      sb(0,1,1,1,N)
      print "1 / 1"

Zavedli jsme rekurzivní funkci sb, která vypisuje zlomky z intervalu (a/b,c/d). Funguje jednoduše tak, že spočte mediant M=(a+c)/(b+d), rekurzivně se zavolá na interval (a/b,M), pak vypíše M a nakonec se zavolá na (M,c/d).

Tento algoritmus určitě vypisuje nějaké zlomky s čitateli a jmenovateli menšími nebo rovnými N, činí tak v ostře rostoucím pořadí (takže žádný nevypíše dvakrát) a vypsáním každého stráví jednotkový čas, a proto je jeho časová složitost lineární v počtu vypsaných zlomků. Jinak ale vzbuzuje spíš otázky:

Jsou vypsané zlomky v základním tvaru? Dokážeme, že kdykoliv se při vkládaní mediantů v naší posloupnosti vyskytnou za sebou čísla a/b a c/d, platí bc-ad=1. Z toho ihned vyplyne, že jak a/b, tak c/d jsou v základním tvaru – kdyby totiž existovalo nějaké k>1 dělící jak a, tak b, muselo by tímto k být dělitelné i bc-ad, a tedy i jednička, což nejde. Podobně pro c/d. A jak naši rovnost dokázat? Indukcí: na počátku platí (1·1 - 0·1 = 1), jakmile vložíme mediant x/y=(a+c)/(b+d), vzniknou nám dvě nové dvojice sousedních zlomků. Naše rovnost jistě platí pro dvojici (a/b,x/y): bx-ay = b(a+c)-a(b+d) =
= ab+bc-ab-ad = bc-ad = 1. Podobně pro dvojici (x/y,c/d): yc-xd = (b+d)c - (a+c)d = bc+cd-ad-cd =
= bc-ad = 1.

Nezapomeneme na nějaký zlomek? Co by se muselo stát, abychom nějaký zlomek x/y s x,y≤ N zapomněli vypsat? Nejdříve si všimněme, že to nemůže být způsobené tím, že jsme rekurzi zastavili příliš brzy – jakmile jednou jmenovatel nějakého zlomku překročí N, mají jmenovatele většího než N i všechny medianty s tímto zlomkem utvořené, takže zastavením rekurze přijdeme pouze o zlomky s příliš velkými jmenovateli. Mohli bychom tedy podmínku y≤ N nahradit omezením hloubky rekurze libovolným obrovským číslem a algoritmus by stále dělal totéž, jen by vypisoval navíc nějaké zlomky, které nás nezajímají.

Udělejme to a sledujme, do kterých intervalů, se kterými algoritmus pracuje, padne pohřešovaný zlomek x/y. V počátečním intervalu (0,1) evidentně je. Kdykoliv interval podrozdělíme na podintervaly (a/b,M) a (M,c/d), musí určitě padnout do právě jednoho z nich, jinak by totiž byl mediantem, a tudíž vypsán. Jakkoliv hluboko se tedy zanoříme do rekurze, vždy najdeme interval, který obsahuje x/y. Ukážeme, že to není možné.

Pokud x/y ∈(a/b,c/d), musí platit nerovnosti bx-ay>0 a cy-dx>0, ale protože čísla a,b,c,d,x,y jsou celá, tak také platí nerovnosti bx-ay≥ 1 a cy-dx≥ 1. Proto výraz Φ= (c+d)(bx-ay)+(a+b)(dy-cx) je větší nebo roven a+b+c+d. Pokud Φ roznásobíme a vytkneme (x+y), dostaneme Φ= (bc-ad)(x+y), jenže jak už víme z úvahy o základním tvaru, pro kterýkoliv interval, který potkáme, platí bc-ad=1. Proto Φ=x+y. Složením obou vztahů pro Φ získáme nerovnost a+b+c+d ≤ x+y. Na každé úrovni rekurze se ovšem alespoň jedno z čísel a,b,c,d zvýší alespoň o jedničku, takže nejpozději po x+y úrovních přestane x/y ležet v intervalu, což je spor.

Hotovo. Teď už tedy víme, že náš algoritmus vypíše každý zlomek právě jednou a učiní tak v lineárním čase s velikostí výstupu, což je, jak víme z výpočtů u předchozího řešení, Θ(N²). Paměti jsme spotřebovali nejvýše lineární množství na zásobník od rekurze.

Poznámka: Funkce sb vám může připomínat in-orderový průchod nějakým binárním vyhledávacím stromem. To není náhoda – zlomky opravdu můžeme popsat tzv. Sternovým-Brocotovým stromem, což je nekonečný strom zlomků, jehož každý vrchol je mediantem dvou vrcholů z předchozí hladiny. V takovém stromu se pak každé racionální číslo z intervalu (0,1) vyskytuje právě jednou a iracionální čísla odpovídají nekonečným cestám z kořene dolů.

Ještě jednodušší řešení

… tentokrát dokonce s konstatní paměťovou složitostí, ale důkaz správnosti si už v zájmu zachování lesů odpustíme (také je založený na podobných úvahách o mediantech, zkuste si ho vymyslet). Vypadá takto:

   def farey(N):
       a,b,c,d = 0,1,1,N
       print a, "/", b
       while c < N:
          k = int((b+N)/d)
          a, b, c, d = c, d, k*c-a, k*d-b
          print a, "/", b

Martin Mareš

22-1-3 Sazba (Zadání)

Škoda, že většina řešitelů se ještě z prázdninové hibernace neprobudila, neboť úloha nebyla příliš těžká. Nebo to bylo způsobeno složitým a místy kostrbatým zadáním? Někteří lidé se také chytili na malou zákeřnost v zadání – krása byla dobře definována i v momentě, když se na řádek vešlo několik slov bez mezer mezinimi. Příště už zlí nebudeme, slibujeme!

A nyní přistupme k řešení. Rozložení slov do bloku je velice pravidelné, díky tomu umíme v konstatním čase spočítat krásu jednoho řádku, máme-li načtené délky slov.

Pak už si stačilo jen rozmyslet, jak počítat minimální krásu (logicky správně spíše minimální ošklivost) pro K+1 slov, pokud už známe všechna minima pro K slov a méně. Postupně budeme zkoušet, kolik se nám s aktuálním slovem vejde předcházejících slov na ten samý řádek. Pro každý takový počet slov P spočítáme krásu řádku a tu sečteme s minimální krásou pro K-P+1 slov, kterou již známe. Najdeme-li minimum ze všech těchto součtů, získáme minimální krásu pro K+1 slov.

Program

Martin Böhm & Martin "Bobřík" Kruliš & CodEx

22-1-4 Bludiště (Zadání)

Pre začiatok si predstavíme bludisko ako graf G, kde voľné políčka reprezentujú orcholy grafu a hrana medzi dvoma políčkami existuje práve vtedy ak sú tieto políčka susedné. Na vyriešenie úlohy si vytvoríme druhý graf G₂. V ktorom vrcholy budú dvojice: (Pozícia hráča, pozícia objektu). Takýto graf má O(M²N²) vrcholov, pričom hrany z vrcholu vedú do vrcholov, do ktorých sa dá dostať po jednom presune hráča, týmto hranám dáme dĺžku 0. Alebo ak hráč stojí vedľa objektu, tak do pozície, keď hráč zatlačí na objekt (ak je to možné), týmto hranám dáme dĺžku 1. Vidíme, že z každého vrcholu vedie maximálne 5 hrán, takže počet hrán je úmerný počtu vrcholov, teda tiež O(M²N²).

Odpoveď sa potom rovná dĺžke najkratšej cesty z počiatočnej pozície hráča do ľubovolnej pozície, kde sa pozícia objektu rovná pozícii koncového miesta. Ak takáto cesta neexistuje, potom sa objekt na danú pozíciu nedá presunúť.

Na nájdenie najkratšej cesty môžeme použiť Dijkstrov algoritmus, čím dostaneme časovú zložitosť O(M²N² log(MN)) alebo len dokonca O(M²N²), prečítajte si vzorové riešenie úlohy 22-1-1 a skúste sa zamyslieť ako na to.

Za takéto riešenie ste mohli získať 7 bodov.

Veľa riešiteľov si všimla, že nám stačí uvažovať len vrcholy grafu G₂, keď je pozícia hráča susedná s pozíciou objektu. Takýchto dvojíc je 4MN. A označme podgraf grafu G₂ tvorený týmito vrcholmi G₃. Teda pozícia objektu a hráč môže stáť z jednej zo štyroch strán objektu. Na začiatku však hráč nemusí byť na pozícii susednej s objektom. To vyriešime tým, že na začiatku spustíme prehľadávanie (do šírky alebo hĺbky) na grafe G a zistíme, kam sa môže dostať hráč z počiatočnej pozície, pričom nás bude zaujímať, na ktoré susedné pozície s objektom sa dá dostať. Tieto dvojice budú naše počiatočné pozície v grafe G₃.

K rýchlemu riešeniu však musíme vyriešiť nasledujúci problém: Potrebujeme zistiť pre vrcholy G₃, ktoré sa líšia len na pozíciou hráča (teda strana objektu na ktorej hráč stojí) či medzi pozíciami hráča existuje nejaká cesta v grafe G, ktorá neobsahuje políčko na ktorom práve stojí objekt.

Môžeme zase potrebnú cestu nájsť prehľadávaním, avšak tým by sme zase dostali riešenie fungujúce v čase O(M²N²).

Správnym riešením sú vrcholovo dvoj-súvislé komponenty grafu G.

O dvojsúvislých komponentách a algoritme, ako ich nájsť si môžete prečítať v kuchárke KSP. Krátke zhrnutie: Vrcholovo-dvojsúvislým komponentom grafu G nazveme takú množinu hrán, že pre každú dvojicu vrcholov, ktoré sú incidentné s týmito hranami, existujú dve vrcholovo-disjunktné cesty. O vrchole v povieme, že patrí do nejakého dvoj-súvislého komponentu, ak aspoň jedna hrana má jeden koniec vo v. Všimnime si, že jeden vrchol môže patriť do viacerých vrcholovo-dvojsúvislých komponentov.

Pre nás je podstatné, že vrcholovo-dvojsúvislé komponenty vieme nájsť v lineárnom čase od veľkosti grafu.

Teda na začiatku nájdeme vrcholovo dvojsúvislé komponenty grafu G a pre každú hranu grafu G si uložíme číslo dvoj-súvislej komponenty do ktorej patrí. Následne pre vrcholy grafu G₃, ktoré sa líšia len pozíciou hráča, zistíme existenciu cesty medzi pozíciami hráča v G, ktorá neobsahuje pozíciu objektu na základe toho, či hrana spájajúce pozíciu objektu a pozíciu hráča v jednom vrchole je v rovnakej dvoj-súvislej komponente ako hrana spájajúca pozíciu objektu a pozíciu hráča v druhom vrchole. Ak takáto cesta existuje, potom medzi tieto vrcholy pridáme hranu dĺžky 0.

A opäť platí, že odpoveďou na náš problém je dĺžka najkratšej cesty z nejakej počiatočnej pozície do ľubovolnej pozície, kde sa pozícia objektu rovná pozícii koncového miesta.

Celková časová zložitosť sa skladá z počiatočného prehľadania grafu G, aby sme zistili, na ktoré susedné pozície objetku sa dá dostať, to stihneme v čase O(MN). Následne nájdeme dvoj-súvislé komponenty grafu G v čase O(MN) a nakoniec nájdeme najkratšiu cestu v grafe G₃, v ktorom je počet vrcholov 4MN, hrán tiež O(MN), pričom hrany majú dĺžky len 1 alebo 0 v čase O(MN). Celková časová a pamäťová zložitosť je teda O(MN).

Program

Peter Ondrúška

22-1-5 Šachovnice na pneumatice (Zadání)

Se ženami to není nikdy lehké, obzvlášť je-li jich n na pneumatice a navzájem se ohrožují. Ukážeme si však, že pro informatika s příslušným aparátem žádný problém nepředstavují.

Políčka šachovnice značme (x,y) pro x,y∈{0..n-1}, pozice jednotlivých dam budou (x_i,y_i). Chceme-li dámy rozestavět bezpečně, musí mít každá z nich vlastní jednu horizontální, jednu vertikální a dvě diagonální přímky. K popisu diagonál (a lecčehos jiného) se nám bude hodit termín kongruence – řekneme, že a ≡ b  mod n (tedy a je kongruentní s b modulo n), pokud čísla a a b dávají po dělení n stejný zbytek – tím elegantně popíšeme, že šachovnice má slepené konce. Hlavní diagonála h_i má pak na pneumatice rovnici (x+y) ≡ i  mod n (obsahuje tedy body (i,0),(i-1,1),...), vedlejší diagonála v_i má rovnici (x-y) ≡ i  mod n (tedy (i,0),(i+1,1),...).

Zkusme na to jít jednoduše, budeme dávat dámy postupně na řádky (y-souřadnice) s odskokem ve sloupečku o dva vůči předchozí (tak jako to bylo v ukázkovém příkladě pro
n=5); což lze popsat dvojicí rovnic y_i ≡ i mod n,
x_i ≡ 2y_i mod n. Pro jaká n toto bude fungovat? Každá dáma má určitě vlastní y-souřadnici, a pokud je n liché, tak funkce 2y_i nejdříve skáče po sudých číslech (počínaje nulou), pak nabyde hodnoty n+1 ≡ 1  mod n a skáče po lichých hodnotách. Dáma i tedy dostane jinou x-souřadnici než všechny předchozí. Hlavní diagonála příslušející dámě i má rovnici (x_i + y_i)≡ (3y_i) mod n – obdobně si všimneme, že není-li n dělitelné třemi, tak se nejdříve skáče po diagonálách čísla 3k, pak se n přeskočí o 1 nebo o 2, a tedy se skáče po 3k+1 nebo 3k+2, a nakonec se n přeskočí o 2 nebo o 1 (podle toho co bylo v minulém kroku) a skáče se po 3k+2 nebo 3k+1 – a tedy opět má každá dáma unikátní hlavní diagonálu. Vedlejší diagonála bude mít situaci nejsnazší, její rovnice je totiž -y_i  mod n, a tedy se skáče o jedničku po všech číslech. Tahle konstrukce tím pádem povolí všechna n, co nejsou dělitelná 2 a 3.

Zkusme na to jít obecněji a stavět následujícím předpisem: y_i = i, x_i ≡ ky_i mod n, kde k bude námi zvolený parametr (tedy dámy necháme odskakovat o k). Teď nám poslouží argument z teorie čísel, konkrétně Eukleidův rozšířený algoritmus. Ten umožňuje pro čísla n,k a libovolné c∈N najít takové koeficienty a a b∈Z, že a·n + b·k = c·nsd(n,k) (nsd je největší společný dělitel). Pokud celou rovnici vymodulíme n, dostaneme b·k ≡ c·nsd(n,k) mod n. Je-li nsd(n,k) = 1, pak umíme pro každé číslo c najít takové b, aby rovnice platila – jinak řečeno, zvolíme-li hodnoty y_i·k ≡ x_i mod n, umíme ke každé přímce x najít její dámu (a má-li každá přímka svou dámu, tak má každá dáma svou přímku – dam a přímek je totiž stejně). Pokud nsd(n,k)≠ 1, pak k některým přímkám dámu nenajdeme (platí totiž, že nsd(n,k) | k ⇒nsd(n,k) | y_ik, a tedy nic jiného než x_i ≡ c·nsd(n,k) nedostaneme).

Stejný argument lze použít i pro hlavní a vedlejší diagonálu – je-li dáma na pozicích (y_ik mod n,y_i), pak sedí na diagonálách s rovnicemi (x_i+y_i) ≡ (y_ik + y_i) ≡ y_i(k+1) mod n, popř. (x_i-y_i) ≡ y_i(k-1) mod n; a tedy musí být nsd(k-1,n) = nsd(k+1,n) = 1.

Nastanou-li tyto tři podmínky, pak každá dáma si ohrožuje jen své vlastní přímky, a rozestavění na šachovnici je tedy korektní. Zbývá se ptát, pro jaká n tohoto lze dosáhnout. Všimneme si, že mezi čísly k-1,k,k+1 je vždy alespoň jedno dělitelné třemi a alespoň jedno dělitelné dvěma – tedy pro žádné k nezvládneme řešit více šachovnic, než pro první popsaný postup s k=2. Na druhou stranu to ale ukazuje poměrně zajímavý fakt, že šachovnice provčíselných rozměrů dávají pro tento předpis „nejvíce volnosti“, k lze volit nejvíce způsoby (takovýchto srandovních vlastností mají prvočísla mnoho). Když už jsme u toho, ani rozestavění předpisem x_i ≡ ky_i určitě není jediné možné, například pro N=19 existuje celkem 820 496 rozestavění neohrožených dam (za tuto cennou informaci děkujeme Vojtovi Hlávkovi).

Předpokládali jsme ale konkrétní předpis pro pozice dam (x_i ≡ ky_i  mod n), nešly by třeba pro zlá n rozestavit dámy jinak? Marná snaha, pro sudá n dokážeme neexistenci řešení následujícím způsobem: ∑(y_i + x_i)≡ ∑i (každá dáma má svou hlavní diagonálu h_i) ≡ n·(n-1)/2 mod n (součet čísel 0..n-1); na druhou stranu ∑y_i + ∑x_i ≡
≡ n·(n-1)/2 + n·(n-1)/2  mod n (každá dáma má svou vlastní horizontální i vertikální přímku) – tedy n·(n-1)/2 ≡
≡ 0 mod n.

Pro 3 | n je situace podobná, uvážíme ale rovnice

opět díky neohroženosti dam navštíví obě sumy kvadráty všech čísel 0..n-1, a tedy

zároveň ale roznásobením druhých mocnin získáme

podobně

a tedy

z čehož již dostaneme pomocí vzorce pro sumu třetích mocnin n(2n+1)(n+1)/3 ≡ 0  mod n, a tedy nutně 3 nedělí n (obdobná argumentace, je-li n=3k, tak nám 2n+1 ani n+1 výsledek neovlivní, protože neobsahují v rozkladu trojku – která tím pádem bude vlevo chybět; na druhou stranu pro n=3k + {1,2} se trojka ztratí v některém z {2n+1,n+1} a vítězíme). Pokud tedy šachovnici nevyřešíme pomocí y_i = i, x_i ≡ 2y_i  mod n, tak už nijak.

vyčarovali pro Vás Martin Mareš & Vojta Tůma
na motivy dávného papyru George Pólyi

22-1-6 Náhradní (Zadání)

Hledáme nejkratší úsek textu, který obsahuje všechna slova ze zadaného slovníku. Slovo chápeme jako libovolnou posloupnost znaků, mezery nehrají žádnou zvláštní roli. Navíc, protože to zadání nezakazuje, budeme předpokládat, že se jednotlivé výskyty slov mohou překrývat. Algoritmus, který vyhledá slova v textu tak, jak potřebujeme, vymyslíme později, zatím budeme předpokládat, že nějaký takový máme.

Uvědomíme si, jak hledaná posloupnost znaků vypadá. Je jasné, že na jejím prvním znaku začíná nějaké z hledaných slov a na posledním nějaké končí. Kdyby to tak nebylo, mohli bychom ji zkrátit tak, že by pořád obsahovala všechna hledaná slova. To by ale znamenalo, že nalezená posloupnost nebyla nejkratší.

Když tedy pro každou pozici v prohledávaném textu, na které končí nějaké hledané slovo, najdeme nejkratší posloupnost, která tam končí a která obsahuje všechna hledaná slova, bude mezi nimi určitě i ta nejkratší, kterou chceme najít. Nejkratší vyhovující posloupnost s daným koncem najdeme tak, že se v textu podíváme na předchozí výskyty všech hledaných slov. Pokud jsme nějaké slovo v textu ještě nenašli, nemůže na dané pozici končit hledaná posloupnost. V opačném případě tady nějaká vyhovující posloupnost končí. Ze všech takových chceme vybrat tu nejkratší, což uděláme tak, že si pro každé hledané slovo určíme jeho poslední (ten, který je nejvíc vpravo) výskyt a z nich vybereme ten, který je nejvíc vlevo. Takto zjistíme délku nejkratší vyhovující posloupnosti s daným koncem. Průběžně si budeme pamatovat nejkratší zatím nalezenou posloupnost, takže na konci algoritmu budeme znát tu úplně nejkratší, kterou hledáme.

Stačí nám tedy pamatovat si poslední výskyt každého hledaného slova. Protože potřebujeme často zjišťovat pozici nejlevějšího z těchto výskytů, hodilo by se nám udržovat je setříděné podle jejich začátků. My ale procházíme výskyty podle jejich konců, a museli bychom tak každý výskyt znova zatřiďovat. Opakované zatřiďování je nutné proto, že začátky a konce výskytů hledaných slov mohou být v jiném pořadí. Uvědomíme si ale, že taková situace nastane jedině tehdy, pokud je jedno hledané slovo podřetězcem druhého, například máme ve slovníku zároveň slova klíč a paklíček. Jenže když nějaká posloupnost obsahuje delší slovo z takové dvojice, obsahuje určitě také kratší z nich, a tedy toto kratší slovo můžeme ze slovníku odstranit a stejně získáme stejný výsledek. (Jak přesně najít slova, která jsou podřetězcem jiného, si ukážeme za chvíli.) To ale znamená, že výskyty mají stejné pořadí, ať už je třídíme podle jejich začátků nebo konců, a můžeme tedy použít spojový seznam. Ten bude setříděný podle pozice posledního výskytu pro každé slovo a vždy, když narazíme na výskyt nějakého slova, přesuneme jemu odpovídající záznam na konec seznamu, což zvládneme v konstantním čase.

Konečně se dostáváme k samotnému vyhledávání slov. Tímto tématem se zabývá kuchařka 5. série 18. ročníku. My z ní použijeme algoritmus Aho-Corasick, který upravíme tak, jak je uvedeno výše, to znamená, že nebude vyhledávat slova, která jsou podřetězcem nějakého jiného slova ve slovníku.

Základní myšlenkou tohoto algoritmu je to, že vždy, když máme načtený nějaký kus textu, tak si budeme pamatovat jeho nejdelší konec, který je také začátkem nějakého z hledaných slov. Protože takovýchto začátků není moc, předem si pro každý z nich spočítáme, kam půjdeme dál, když na vstupu dostaneme nějaký znak. Vytvoříme si orientovaný graf (říká se mu trie), ve kterém vrcholy odpovídají všem počátečním podřetězcům hledaných slov, včetně prázdného. Navíc si budeme pamatovat, které podřetězce odpovídají hledaným slovům. Pokud mají dvě slova stejný nějaký začáteční podřetězec, bude těmto podřetězcům odpovídat stejný vrchol. Z vrcholu, kterému odpovídá nějaký řetězec, pak povedou hrany do všech vrcholů, kterým odpovídají řetězce o jedna delší a pro které je tento řetězec jejich začátkem.

Trii postavíme tak, že pro každé slovo začneme ve vrcholu, který odpovídá prázdnému řetězci. Dál postupně čteme znaky slova. Pokud aktuální vrchol už má hranu pro tento znak, tak po ní projdeme, jinak ji nasměrujeme na nově vytvořený vrchol a stejnětak po ní přejdeme. V obou případech pokračujeme dalším znakem. Nakonec si ještě u posledního vrcholu poznačíme, že tady končí toto slovo.

Po vytvořených hranách můžeme postupovat dopředu (budeme jim proto říkat dopředné), pokud to jde, ale my se musíme nějak vypořádat i se situací, že to nejde. To uděláme tak, že si u každého vrcholu budeme navíc pamatovat ještě tak zvanou zpětnou hranu. Ta povede do vrcholu, jehož řetězec je nejdelším možným koncem řetězce v tomto vrcholu. Při vyhledávání pak vždy zkusíme jít dopředu po odpovídající dopředné hraně a pokud to nejde, tak použijeme zpětnou hranu a celý postup opakujeme.

Jak ale zpětné hrany určíme? Budeme postupovat od nejkratších řetězců. Prázdný řetězec je speciální případ, u něho budou existovat dopředné hrany pro každý znak. Pokud neexistuje vrchol, kam by nějaká taková hrana mohla vést, tak povede zpět do tohoto vrcholu. Z vrcholů pro řetězce délky jedna musí vést zpětné hrany do vrcholu pro prázdný řetězec. Dále budeme u každého řetězce počítat s tím, že zpětné hrany už známe u všech kratších řetězců. Pak cíl zpětné hrany pro tento vrchol určíme stejně, jako bychom hledali následující stav pro poslední znak řetězce tohoto vrcholu, kdybychom postupovali z jeho rodiče (tj. jediného vrcholu, ze kterého sem vede dopředná hrana) a pokud bychom nemohli jít do tohoto vrcholu. Použijeme při tom určitě zpětnou hranu rodiče a možná i nějakých dalších vrcholů, ale o těch vím, že už existují.

Teď se ještě potřebujeme zbavit slov, která jsou podřetězcem nějakého z hledaných slov. To provedeme ve dvou fázích. Jednak už při stavění trie se může stát, že vytváříme syna vrcholu, ve kterém už nějaké slovo končí. Takové slovo pak ale musí být podřetězcem právě přidávaného, takže si u tohoto vrcholu poznačíme, že tam žádné slovo nekončí a tím se nám podařilo na něj zapomenout, jak jsme chtěli. Druhou fázi budeme provádět při budování zpětných hran. Pokud vytvoříme zpětnou hranu do vrcholu, ve kterém končí nějaké slovo, opět platí, že musí být podřetězcem nějakého slova, které prochází tímto vrcholem, a tak jej musíme zapomenout. Tím jsme docílili odstranění všech slov, u kterých jsme to požadovali.

Upravený algoritmus Aho-Corasick má časovou složitost O(S + T), kde S je součet délek hledaných slov a T je délka prohledávaného textu. Musíme sice zpracovat každý výskyt hledaného slova (kromě odstraněných), ale těch je nejvýše tolik, kolik je znaků v prohledávaném textu (pokud by na nějakém znaku končily dvě slova, tak musí jedno být podřetězcem druhého a taková slova jsme z vyhledávání odstraňovali). Paměťová složitost je O(S).

Celková časová složitost bude O(S + T), protože každý výskyt hledaného slova zvládneme zpracovat v konstantním čase. Paměťová složitost je O(N + S), kde N je počet hledaných slov.

Program

Petr Onderka

22-1-7 Když telefony pekly jazyk (Zadání)

Každý druhý

Princip je jednoduchý. Budeme ze vstupního seznamu ukusovat od začátku po dvou prvcích. Z každého takového bloku (no, bločku) dáme do výstupu jen ten druhý a rekurzivně necháme zpracovat zbytek.

Ve chvíli, kdy již nebude k dispozici celý dvoubloček, tedy zbývá maximálně jeden prvek, není již co dávat na výstup, tedy skončíme.

Fibonacciho čísla

První verze (fibslow) je jen přepsáním definice ze zadání. V případě malých čísel přímo vrací výsledek, u větších spočítá dvě menší čísla a vrátí součet. Bohužel, toto je pomalé – má to složitost O(2ⁿ) – viz například kuchařku 21. ročníku 5. série.

Inspirujeme se tedy kuchařkou a vyřešíme to tak, že budeme počítat postupně fibonacciho čísla od nejmenších postupně až k požadovanému. Nové se jednoduše spočítá sečtením dvou posledních, která si průběžně pamatujeme. Tímto snížíme časovou složitost na O(n).

Myšlenka zřejmá, jak ale takovou věc napíšeme, když není k dispozici žádný cyklus? Inu, všemocná rekurze nás zachrání. V každém kroku spočítáme jedno další číslo a rekurzí necháme spočítat ten zbytek. Až budeme na správném čísle, rekurzi zastavíme a vrátíme výsledek.

Nakonec jen zbývá rekurzivní funkci s velkým počtem parametrů obalit do něčeho, co má jen potřebný jeden, a je hotovo. Tato lineární verze se ve vzorovém řešení nazývá fiblin. Rychlostní rozdíl je možné vyzkoušet – již např. u 40 je rozdíl vidět pouhým okem velmi zřetelně.

Poznámka: Existuje ještě vzoreček na spočítání n-tého Fibonacciho čísla, mohli bychom ho použít a zvládnout to v logaritmickém čase (mocní se v něm). Obdobný trik používá mocnění matic. Za takové řešení byl malý bodový bonus.

Prvočísla

Na hledání prvočísel existují dva jednoduché algoritmy – Eratosthenovo síto a zkoušet dělit všemi prvočísly do odmocniny. My použijeme druhý, protože nevíme, jak velké bychom potřebovali síto.

Funkce prvo (verze s 3 parametry) plní funkci vnějšího cyklu – dokud nemá dostatek prvočísel, tak postupně zkouší jednotlivá čísla a když nejsou ničím dělitelná, tak je přidává na konec seznamu (aby zůstal setříděný vzestupně – což je výhodné, neboť mnoho čísel je dělitelných malými čísly a můžeme si dovolit optimalizaci s odmocninou).

Každé číslo testuje funkcí delitelne – ta zkouší, jestli zbytek po dělení jednotlivými prvočísly je nula. Skončí ve chvíli, kdy již nejsou žádná prvočísla, aktuální prvočíslo je větší než odmocnina a nebo jsme našli nějakého dělitele.

Všimněte si, že ve funkci prvo je použitá podmínka za pomocí case a ne when jako v ostatních případech. To proto, že when a if nedovolují volat funkce (kvůli optimalizacím). Ti, kteří si kód vyzkoušeli, na takovou věc jistě přišli.

Poznámka: Při programování nějakých reálných úloh se samozřejmě používají různé knihovny. Například v této úloze bychom si mohli ušetřit práci a nepsat funkci pridej, neboť taková se vyskytuje v modulu lists a jmenuje se append.

Kód funkcí