Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (1. soutěžní den) 57. ročníku

P-III-1 Karpaty

Jedním z nejjednodušších (a také nejpomalejších) způsobů, jak úlohu řešit, je projít postupně všechny možnosti, na které kopce byste vystoupili. V jednom průchodu bychom našli délku nejdelší rostoucí podposloupnosti a v druhém průchodu bychom pak zjistili, které vrcholy se vyskytují ve všech nejdelších podposloupnostech, které jen v některých a na které se vystoupit nesmí. Bohužel, časová složitost takového algoritmu bude řádově O(2N), protože tolik je možností výstupu na jednotlivé vrcholy (u každého si vyberete, zda na něj vystoupíte nebo ne).

Zkušený řešitel olympiády si však hravě všimne, že minimálně délku nejdelší rostoucí podposloupnosti lze zjistit výrazně rychleji metodou dynamického programování. To jsme už potkali v řešení úlohy P-I-1, nyní si ukážeme trochu jiný postup, který půjde lépe zobecnit.

Označme si di délku nejdelší rostoucí podposloupnosti, jejímž posledním členem je vi (výška i-té hory). Hledaná délka pak bude maximum z čísel di. A jak lze hodnoty di spočítat? Podívejme se, jak nějaká taková nejdelší podposloupnost P končící vrcholem i vypadá: Buď obsahuje jen vrchol i (a pak má tedy délku 1) nebo jejím předposledním vrcholem je nějaký vrchol j, pro který platí, že j < i a vj < vi. Všimněme si, že v druhém případě určitě platí, že pokud z P odstraníme poslední prvek (tedy vrchol i), získáme podposloupnost P' končící vrcholem j, která je zároveň jednou z nejdelších podposloupností, které končí v tomto vrcholu. Kdyby tomu tak nebylo, tak bychom přidáním vrcholu i na konec některé z nejdelších podposloupností končících vrcholem j získali podposloupnost, která by končila vrcholem i, ale její délka by byla větší než délka P. Takže stačí postupně počítat di v cyklu od 1 do N, pro každé i se podíváme na hodnoty dj pro j=1,...,i-1 takové, že vj < vi a, pokud nějaké najdeme, vezmeme za di jejich maximum zvýšené o jedna; pokud žádné takové vj neexistuje, nastavíme di na 1. Přímočarou implementací tohoto postupu dostaneme algoritmus s časovou složitostí O(N2).

Když jsme se takto zvládli zbavit exponenciálního času výpočtu délky nejdelší rostoucí podposloupnosti, nemohli bychom podobný princip použít i pro druhou část úlohy? Odpověď na tuto otázku je ano, ale bude to vyžadovat malinko více práce. Nejprve si kromě hodnot di spočteme i hodnoty zi, kde zi bude délka nejdelší rostoucí podposloupnosti začínající prvkem vi. Spočítat tyto hodnoty zvládneme obdobným způsobem jako u hodnot di (místo od začátku budeme posloupnost procházet od konce). Nyní nahlédneme, že délka nejdelší rostoucí podposloupnosti obsahující i-tý vrchol je di+zi-1. To proto, že pokud by P byla nějaká taková nejdelší podposloupnost a přitom její část od začátku po i-tý vrchol by nebyla nejdelší rostoucí podposloupností končící i-tým vrcholem, mohli bychom P prodloužit výměnou úvodní části za nějakou delší. Naopak spojením nejdelších podposloupností z a do i-tého vrcholu dostaneme rostoucí podposloupnost požadované délky.

Označme maximum z čísel di+zi-1 tedy L. Již víme, jak poznat vrcholy, na které vystoupit nesmíme – podíváme se, zda di+zi-1 je rovno L (pak na tento vrchol můžeme a možná i musíme vystoupit) nebo ne (a pak na tento vrchol nesmíme vystoupit). Zbývá rozpoznat ty vrcholy, na které musíme vystoupit, od těch, na které „jen můžeme” vystoupit. Pokud je pro vrchol vi hodnota di+zi-1 rovna L, pak vi je di-tým vrcholem v každé nejdelší rostoucí podposloupnosti, která ho obsahuje. Vrchol vi je tedy v každé nejdelší rostoucí podposloupnosti právě tehdy, když neexistuje jiný vrchol vj s dj+zj-1=L a di=dj.

Pokud implementujeme výše uvedený postup, dostaneme algoritmus s kvadratickou časovou složitostí, kde všechny operace kromě výpočtu hodnot di a zi zaberou jen lineární čas. Ve zbytku řešení si ukážeme, jak výpočet hodnot di a zi provést v čase O(N logN). Tím získáme algoritmus s časovou složitostí O(N logN). A jak na to? Použijeme upravené binární vyhledávací stromy. Pro každý uzel si kromě klíče, tj. hodnoty, podle které vyhledáváme (klíč tedy bude výška hory vi), zapamatujeme i délku nejdelší rostoucí podposloupnosti, která v tomto vrcholu končí nebo začíná. Tj., při prvním výpočtu si budeme pamatovat hodnotu di a při druhém zi. Navíc si ještě v každém uzlu budeme udržovat maximum z délek v podstromu tohoto uzlu.

Na začátku do stromu vložíme všechna vi a délky nastavíme na 0. To provedeme například tak, že hodnoty vi v čase O(N logN) setřídíme, odstraníme opakované výskyty stejných čísel (různé kopce přece mohou být stejně vysoké) a pak strom rekurzivně sestavíme: rekurzivní procedura dostane úsek setříděného pole, vybere prostřední prvek (řekněme, že je to x-tý prvek pole), vytvoří pro něj uzel, jehož levý podstrom vznikne rekurzivním voláním na úsek od začátku po (x-1)-ní prvek a pravý podstrom voláním na úsek od (x+1)-ního prvku do konce. Všimněte si, že hloubka takto vytvořeného stromu bude řádově log2 N.

Nyní postupně počítáme hodnoty di. Nejprve zjistíme, jaká největší délka je ve stromu uložená u nějakého uzlu s hodnotou menší než vi (pokud takovou nenajdeme, vrátíme 0). Tuto délku zvýšenou o 1 pak uložíme do di a do uzlu u s hodnotou vi nastavíme délku di a upravíme maxima na cestě z u do kořene. Nyní bude platit, že ve stromě mají nenulovou délku cesty právě uzly s hodnotami v1,...,vi, přičemž délka uložená v uzlu s hodnotou v je maximum z dj pro taková j, že vj = v a 1≤j ≤i (speciálně tedy neplatí, že hodnota dj pro j<i je nutně rovna hodnotě di uložené v uzlu s hodnotou vi=vj). Výpočet hodnot zi bude opět podobný, jen budeme postupovat od konce a hledat největší délku mezi uzly s hodnotami vyššími než vi.

Zbývá tedy vyřešit, jak najdeme onu největší délku uloženou v uzlu s hodnotou menší než nějaké x. Pro její nalezení použijeme modifikovanou proceduru na vyhledání prvku v binárním vyhledávacím stromu. V průběhu hledání budeme největší délku počítat průběžně, na začátku ji nastavíme na 0. Rozlišíme tři případy, podle toho, zda je hodnota v uzlu menší než, větší než nebo rovna x. Je-li hodnota uzlu větší než x, pak jen pokračujeme v hledání v levém podstromu. Je-li menší, pak maximum porovnáme s délkou uloženou v uzlu a maximem délek uložených v levém podstromu (protože si pamatujeme maximum délek v podstromu, stačí přečíst hodnotu z levého syna) a dále pokračujeme v pravém podstromu. Nu a pokud je hodnota rovna x, tak maximum porovnáme jen s uloženým maximem v levém synovi a skončíme. Poté, co dojdeme do uzlu s hodnotou x (takový tam určitě je), bude spočítané maximum buď 0 (to pokud neexistuje žádná uložená hodnota vi menší než x) nebo právě požadovaná délka. Časová složitost této prohledávací operace je úměrná hloubce podstromu, tedy O(logN).

Shrňme si nyní celý postup. Nejprve v čase O(N logN) setřídíme výšky, pak z nich v lineárním čase sestavíme strom, v čase O(N logN) spočteme hodnoty di a zi (N-krát voláme dvě operace s logaritmickou složitostí), v lineárním čase pro každé k zjistíme, kolik existuje vrcholů, které jsou na k-tém místě v nějaké nejdelší rostoucí podposloupnosti, a nakonec, opět v lineárním čase, vypíšeme výsledek. Pokud se týká paměti, potřebujeme si uložit hodnoty vi, di a zi, pomocný vyhledávací strom použije O(N) paměti a k uložení počtů vrcholů na k-tém místě v nejdelší podposloupnosti nám též postačí lineární paměť. Časová složitost námi navrženého algoritmu je O(N logN) a paměťová O(N). p31.pas

P-III-2 Velechrám

Nejprve si úlohu převedeme do teorie grafů. Z velechrámu uděláme graf, jehož množinu vrcholů tvoří řádky a sloupce šachovnice. Hrana mezi i-tým řádkem a j-tým sloupcem vede právě tehdy, když na příslušném poli stojí sloup. Nyní místo sloupů barvíme hrany tohoto grafu.

Dvě hrany mají společný vrchol pravě tehdy, když odpovídají sloupům, které leží ve stejném řádku nebo sloupci. Různé barvy sloupů ve stejném řádku a sloupci znamenají různé barvy hran, které mají společný vrchol. Chceme tedy obarvit hrany zkonstruovaného grafu tak, aby u každého vrcholu byly barvy všech hran různé.

Všimněte si, že potřebujeme alespoň tolik barev, kolik je maximální stupeň grafu Δ, tj. největší počet hran vedoucí z některého z vrcholů grafu. Ukážeme, že nám jich zároveň právě tolik stačí. Navíc ukážeme, jak takové obarvení i rychle najít.

Pojďme rovnou na algoritmus. Začneme s grafem bez hran. Potom budeme hrany v libovolném pořadí po jedné přidávat.

Při přidávání hrany e mohou nastat dvě možnosti. Pokud se na sousedních hranách přidávané hrany e nevyskytuje ještě všech Δ barev, obarvíme e libovolnou ze zbývajících barev.

V opačném případě to bude složitější. Označme si jako Ce množinu barev přiřazených hranám, které mají s e alespoň jeden společný vrchol. Protože e má alespoň Δ sousedních hran, s oběma koncovými vrcholy e je incidentní alespoň jedna již obarvená hrana (Δ je maximální stupeň pomocného grafu). Označme C1 a C2 množinu barev sousedních hran incidentních s jednotlivými koncovými vrcholy hrany e. Vybereme dvojici barev A ∈C1 \C2 a B ∈C2 \C1. Takové barvy lze určitě vybrat, protože C1 ∪C2 = Ce a zároveň C1 ≠Ce ≠C2.

Nyní přebarvíme některé hrany tak, abychom mohli e obarvit buď barvou A nebo barvou B. Zahoďme na chvíli všechny hrany, které nemají barvu A nebo B. Protože z jednoho vrcholu mohou vést pouze dvě hrany obarvené jednou z barev A a B, v grafu nám zbudou pouze cesty a kružnice. Navíc v koncových vrcholech hrany e začínají některé z cest, protože u obou koncových vrcholů e jedna z barev A a B chybí. Pokud jsou tyto dvě cesty různé, prohodíme barvy AB v jedné z těchto cest. Tím určitě neporušíme podmínku na různost barev u žádného vrcholu na cestě a navíc nyní chybí jedna z barev A a B mezi sousedy e. Obarvíme tedy touto barvou hranu e.

Může se nám stát, že koncové vrcholy e jsou spojeny cestou? Předpokládejme, že to tak je. Připomeňme si, že vrcholy pomocného grafu odpovídají řádkům a sloupcům šachovnice a hrany vždy vedou mezi jedním z řádků a jedním ze sloupců. Na cestě spojující koncové vrcholy hrany e se tedy pravidelně střídají vrcholy odpovídající řádkům a sloupcům šachovnice a tedy tato cesta obsahuje lichý počet hran. V takovém případě, ale její první a poslední hrana musí mít stejnou barvu (na cestě se pravidelně střídají hrany barvy A a hrany barvy B), což není možné.

Tím jsme ukázali, že vždy dokážeme přebarvit některé hrany tak, abychom mohli korektně obarvit nově přidanou hranu. Po přidání všech hran do pomocného grafu tak dostaneme korektní obarvení hran grafu.

Podívejme se na časovou a paměťovou složitost navrženého algoritmu. V naší implementaci algoritmu si potřebujeme pamatovat ke každému vrcholu v a barvě c, která hrana s barvou c je incidentní s vrcholem v. Samozřejmě si pamatujeme strukturu grafu a informace o jeho hranách a vrcholech. To nám dává paměťovou složitost O(NΔ+ M). Algoritmus přidává M hran a při každém přidání musí přebarvit až O(N) hran (nikdy nepřebarvujeme víc než dvě hrany u jednoho vrcholu). Celková časová složitost našeho algoritmu tedy je O(NM).

p32.pas

P-III-3 Překládací stroje

a) Překládací stroj bude pracovat na následující jednoduché myšlence: ke každé levé kulaté závorce obsahuje každý řetězec v množině A pravou závorku. Můžeme tedy levé kulaté závorky přeložit na řetězec a, pravé kulaté závorky na řetězec bb a na konec řetězce připsat libovolný počet znaků b. Aby se ve vytvořeném řetězci nepromíchaly znaky a a b mezi sebou, tj. nejdříve byly všechny znaky a a pak teprve znaky b, po nalezení prvního znaku, který není levou kulatou závorkou, budeme očekávat jen pravé kulaté závorky, tj. budeme překládat jen řetězce (((...))). Řetězec (((...))) tvořený n dvojicemi závorek, se tedy přeloží na řetězec s n znaky a a alespoň 2n znaky b.

Formálně je tedy vytvořený překládací stroj pětice (K,Σ,P,q0,F), kde K={začátek,konec}, Σ={(,),[,],{,},a,b}, q0=začátek a F={konec}. Množina P pak obsahuje následující překladová pravidla:

b) Do hledané množiny E prostě vhodně vložíme obě množiny A a D, a to tak, že řetězce začínající znakem a budou odpovídat řetězcům množiny A a řetězce začínající znakem b řetězcům množiny D. Řetězce množiny D lze do množiny E zakódovat jednoduše tak, že na jejich začátek připíšeme písmeno b, znaky a a b zdvojíme a znaky c nahradíme řetězcem ab. Řetězec aabbcc∈D bude tedy odpovídat řetězci baaaabbbbabab. Zakódování řetězců množiny A je složitější: každý ze znaků (, ), [, ], { a } nahradíme řetězcem aaa, aab, aba, abb, baa a bab, a navíc na začátek řetězce přidáme písmeno a. Tím jsme nadefinovali množinu E.

Samotné překládací stroje M1 a M2 je již snadné sestrojit. První stroj M1 je pětice (K,Σ,P,q0,F), kde K={začátek,stav}, Σ={(,),[,],{,},a,b}, q0=začátek a F={stav}. Množina P pak obsahuje následující překladová pravidla:

Druhý stroj M2 je pětice (K,Σ,P,q0,F), kde K={začátek,stav}, Σ={a,b,c}, q0=začátek a F={stav}. Množina P pak obsahuje následující překladová pravidla: c) První myšlenka, která každého asi napadne, je přeložit levé závorky na znaky a a pravé závorky na znaky b. Takovéto řetězce určitě obsahují stejný počet znaků a a b, nicméně určitě takto nezískáme všechny řetězce množiny C (např. ty, které začínají znakem b). Zkusme tedy tuto myšlenku vylepšit a pro jeden typ závorek překládat levé závorky na a a pro jiný na b. Uvažujeme tedy následující překládací stroj P tvořený pěticí (K,Σ,P,q0,F), kde K={stav}, Σ={(,),[,],{,},a,b}, q0=stav, F={stav} a množina P obsahuje následující čtyři překladová pravidla: (stav,(,a,stav), (stav,),b,stav), (stav,[,b,stav) a (stav,],a,stav).

Zbývá si rozmyslet, že množinu A přeloží stroj P na množinu C. Zjevně každé slovo, které stroj P vytvoří, náleží do množiny C. Nyní dokážeme indukcí, že stroj P vytvoří každé slovo x1x2...xk∈C (číslo k je zjevně sudé). Pokud k=0, je tvrzení jasné. Pokud k=2, pak x1x2=ab nebo x1x2=ba a stroj P přeloží řetězec y1y2=() na ab a řetězec y1y2=[] na řetězec ba.

Předpokládejme tedy, že k≥4. Pokud x1=a a xk=b, pak podle indukčního předpokladu existuje řetězec y2...yk-1, které se přeloží na řetězec x2...xk-1. Řetězec (y2...yk-1) pak stroj P přeloží na x1x2...xk. Analogicky postupujeme, pokud x1=b a xk=a, s tím rozdílem, že místo kulatých závorek doplníme závorky hranaté.

Zaměřme se nyní na případ, kdy x1=xk=a. Nechť f(i) je rovno rozdílu počtu znaků a a počtu znaků b v řetězci x1...xi. Zjevně platí f(1)=1, f(k-1)=-1 a f(k)=0. Protože se hodnoty f(i) a f(i+1) liší právě o 1 a f(1)>0>f(k-1), musí existovat index 1<l<k, pro který je hodnota f(l) nulová. Zjevně pak platí, že x1...xl∈C a xl+1...xk∈C. Podle indukčního předpokladu pak existuje řetězec y1...yl∈A, který stroj P přeloží na řetězec x1...xl, a řetězec yl+1...yk∈A, který se přeloží na řetězec xl+1...xk. Řetězec y1...yk∈A je pak strojem P přeložen na řetězec x1x2...xk. Případ x1=xk=b lze rozebrat analogicky.