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

Řešení úloh


17-4-1 Mandarinková zeď (Zadání)


V některých paralelních vesmírech císař No-san zkrachoval, či nepřežil povstání svých nevěrných poddaných, ale jinde jeho Mandarínie dále prosperovala díky Vašim radám.

Problém můžeme rozdělit na dva případy. Pokud je strážců sudý počet, je řešení jednoduché. Označme si P(i) počet medailí, které vyžaduje i-tý strážce. Celkem nám bude stačit maximum z požadavků libovolných dvou sousedů – pm = max(P(i)+P(i+1)), přičemž indexy bereme cyklicky, takže n + 1 = 1. Druhy medailí budeme označovat čísly 1..p. Medaile rozdělíme takto: Strážci na liché pozici dáme medaile 1..P(i), strážci na sudé pozici dáme medaile pm - P(i) + 1..pm. Každí dva sousedi se liší paritou pozice a proto mají dohromady medaile 1..P(i), pm - P(i) + 1..pm a určitě nemají žádnou oba dva, protože pak by jich měli dohromady více než pm.

Podívejme se na lichá n. Určitě potřebujeme alespoň pm medailí, ale můžeme jich potřebovat i více. Například třem strážcům musíme dát tolik medailí, kolik je součet jejich požadavků. Označme si S(i) = ∑
i
k=1
P(i) součet prvních i požadavků. Protože jeden druh medaile můžeme dát maximálně pouze m strážcům, kde n = 2m + 1, budeme určitě potřebovat alespoň ps = S(n)/m medailí. Ukážeme, že nám bude vždy stačit p = max(ps, pm) medailí.

Danger!Myšlenka je asi taková, že máme na začátku množinu medailí L, které má strážce na liché pozici, a medaile P, které má strážce na sudé pozici. Protože ale poslední strážce je na liché pozici, měly by se množiny v průběhu rozdělování prohodit tak, aby poslední strážce měl jiné medaile než ten první. Medaile budeme rozdělovat speciálním způsobem. Půjdeme od prvního strážce k poslednímu a přitom jim budeme dávat medaile. Zapíšeme si medaile do nekonečné cyklické posloupnosti 1..p,1..p,… a budeme je přiřazovat strážcům popořadě. Označíme tuto posloupnost a, a[i] = ((i - 1) mod p) + 1. Můžeme tedy explicitně zapsat, jaké medaile dostane i-tý strážce – a[S(i - 1) + 1]..a[S(i)]. Protože p ≥ pm, nemohou dostat žádní dva sousedé stejné medaile.

Takto rozdělujeme medaile, ale jen do té doby, dokud mají strážci na liché pozici alespoň 1 z medailí 1..P(1) prvního strážce. Hledáme tedy nejmenší k takové, že součet požadavků do k-tého lichého strážce S(2k+1) je menší nebo roven k·p. Že takové k existuje se můžeme například přesvědčit tak, že zvolíme k = m. Pak víme, že mp ≥ m·ps = m ·S(n)/m ≥ S(n), takže víme, že pro k = m je předpoklad splněn a vždy takové k existuje. Nyní si ukážeme, že pokud rozdělíme výše popsaným způsobem medaile prvním 2k strážcům, můžeme strážcům 2k+1..n dávat medaile už podle parity jako pro n sudé. Podívejme se na to, jaké medaile dostane strážce na pozici 2k. Protože k je minimální, S(2k-1) > (k - 1)·p, proto strážce na pozici 2k nemá žádnou z barev p..p-P(2k+1)+1 (nakreslete si obrázek). Jsme tedy schopni najít rozdělení pro p druhů medailí, ale nám stačí jenom tento počet.

Algoritmus bude velmi jednoduchý, spočteme pm a pro n sudé vypíšeme tuto hodnotu, pro n liché si ještě spočítáme ps a vrátíme tu větší z nich. To vše určitě zvládneme s lineárním časem i pamětí – tedy O(n).

Petr Škoda


17-4-2 Válicie (Zadání)


Úlohu rozmístit Válicie na křižovatkách Mandarínie tak, aby na každé křižovatce byla právě jedna, převedeme na úlohu barvení vrcholů grafu dvěma barvami. Lze snadno nahlédnut, že obarvení prvního vrcholu jednou ze dvou barev (postavit nebo nepostavit stanici) určuje barvu ostatních vrcholů, které jsou s ním spojeny cestou. Vrcholy vzdálené o lichý počet jednotek nesmí být obarvené stejnou barvou, na rozdíl od těch na sudých pozicích, které ji musí mít stejnou. Z této úvahy hned plyne, že dvěma barvami nelze obarvit graf, který obsahuje cyklus liché délky (například trojúhelník). Protože potřebujeme minimalizovat počet stanic, vybereme si v každé komponentě souvislosti grafu tu barvu, kterou je obarveno méně vrcholů.

Algoritmus řešící úlohu může být následující. Vezmeme vrchol, obarvíme ho, a všechny jeho dosud neobarvené sousedy obarvíme týmž algoritmem druhou barvou. Úloha nemá řešení, pokud nějaký soused zpracovávaného vrcholu má již stejnou barvu. V tom případě totiž existuje v grafu cyklus liché délky.

Po dokončení obarvování komponenty zkontrolujeme, jestli je barvy značící „postavit stanici“ méně než barvy druhé. Pokud ne, barvy v komponentě zinvertujeme.

Vrcholy jsou obarvované rekurzivní funkcí pracující se seznamem sousedů. Každý vrchol je zpracován nanejvýš dvakrát. Proto je časová i paměťová složitost O(N+M).

Miroslav 'miEro' Rudišin


17-4-3 Phirma (Zadání)


Nejveleváženější císaři No-sane!

Dle Tvého hlubokomyslného rozkazu Ti phirma Jakobi-Čestná zasílá skvostné dary. Na stanovení její ceny se podíleli nejpovolanější učenci, slovutní programátoři a osvícení teoretici, kteří za použití nejďábelštějších, nejfantasknějších a nejdůmyslnějších konstrukcí, mohutného binárního stromoví roztodivných názvů, jakož i větvoví intervalového a AVL, namnoze pak půlení binárního, sestavili vzletné programy lepých tvarů.

S nejuctivějšími pozdravy
Skutečně-Nečestná, účetní

Vážená paní Skutečně-Nečestná,

již jsme se chystali Váš velkolepě vyhlížející dar přijmout, když tu jakýsi účetní nevelkých znalostí povšiml si výpočtu mnohem jednoduššího, nemnoha struktur vyžadujícího, prabídně prostého, ba až hanebně rychlého.

Poslyšte návod:

Většinu řešitelů napadla jednoduchá myšlenka – vytvořit k zadané posloupnosti a1,…,aN posloupnost částečných součtů s1,…,sN, kde si=∑
i
k=1
ak, a řešení pak hledat prostým prozkoumáním všech možných dvojic. Takový postup je sice průzračný a zaručeně vede k výsledku, ale trvá O(N2). Někteří ostřílení řešitelé objevili, že různými hrátkami se stromy můžeme vyzískat řešení v čase O(N log N), ale my si ukážeme řešení v čase O(N).

Chceme tedy najít dvojici indexů i a j (i≤ j) takovou, aby sj-si-1=ai+… +aj>0 a j-i bylo nejvyšší možné. Navíc máme vybrat úsek s největším součtem. Využijeme nápadu s posloupností částečných součtů si. Dále si připravíme pomocnou strukturku – posloupnost m1,…,mN, kde mi=max(si,…,sN) a indexy i a j, které nastavíme na začátek posloupnosti.

V každém kroku se snažíme najít nejdelší kladný úsek, který začíná prvkem i, ale děláme to jenom tehdy, když máme jistotu, že může být výhodnější než zatím nejdelší nalezený úsek. Index j tedy posouváme tak dlouho, dokud platí, že si < mj+1. Dále už nesmíme j zvyšovat, protože mj je maximem z prvků sj,…,sN, takže za indexem j se částečné součty už jenom snižují (to bychom si k zatím nalezenému kladnému úseku přičítali záporné prvky).

Jakmile nalezneme poslední j, pro které ještě platí mj > si, posuneme index i na i+1 a zkusíme najít nový kladný úsek. Klíčovým pozorováním je fakt, že s indexem j se nemusíme vracet, zlepšení může přinést jedině posun dále. Kdybychom se s j vrátili zpět, můžeme už získat jenom kratší úsek než ten už dříve nalezený.

Kdykoliv nalezneme nový úsek s kladným součtem prvků, porovnáme ho se zatím nejlepším nalezeným úsekem a zapamatujeme si samozřejmě ten lepší z nich. Porovnáváme nejprve podle délky, v případě shody ještě podle součtu prvků (ten můžeme počítat v konstantním čase, protože ai+… +aj=∑
j
k=1
ak - ∑
i-1
k=1
ak=sj-si-1).

Jak i, tak j projdou posloupnost nejhůř jednou od začátku do konce, a protože načíst a vytvořit všechna pole umíme v čase O(N), má algoritmus lineární časovou složitost.

Jana Kravalová


17-4-4 Antifrňákovník (Zadání)


Celkem jednoduché řešení této úlohy bylo v čase O(n2) vyzkoušet všechny dvojice kabelů vlevo a vpravo. Pro trochu složitější řešení si všimnu, že můžu položit dotaz „které pravé kabely jsou připojeny k těmto levým“ v čase O(n). V takovém čase si stihnu nalevo připojit k zemnění ty kabely, které potřebuji, a zjistit, které z pravých jsou uzemněny.

Nyní si stačí vybrat vhodné podmnožiny kabelů nalevo. Kabely si očísluji 1..n a budu zkoumat, jaké kabely pasují ke kabelům vpravo – Ri je číslo toho kabelu nalevo, který je spojen s kabelem i vpravo. Vyberu-li nalevo nejprve kabely s číslem nedělitelným dvěma, budou mít všechny odpovídající kabely vpravo určitě Ri liché, zatímco ostatní jsou buď nezapojené nebo mají Ri sudé. Takto jsem vlastně zjistil, jak bude vypadat 0. bit čísel R[i]. A stejně mohu zjistit i 1., 2., …, (log n)-tý bit: zapojím vždy kabely s i-tým bitem nenulovým a nastavím tento bit odpovídajícím kabelům v Ri, čili kabelům, jejichž levý konec je připojen na zemnění a má i-tý bit nenulový. Pokud bude mít nakonec nějaký kabel Ri=0, pak je určitě nezapojený, jinak bude v Ri číslo odpovídajícího levému kabelu.

Toto řešení má časovou složitost O(n log n). Navíc je to nejmenší možná složitost, což můžeme dokázat takto: i kdyby byly všechny kabely zaručeně propojeny, potřebuji zjistit, kterou z permutací mám před sebou. Těch je n!, potřebuji tedy získat řádově log(n!) ≈ n log n bitů, přičemž jednou odpovědí získám právě 1 bit. Toto je tedy dolní odhad slabší verze našeho problému, s nezapojenými kabely je to určitě jen složitější.

Tomáš Gavenčiak


17-4-5 Jazykozpytec vrací úder (Zadání)


Odvážnému štěstí přeje, praví se, a velmi podobně tomu bylo i ve čtvrté seriálové úloze. Kdo v sobě našel dosti odvahy přečíst si dlouhé a hrozivě vypadající zadání, a pochopit, co se po něm vlastně chce, zjistil, že všechny úlohy jsou velmi snadné. O tom koneckonců svědčí i bodové zisky. Účelem tentokrát nebylo vymýšlet komplikované algoritmy na komplikované problémy, jako si spíše přesně uvědomit, jak spolu souvisí různé druhy dosud převedených automatů. Ale teď už k správným řešením.

Úloha 1

Chceme-li ukázat, že jazyk L={0n1m;  1≤ n≤ m} lze rozpoznávat deterministickým zásobníkovým automatem koncovým stavem, zkrátka takový automat sestrojíme. DZA bude používat stavy Q={l,p,f}, zásobníkové symboly Z={z,0}, počáteční stav bude l a počáteční zásobníkový symbol z, jediný přijímací stav bude f. Sada instrukcí bude následující:

δ(l,0,z) = (l,z0) načti první 0
δ(l,0,0) = (l,00) čti další 0
δ(l,1,0) = (p,λ) začni odmazávat 0 ze zásobníku
δ(p,1,0) = (p,λ) maž další 0
δ(p,λ,z) = (f,z) už máme 0n1n
δ(f,1,z) = (f,z) dočítej zbylé 1

Princip je stejný jako u příkladu v zadání s tím rozdílem, že při načtení 0n1n se ještě načítá libovolný počet 1. Kdyby se při dočítání vyskytla 0, stroj se zastaví na nedefinovanou instrukci, a jelikož se nenačetlo slovo celé, bude odmítnuto.

Chceme-li ukázat, že DZA přijímajícím prázdným zásobníkem jazyk L nemůže nikdy rozpoznávat, budeme argumentovat takto: Kdybychom takový automat měli, slovo 0n1m by bylo přijato, tedy automat by vyprázdnil zásobník a zastavil se tak. Ale slovo 0n1m+1 tím pádem už nikdy nemůže být rozpoznáno, protože automat se zastavil už o krok dříve. Proto žádný takový stroj nemůže vůbec existovat. Podobně lze najít i regulární jazyk nerozpoznatelný DZAPZ. Bude to třeba jazyk {ai;  i∈N} (proč je regulární snad již nemusíme zdůvodňovat) a použijeme téměř stejný argument.

Úloha 2

U jednoho směru převodu, tedy NZA přijímající prázdným zásobníkem na ekvivalentní NZA přijímající koncovým stavem, projde naprosto stejný postup jako u deterministických ZA, který jsme si předvedli v zadání. Druhý směr je zajímavější a již nutně musí nějak využívat nedeterminismu stroje. Mějme tedy nějaký NZAKS M=(Q,A,Z,δ,q0,z0,F). Do M přidáme speciální stav qf a instrukce δ(qf, λ, z)=(qf,λ) pro každý zásobníkový symbol z. Kdykoli se vstoupí do stavu qf, zásobník se vymaže a stroj se zastaví. Z každého přijímacího stavu f potom natáhneme „odbočku“ do stavu qf pomocí instrukcí δ(f, λ, z)=(qf, z) pro každý z∈Z a f∈F. V každém přijímacím stavu se pak stroj nedeterministicky rozhodne, jestli už je to ten opravdu poslední stav (neboli slovo je celé načteno), v tom případě odbočí a přijme slovo prázdným zásobníkem. Pokud by výpočet odbočil dříve než je celé slovo přečteno, podle naší definice zásobníkového automatu bude slovo odmítnuto a nebudou tak přijímány nesmysly. Zjevně jsme tak tedy sestrojili ekvivalentní automat přijímající prázdným zásobníkem.

Úloha 3

Rozmysleme si ještě pro pořádek, jak se dá u automatů pohlížet na nedeterminismus. První úhel pohledu je takový, že stroj, může-li se v některých situacích nedeterministicky rozhodnout, je veden neomylnou intuicí, a vždy si vybere tu možnost, která vede k příjetí slova. Pokud žádná cesta k přijetí neexistuje, pak ani neomylná intuice nepomůže, a slovo bude odmítnuto. Druhý pohled je ten, že nedeterministický automat je schopen paralelně provádět mnoho větví výpočtu, a tak najít cestu k přijetí, pokud taková ovšem vůbec existuje. Oba pohledy vystihují naši původní definici nedeterminismu.

Myšlenka nedeterministického přijímání jazyka všech palindromů nad abecedou A={a,b} je poměrně jednoduchá: budeme načítat symboly na zásobník, nedeterministicky uhodneme, jestli právě přišel střed palindromu, načež začneme zásobník vyprazdňovat a kontrolovat, jestli jsou obě poloviny symetrické. Sepišme si to přesně.

Zkonstruujeme NZA přijímající prázdným zásobníkem, jehož množina stavů bude Q={l,p}, zásobníkové symboly Z={z0,a,b}, počáteční stav bude l a počáteční zásobníkový symbol z0. Sada instrukcí bude tato:

δ(l, x, z) = (l, zx)  ∀x∈A, z∈Z načti levou půlku
δ(l, x, z) = (p, zx)  ∀x∈A, z∈Z uhodni sudý střed
δ(l, x, z) = (p, z)  ∀x∈A, z∈Z uhodni lichý střed
δ(p, x, x) = (p, λ)  ∀x∈A ověř pravou půlku
δ(p, λ, z0) = (p, λ) vyprázdni zásobník a skonči

Zjevně pokud automat uhodl střed na správné pozici a obě půlky byly symetrické, slovo bude přijato. Pokud symetrické nebyly, stroj se zastaví před vyprázdněním zásobníku na nedefinovanou instrukci. Pokud stroj uhodl střed palindromu příliš brzo či příliš pozdě, nebude načteno celé slovo nebo se zastaví se na nedefinovanou instrukci před vyprázdněním zásobníku. Tyto větve výpočtu tedy nevydají špatný výsledek a automat tak skutečně přijímá právě jazyk všech palindromů.

Že na tento jazyk nestačí DZA přijímající prázdným zásobníkem se dá odůvodnit téměř stejně, jako v první úloze. Kdyby takový automat přijal palindrom ai, nemohl by již přijmout palindrom ai+1.

A to je celé.

Tomáš Valla