Čtvrtá 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-4-1: Mandarinková zeď
• 17-4-2: Válicie
• 17-4-3: Phirma
• 17-4-4: Antifrňákovník
• 17-4-5: Jazykozpytec vrací úder

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ů – p_m = 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 p_m - P(i) + 1..p_m. Každí dva sousedi se liší paritou pozice a proto mají dohromady medaile 1..P(i), p_m - P(i) + 1..p_m a určitě nemají žádnou oba dva, protože pak by jich měli dohromady více než p_m.

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 ≥ p_m, 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·p_s = 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 p_m a pro n sudé vypíšeme tuto hodnotu, pro n liché si ještě spočítáme p_s 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).

Program

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).

Program

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ů.

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:

Chceme tedy najít dvojici indexů i a j (i≤ j) takovou, aby s_j-s_i-1=a_i+… +a_j>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ů s_i. Dále si připravíme pomocnou strukturku – posloupnost m₁,…,m_N, kde m_i=max(s_i,…,s_N) 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 s_i < m_j+1. Dále už nesmíme j zvyšovat, protože m_j je maximem z prvků s_j,…,s_N, 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í m_j > s_i, 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ý.

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.

Program

Jana Kravalová

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

Celkem jednoduché řešení této úlohy bylo v čase O(n²) 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 – R_i 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ě R_i liché, zatímco ostatní jsou buď nezapojené nebo mají R_i 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 R_i, č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 R_i=0, pak je určitě nezapojený, jinak bude v R_i čí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ší.

Program

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={0ⁿ1^m;  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í:

Princip je stejný jako u příkladu v zadání s tím rozdílem, že při načtení 0ⁿ1ⁿ 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 0ⁿ1^m by bylo přijato, tedy automat by vyprázdnil zásobník a zastavil se tak. Ale slovo 0ⁿ1^m+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 {aⁱ;  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,δ,q₀,z₀,F). Do M přidáme speciální stav q_f a instrukce δ(q_f, λ, z)=(q_f,λ) pro každý zásobníkový symbol z. Kdykoli se vstoupí do stavu q_f, 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 q_f pomocí instrukcí δ(f, λ, z)=(q_f, 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={z₀,a,b}, počáteční stav bude l a počáteční zásobníkový symbol z₀. Sada instrukcí bude tato:

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 aⁱ, nemohl by již přijmout palindrom aⁱ⁺¹.

A to je celé.

Tomáš Valla