První série sedmnáctého ročníku KSP

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

Řešení úloh

• 17-1-1: Výdělek bratří Součků
• 17-1-2: Bůhdhova odměna
• 17-1-3: Chmatákův lup
• 17-1-4: Paloučkova výhra
• 17-1-5: Jazykozpytcův poklad

17-1-1 Výdělek bratří Součků (Zadání)

Řešení této úlohy by se dala rozdělit do tří skupin. Lineární, kvadratické (vůči délce vstupu) a nefunkční. Kromě toho několik lidí předpokládalo, že řetězce mohou být vůči sobě posunuté. Nechápu proč. Bratři byli vyslání na koncert společně a začali zapisovat oba hned na začátku.

No a jak mělo řešení vypadat? Nejprve je třeba si uvědomit, že pokud mají být řetězce záznamem toho samého, pak musí obsahovat stejný podřetězec, jehož opakováním vytvoříme Ainův i Kábelův záznam. No a jak dlouhý tento podřetězec může být? Jelikož jeho několikanásobným zopakováním musíme dostat jak Ainův, tak Kábelův záznam, musí jeho délka být největší společný dělitel délek záznamů Aina a Kábela, resp. NSD musí být jeho celočíselným násobkem.

Pokud bude tedy Ainův i Kábelův záznam složen z opakujícího se podřetězce délky NSD a tyto podřetězce budou u Aina i Kábela stejné, víme, že zápisy budou stejné. A pokud podmínka splněná nebude, zaznamenali oba něco jiného.

Algoritmus řešící úlohu je jenom přímočarou implementací popsaného postupu, jeho časová i paměťová složitost je lineární vůči délce zápisů obou bratří.

Toto mělo být řešení této úlohy, ale při pročítání řešení účastníků jsem nalezl jedno výrazně elegantnější:

var Ain,Kabel:string;
begin
    write('Ain:');readln(Ain);
    write('Kabel:');readln(Kabel);
    if (Ain+Kabel = Kabel+Ain) then
      writeln('Záznamy jsou stejné.')
   else
      writeln('Záznamy jsou ruzné.');
end.

A proč toto funguje? BÚNO (bez újmy na obecnosti) předpokládejme, že Kábelův záznam (označme jej K a jeho délku L_K) je delší než Ainův (A, L_A). Záznamy budeme indexovat od nuly. Zřejmě ono porovnání vypadá takto:

Z porovnání těchto řádků dostaneme jednoduše:

Zkombinováním (1) a (3):

A po uvažování (2):

Iterováním této rovnosti pro libovolné celé c:

Z toho je již vidět (po chvilce zamyšlení), že:

a tedy rovnost je splněna, právě když jsou záznamy stejné.

Program

Pavel Čížek

17-1-2 Bůhdhova odměna (Zadání)

V této úloze nám nejde o nic jiného než o tak řečené barvení grafu, čili o přiřazení nějakých čísel (barev) 1, …, k vrcholům grafu tak, aby žádné dva vrcholy spojené hranou nedostaly stejnou barvu. Zjistit, jestli je graf nějakými k barvami obarvitelný, je obecně velice těžký problém (pro obecné grafy a k>2 ho nikdo neumí vyřešit v polynomiálním čase; případy k=1 a k=2 si rozmyslete sami, ty jsou pro změnu triviální). Ale my o našem grafu naštěstí víme, že je rovinný (viz povídání v tomto vydání naši kuchařky), což situaci značně mění.

Každý rovinný graf lze obarvit čtyřmi barvami (to ale vůbec není triviální dokázat, matematikové se s tím trápili více než 100 let a nejkratší známý důkaz má přes sto stránek a rozebírá 633 různých případů). My si dokážeme, že vždy stačí 6 barev a že Bůhdha má tedy vždy šanci svou odměnu rozdělit:

Věta: (o šesti barvách) Každý rovinný graf je možno obarvit šesti barvami.

Důkaz: Indukcí podle počtu vrcholů. Pokud má graf nejvýše 6 vrcholů, obarvit ho dozajista můžeme. Pokud je graf větší, věta dokázaná v kuchařce nám říká, že v něm vždy existuje nějaký vrchol v stupně maximálně 5. Když takový vrchol odstraníme, dostaneme menší graf a ten je již podle indukčního předpokladu obarvitelný. Následně do obarveného grafu vrchol v vrátíme, a jelikož má nejvýše 5 sousedů, vždy je pro v alespoň jedna barva volná.

Již tento důkaz nám dává jednoduchý algoritmus pro Bůhdhův problém, ale ještě si musíme rozmyslet, jak neztrácet příliš mnoho času hledáním vrcholů nízkého stupně. Předem si spočítáme stupně všech vrcholů a do fronty uložíme ty vrcholy, které měly už na počátku stupeň ≤ 5. Poté postupně čteme vrcholy z fronty, snižujeme stupně jejich sousedům a jakmile některému sousedovi klesne stupeň pod 6, přidáme jej na konec fronty. Tím jsme vlastně sestrojili takové uspořádání vrcholů, že z každého vrcholu vede „doprava“ nejvýše 5 hran. Stačí tedy frontu projít pozpátku a postupně přidělovat volné barvy.

Tento algoritmus má lineární časovou i prostorovou složitost O(N) (všimněte si, že jelikož je graf rovinný, má O(N) hran). V programu stojí za zmínku snad jedině způsob reprezentace grafu: hrany máme uloženy v poli (každou dvakrát – v obou směrech), každý vrchol si pamatuje číslo první hrany z něj vycházející a každá hrana číslo následující hrany vycházející z téhož vrcholu. Při odtrhávání vrcholů hrany neodstraňujeme, pouze snižujeme stupně.

[P.S.: Po chvíli přemýšlení můžete náš důkaz upravit tak, aby ukazoval, že stačí 5 barev. Bůhdha se ale spokojí s šesti, takže mu nebudeme komplikovat život.]

Na závěr ještě ukážeme několik variant hladového barvícího algoritmu, který se často objevoval ve vašich řešeních a bohužel pro rovinné grafy nemůže fungovat.

Hladové barvení funguje takto: probíráme vrcholy jeden po druhém a každému přidělíme nejnižší barvu, která není použitá již obarvenými sousedy tohoto vrcholu. Zkusme si rozmyslet, jak obarví následující grafy:

Zde B₁ je graf z jednoho vrcholu a B_k+1 zkonstruujeme tak, že vezmeme B₁, …, B_k a přidáme nový koncový vrchol v_k spojený s koncovými vrcholy všech B_i hranou. Vrcholy nového grafu uspořádáme tak, že nejdříve půjdou vrcholy grafů B₁, pak B₂, …, B_k a na konec umístíme nově vytvořený vrchol.

Všimneme si, že zadáme-li hladovému barvícímu algoritmu graf B_k, spotřebuje k barev a vrchol v_k obarví barvou k. I tentokrát nám k důkazu pomůže indukce: B₁ obarvíme jednou barvou, B₂ dvěma; pokud spustíme algoritmus na graf B_k, nejdříve obarví B₁ až B_k-1, a jelikož jsou v tom správném pořadí a nevedou mezi nimi žádné hrany, dopadne to stejně, jako bychom barvili každý zvlášť, čili podle indukčního předpokladu budou jejich koncové vrcholy obarveny barvami 1 až k-1, proto na zbývající vrchol v_k zbude barva k.

Jenže B_k je určitě rovinný graf, takže se dá obarvit šesti barvami (on je to dokonce strom, a tak stačí barvy dvě). Proto na něm pro k>6 nemůže hladový barvící algoritmus fungovat.

Hladové barvení se ještě můžeme pokusit zachránit tím, že si zvolíme nějaké šikovné pořadí vrcholů (konec konců i náš správný barvící algoritmus je vlastně toho druhu). Ale jen tak ledajaké pořadí neposlouží:

• Pořadí podle rostoucích stupňů: v našem grafu pouze zparalelizuje barvení podgrafů B₁, …, B_k – jenže mezi nimi nevedou žádné hrany, takže výsledek musí vyjít stejný.
• Podle klesajících stupňů: stačí k vrcholům přivěsit spoustu listů (vrcholů stupně 1) a tím algoritmus donutit k takovému pořadí, jaké chceme (možná bude potřebovat ještě jednu barvu na listy, ale tím hůř pro něj).
• Podle prohledávání do šířky: přidáme každému B_i ještě počáteční vrchol w_i a při vytváření B_k+1 připojíme nový počáteční vrchol w_k+1 k počátečním vrcholům w₁, …, w_k cestami délek zvolených tak, aby koncové vrcholy všech B_i byly ve stejné vzdálenosti od w_k+1. Tehdy bude nový koncový vrchol v_k+1 obarven až po všech ostatních vrcholech, čehož jsme přesně potřebovali dosáhnout. Graf přitom zůstane rovinný.
• Podle prohledávání do hloubky: tentokrát budeme přidávat hrany z v_i do w_i+1 a zařadíme je tak, aby je prohledávací algoritmus objevil vždy před hranou do v_k+1. Takové cesty donutí prohledávání zpracovat nejdřív B₁ až B_k a teprve pak barvit vrchol v_k+1. Přitom vrchol w_i má blokovánu pouze barvu i-1, takže ho určitě obarvíme jedničkou. Protipříklad opět zachráněn, graf opět zůstane rovinný. (Jediný problém je s hranou v₁w₂, na tu musíme přidat ještě jeden vrchol, jinak bude w₂ obarven barvou 2, což nechceme.)

Program

Martin Mareš

17-1-3 Chmatákův lup (Zadání)

Při řešení tohoto příkladu se mnoho z Vás inspirovalo příkladem v kuchařce. Avšak asi jenom polovina řešení byla správně. Hlavním problémem nefunkčních řešení bylo zejména nesprávné ošetření vícenásobného započtení jednoho předmětu.

Klíčové pozorování, které vede k pěknému řešení: Máme-li maximální dosažitelné ceny lupu pro všechny celočíselné kapacity batohu pomocí prvních k předmětů, snadno spočtěme maximální ceny pro prvních k+1 předmětů. A to tak, že zkusíme přidat k+1-ní předmět do batohu s k předměty a kapacitou nižší o hmotnost tohoto předmětu. Předmět nepřidáme, pokud cena takového lupu není vyšší od ceny lupu z prvních k předmětů v batohu se stejnou kapacitou. První předmět je možné vložit do batohu s kapacitou rovnou alespoň hmotnosti předmětu a cena lupu je maximální možná. Pro další předměty to plyne z indukce.

Budeme postupně zaplňovat tabulku podle popisu v pozorování. Z této tabulky snadno zrekonstruujeme vložené předměty. Stačí si uvědomit, že předmět i byl použit, pokud vylepšil cenu lupu v batohu se stejnou nosností bez tohoto předmětu.

Časová i paměťová složitost je O(P·N).

Program

Miroslav 'miEro' Rudišín

17-1-4 Paloučkova výhra (Zadání)

V této úloze jde o nalezení nejkratší kružnice v ohodnoceném grafu. Celkem často se vyskytovalo jedno popsaných řešení, ale našla se i originální řešení v O(N⁴), O(N⁵).

Jednodušší řešení je dynamické, upravím vlastně Floyd-Warshalla tak, že postupně rozšiřuji množinu S už prozkoumaných vrcholů. Na začátku do ní vložím libovolné 2 vrcholy a do matice vzdáleností D si uložím délky hran nebo příp. nekonečna (jako v kuchařce). Potom vždy vezmu vrchol k, který ještě není v S, a pro všechny jeho sousedy i,j, kteří už jsou v S (jsou-li takoví), prozkoumám cestu i...j. Pokud ji totiž už znám, určitě nevede přes k a k-i...j-k je tedy kružnice. Ze všech takto postupně nacházených kružnic si vyberu nejmenší a tu si zapíšu (pamatuji si vždy jen tu nejlepší) – to udělám tak, že si (stejně jako v kuchařce) pamatuji město s největším číslem na každé cestě E[i,j], updatuji ho při změně cesty, vypisuji rekurzí. Nemůžu nejmenší kružnici nijak přeskočit, protože jakmile právě přidávám do S její poslední vrchol, potom i a j se jednou trefí do jejich hran a pokud by její součástí měla být delší cesta než mnou nalezená i...j, nebyl by výsledek nejmenší kružnice. Už zbývá jen projet všechna i,j∈S a zjistit, zda nejsou i...k...j nebo i...j-k kratší než původní i...j nebo i...k a případně je vylepšit. Časová složitost jednodušší verze je O(N³), paměťová složitost O(N²).

Další možnost řešení byla vybrat postupně každý vrchol jako start a spustit z něj Dijkstrův algoritmus (kterým najdu nejkratší cesty do všech ostatních vrcholů) a potom pro každou hranu nevedoucí z/do startu prozkoumat nejkratší cesty vedoucí z jejich konců na start. Pokud ani jedna z těchto cest není podmnožinou té druhé (na to se stačí podívat na jejich první hrany, jestli některá není ta prozkoumávaná), určitě tvoří buď kružnici nebo pseudokružnici (s „ocáskem“). Tak jako tak si z těchto všech mohu zapamatovat nejkratší (pseudo)kružnici, protože platí, že stejně musím (pro nějaký jiný start) objevit i kružnici bez toho ocásku, a ta bude určitě kratší. Časová složitost je zde (podle implementace Dijkstrova algoritmu) O(N³) při nejjednodušší implementaci, O(MN log N) při použití haldy a O(MN+N² log N) při použití Fibonnacciho haldy. Rozdíl těchto časových složitostí není sice velký (ty jsou v nejhorším vždy O(N³) až O(N³ log N)), ale některé z těchto implementací jsou mnohem lepší pro řídké grafy. Paměťová složitost je O(N²).

Program

Tomáš Gavenčiak

17-1-5 Jazykozpytcův poklad (Zadání)

Obě zadané úlohy patřily spíše k těm snazším a řešitelé, kteří úlohy odeslali, byli převážně dvou druhů. První, malá skupina těch, kteří si nejspíše pořádně nepřečetli zadání, řešila povětšinou něco úplně jiného. Skupina druhá, naštěstí podstatně větší, která se prokousala povídáním o jazycích a správně pochopila definici konečného automatu a gramatiky, po přečtení zadání bez problémů obě úlohy vyřešila.

Jak tedy na konstrukci konečného automatu, který rozpoznává binární čísla dělitelná třemi a nedělitelná dvěma? Použijeme velice jednoduchý trik. Budeme automatem postupně cifru po cifře načítat číslo a průběžně si budeme pamatovat nikoli jeho hodnotu, nýbrž pouze zbytek po dělení šesti. Zjevně nám potom budou vyhovovat pouze čísla tvaru 6k+3 pro nějaké k, ostatní jsou buďto dělitelná dvojkou nebo nedělitelná trojkou. Když máme načtené číslo s aktuálním zbytkem z (tedy tvaru 6k+z), po načtení 0 dostaneme číslo 2(6k+z), po načtení 1 číslo 2(6k+z)+1. Zbývá si tedy pouze spočítat, jak se pro každé z a načtenou cifru zbytek změní.

Náš stroj tedy bude používat stavy Q={q₀,…,q₅}, kde stav q_i značí, že aktuální zbytek je i. Počáteční stav bude q₀ a jediný přijímací stav bude F={q₃}. Přechodová funkce δ bude vypadat takto:

Každý sám už si asi domyslí, že podobný postup by fungoval, pokud bychom měli zadanou libovolnou konečnou množinu M čísel, které musí, resp. nesmí dělit vstup. Stačí vzít tolik stavů, kolik je nejmenší společný násobek čísel z M, přepočítávat při načítání zbytek a vhodně zvolit přijímací stavy.

Když už máme hotový automat (Q,A,δ,q₀,F), je, jak si také většina řešitelů správně všimla, velmi jednoduché podle něj zkonstruovat ekvivalentní gramatiku (V_N,V_T,S,P). Pro stavy automatu Q={q₀,…,q_k}, zavedeme do gramatiky neterminální symboly V_N={Q₀,…,Q_k}, terminální symboly V_T=A budou písmena abecedy, počáteční symbol S=Q₀ bude neterminál odpovídající počátečnímu stavu automatu.

Pro každý stav q_i a každé písmeno p se podíváme, jaký nový stav q_j=δ(q_i,p) vrací přechodová funkce. Do množiny přepisovacích pravidel P potom dáme příslušné pravidlo Q_i→p Q_j. Pokud je navíc stav q_j přijímací, přidáme ještě pravidlo Q_i→p. Každá expanze gramatiky zjevně následuje výpočet automatu, a tudíž generuje stejný jazyk.

První dva řádky jsou víceméně stejné, lze je tedy dokonce nahradit jediným řádkem Q₀→0Q₀ | 1Q₁, příslušně modifikovat pravidlo pro Q₁ a ušetřit tak jeden neterminální symbol.

V zadání jsme tvrdili, že regulárním jazykům odpovídají právě gramatiky s pravidly tvaru N→uM a N→u, kde N,M jsou neterminály a u je terminál. První část tohoto tvrzení, konstrukce ekvivalentní gramatiky ze zadaného automatu, jsme právě ukázali. Zbývá popsat konstrukci ekvivalentního automatu ze zadané gramatiky výše uvedeného tvaru. Ta se provede opačným postupem než při převodu automat → gramatika a detaily si jistě rozmyslí každý sám.

Tomáš Valla