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

Řešení úloh

• 14-1-1: Kostky
• 14-1-2: Orientační běh
• 14-1-3: Elektrická vedení
• 14-1-4: k-Klidná posloupnost
• 14-1-5: Turingovy stroje

14-1-1 Kostky (Zadání)

Tuto úlohu (jako ostatně skoro všechny v KSP) jde řešit hrubou silou, tzn. probráním všech možností; bohužel se také touto cestou mnoho řešitelů vydalo. 1 bod za takováto řešení jim budiž výstrahou.

Povšimneme-li si toho, že jestliže kostičky k₁ a k₂ nemají stejnou podstavu a k₁ se dá postavit na k₂, pak k₂ se nedá postavit na k₁, vzklíčí v nás podezření, zda by kostičky nešlo nějak uspořádat. Toto podezření snadno potvrdíme ověřením toho, že pokud kostička k₁ jde postavit na kostičku k₂ a ta jde postavit na kostičku k₃, tak jde postavit i přímo k₁ na k₃. Kostičky si tedy můžeme seřadit za sebe tak, že kostička k půjde postavit pouze pod předešlé kostičky (ne nutně všechny). Nyní se nabízí řešení dynamickým programováním:

Kostičky si setřídíme podle šířky podstavy a v nerozhodných případech podle hloubky. Dále si budeme postupně brát kostičky od nejmenší a budeme si počítat, jakou největší věž můžeme postavit tak, aby tato námi zvolená kostička k byla úplně dole. Taková věž je buď k samotná, nebo k, na níž leží nějaká věž v. Kostičku úplně vespod v si označme l. Nyní provedeme dvě jednoduchá pozorování:

1. v musí být největší věž, kterou lze s l ve spodu postavit (jinak bychom si mohli místo ní vzít tu větší).
2. l musí být menší než k, tedy vzhledem k našemu uspořádání již pro ni máme spočítanou výšku této maximální věže.

Tento postup má časovou složitost O(n²). Jde to lépe? Místem, které nás zdržuje při výpočtu výšky věže, kterou lze postavit na k, je průchod přes všechny kostky před ní, při němž hledáme tu, kterou na k postavit. Co to přesně znamená? Hledáme kostičku, která je nanejvýš tak široká i hluboká, jako k. Nicméně všechny kostičky před k jsou vzhledem ke zvolenému setřídění nanejvýš tak široké jako k. Tedy se tato podmínka redukuje na to, aby tato kostička byla nanejvýš tak hluboká jako k. Zajímá nás tedy maximum nějaké hodnoty (výšky věže) přiřazené číslům (šířkám kostiček) na nějakém intervalu (od hloubky nejmělčí kostičky po hloubku k). Existuje datová struktura, která nám umožňuje na takovéto dotazy odpovídat v logaritmickém čase (a také jsme schopni do ní přidat hodnotu v logaritmickém čase). Jejím použitím dosáhneme optimální časové složitosti O(n log n). Jak tato struktura vypadá:

Bude nám stačit, aby čísla, jimž budeme přiřazovat hodnoty, byla v rozsahu od 0 do n-1 (vzhledem k tomu, že u hloubek nás zajímá pouze uspořádání, si je můžeme snadno přečíslovat). Naši strukturu bude tvořit vyvážený binární strom. Jeho listy si zleva doprava očíslujeme od 0 do n-1 (obecně nám nějaké zbydou, pokud n nebude mocnina 2, ale to nám nevadí – zvolíme-li hloubku stromu na log n (zaokrouhleno nahoru), bude jich nejvýše n). Do těchto listů si budeme ukládat hodnoty odpovídající příslušným číslům. Vnitřní uzly pak budou odpovídat intervalům – konkrétně těm číslům, která leží v jejich podstromu (tedy např. kořen bude odpovídat všem číslům v rozsahu od 0 do n-1) a bude obsahovat maximum z jejich hodnot. Nejprve se podívejme, jak bude vypadat změna hodnoty v k-tém prvku; zřejmě tím ovlivníme pouze hodnoty přiřazené listu k a uzlům na cestě z něj ke kořeni. Těch je pouze logaritmický počet a jsme každou z nich schopni spočítat v konstantním čase (jako maximum z hodnot přiřazených synům daného uzlu), tedy nám to zabere slibovaný logaritmický čas.

Nechť tedy chceme zjistit maximum z hodnot v nějakém intervalu I. Začneme v kořeni a podíváme se, zda I leží celý v jednom intervalů odpovídajících jeho synům. Je-li tomu tak, ten druhý nás nezajímá – přesuneme se tedy do toho prvního a postup opakujeme. Zajímavější je případ, kdy I protíná oba tyto intervaly. Stále ale ještě máme šanci na jednoduché řešení: pokud I obsahuje jeden z těchto intervalů, maximum z hodnot na této části známe rovnou (je uloženo v příslušném uzlu). Stačí se tedy přesunout do druhého intervalu, opakovat postup a na konci vzít maximum ze získaných hodnot. Nicméně se nám může stát, že toto nenastane; v té chvíli nám nezbývá nic jiného, než interval rozdělit na dva a popisovaný postup použít na oba (a samozřejmě na konci vzít větší z výsledků). Mohlo by se zdát, že toto nám může zkazit časovou složitost, ale není tomu tak – snadno nahlédneme, že jakmile jsme jednou provedli rozdělení intervalu, vždy už budou nastávat pouze první dvě možnosti; tedy k rozdělení dojde nanejvýš jednou. Vzhledem k tomu, že první dvě možnosti nás vždy přesunou ve stromu o úroveň níž a potřebují na to konstantní čas, je časová složitost této operace O(log n).

Ve skutečnosti v programu zneužívám toho, že dotazy jsou vždy speciálního tvaru (na interval od začátku někam). Díky tomu nemůže dojít na třetí případ (dělení intervalu), což program trochu zjednodušuje.

Zbývá se podívat na paměťovou složitost. Ta je lineární (jediným místem, které by nám mohlo něco pokazit, je strom použitý pro zjišťování maxim; nicméně počet vnitřních uzlů binárního stromu je roven počtu listů bez jedné, a počet listů je menší než 2n.

Program

Zdeněk Dvořák

14-1-2 Orientační běh (Zadání)

Jak bylo možné poznat z bodového ohodnocení, patřila tato úloha k těm snazším, což potvrzuje fakt, že většina došlých řešení úlohu více či méně efektivně řešila (což se bohužel nedá říci o určování časové a paměťové složitosti).

Je evidentní, že chceme udělat průnik ze seznamů ze všech stanovišť. Budeme postupovat takto: Načteme závodníky, kteří proběhli prvním stanovištěm do lineárního spojového seznamu. Pak pro každé další stanoviště projdeme „náš“ seznam a seznam ze stanoviště a z „našeho“ seznamu odstraníme závodníky, kteří neproběhli daným stanovištěm. Protože po zpracování k stanovišť jsou v našem seznamu právě ti závodníci, kteří proběhli všemi prvními k stanovišti, získáme po zpracování všech stanovišť hledaný seznam poctivých závodníků.

Při zpracovávání jednoho stanoviště se „postavíme“ na začátek „našeho“ seznamu a pak vždy načteme číslo závodníka ze vstupu (A) a porovnáme ho s číslem na aktuální pozici „našeho“ seznamu (B). Mohou nastat tři případy:

1. A>B: závodník B neproběhl aktuální stanoviště (protože seznam závodníků ze stanoviště je setříděný), bez milosti ho z „našeho“ seznamu vyřadíme, vezmeme následujícího závodníka z „našeho“ seznamu a znovu jej porovnáváme s A, dokud nenastane některý z následujících případů (tj. dokud z „našeho“ seznamu neodstraníme všechny závodníky s čísly menšími než A).
2. A=B: vše je v pořádku, závodník A dosud proběhl všechna stanoviště, v „našem“ seznamu se posuneme na následující pozici.
3. A<B, nebo jsme na konci „našeho“ seznamu: závodník A neproběhl předchozí stanoviště, takže na něj můžeme zapomenout a zpracovávat dalšího.

Když takto zpracujeme celý seznam z aktuálního stanoviště, ještě nezapomeneme z „našeho“ seznamu odstranit všechny závodníky od aktuální pozice dále, protože ti také neproběhli aktuálním stanovištěm (toto je také odstraňování prvků, takže dále jej zahrneme pod první případ).

Tím jsme získali průnik dvou vzestupně setříděných seznamů. Jednodušeji se to dá říci tak, že máme-li dva vzestupně setříděné seznamy a jejich první prvky se nerovnají, menší z těchto prvků v druhém seznamu jistě není a můžeme jej tedy odstranit, stejně jako odstraníme prvky v jednom seznamu, je-li druhý prázdný. Ten složitější popis se nám bude ale hodit pro určování časové složitosti získání tohoto průniku:

Má-li seznam z k-tého stanoviště celkem N_k závodníků, načetli jsme N_k čísel a s každým z nich jsme prošli právě jednou případem 2) nebo 3). Případem 1) jsme mohli obecně projít vícekrát, ale při každém výskytu případu 1) rušíme jeden prvek z „našeho“ seznamu, tedy případ 1) se za celou dobu běhu programu může vyskytnout nejvýše tolikrát, kolik v něm na začátku bylo prvků, to je N₁ krát.

Celková časová složitost je O(N₁) pro zpracování prvního stanoviště a O(N₂ + ...+ N_M) pro případy 2) a 3) (je-li M počet stanovišť) a O(N₁) pro případy 1). Ještě nesmíme zapomenout, že pro každé stanoviště musíme udělat trochu práce (přejít na začátek „našeho“ seznamu), i když je seznam ze stanoviště prázdný (což by se také mohlo stát), a započítat proto ještě O(M). Pokud označíme P počet čísel na vstupu, přičemž za číslo považujeme i -1, kterou ukončujeme seznam každého stanoviště, je časová složitost O(P). Paměťová složitost je zjevně O(N₁).

Vzorové řešení používá jediný netriviální obrat: potřebujeme odebírat prvky z aktuální pozice v seznamu. K tomu pro aktuální pozici potřebujeme vědět, odkud na ni ukazuje předchozí prvek nebo hlava seznamu. Dá se použít obousměrný seznam nebo si pamatovat prvek před aktuální pozicí (pak bychom museli začátek seznamu ošetřit zvlášť nebo na začátek seznamu vložit „falešný“ prvek), vzorové řešení používá ukazatel na ukazatel. Proměnná lp ukazuje na ukazatel na aktuální prvek v seznamu, *lp je tedy ukazatel na aktuální prvek.

Program

Mirek Trmač

14-1-3 Elektrická vedení (Zadání)

Zločinecký syndikát opět zasáhl a k naprostému zděšení inženýrů AEZu se z aletonských podzemních krčem rozšířil po planetě drb o plánovaném rozšiřování servisních stanic na kulábrová centra. Není se pak čemu divit, že velké množství došlých návrhů na rozmisťování SS si počínalo poněkud neskromným způsobem. Největší experti navrhovali dokonce umisťování po celém Aletonu krom okrajových stanic; pozůstatek pozemské sofistické školy započal vychytrale obdobné návrhy vylepšovat rozpustilými heuristikami, kdy ze kterého vrcholu SS odstranit. Když vedení AEZu přešly první záchvaty entuziastického vymýšlení protipříkladů, rozhodlo se brát opravdu vážně jen návrhy, které zdůvodnily, proč navržená heuristika najde v skutku optimum (mnozí se zjevně řídili pravidlem Je-li to kopyto – platí to. Ku podivu však poté zapomněli kopyto dokázat.)

Vzrůstající tradice foliantismu si i pro tentokrát našla své příznivce, kteří bohům díky podnes nechávají heuristikám spát. Listy si rozdělili na tré druhů – listy nepokryté (LN), listy pokryté sousedním servisem (LP) a listy servisní (LS).

Je-li LN můžeme ho pokrýt pouze dvojím způsobem – vložením SS do LN nebo do jeho souseda – je však patrné, že varianta se sousedem je výhodnější. Po vložení je pro nás list nezajímavým (v řešení už nebude hrát roli) – můžeme ho proto odtrhnout.

Je-li LP, je taktéž nezajímavý a rovnou trháme.

Je-li LS, je třeba pouze dohlédnout na to, aby jeho sousedé nebyli označeni za nepokryté (to budeme dělat při umisťování SS) a dál už nás také nezajímá.

A teď přijde kouzlo – protože máme zadáním zaručeno, že graf je stromem, odtržením listu, vznikne nový list se kterým víme, co si počít – nemusíme už tedy vymýšlet nic dalšího.

Postup je krom starání se o pokrytost téměř identický s úlohou 13-1-2 – naleznu všechny listy. S každým naložím podle postupu uvedeného výše. Vzniknou nové listy a celý cyklus bude opakován, dokud je co trhat. Výsledkem pak pro nás není zbylé centrum stromu, nýbrž všechny vrcholy označené za servisní.

Implementace: Fronta, do které si postupně ukládám listí určené k utrhnutí. Při každém utržení vkládám do fronty nově vzniklé listy. Ke každému vrcholu si navíc vedu záznam, jakého je typu (pokryt).

Čas a paměť: Na každý vrchol šáhnu jednou – celkem tedy O(n) – a u každého vrcholu hledám sousedy – stromeček má v celém grafu lineární počet sousedů, tedy +O(n) = O(n). Paměťová složitost je kvadratická, leč jako obvykle bychom byli schopni ji převést na lineární. A přesně v ten slavný den, kdy k nám byl zaveden elektrický proud, byla ukázána konečnost, ježto v každém kroku ubereme jeden z konečného počtu vrcholů.

Program

Pavel Šanda

14-1-4 k-Klidná posloupnost (Zadání)

Hledejme nejdříve délku nejdelší k-klidné podposloupnosti. Řešení si ukážeme ve třech krocích; začneme poměrně jednoduchým algoritmem, který budeme postupně vylepšovat.

Krok 1. Použijeme myšlenku dynamického programování. Zavedeme si celočíselné pole P délky n, jehož i-tý prvek bude udávat délku nejdelší vybrané k-klidné podposloupnosti začínající i-tým prvkem vstupní posloupnosti. Poslední prvek vstupu je sám o sobě podposloupností, tedy P_n nastavíme na 1. Teď se budeme postupně za každý prvek a_n-1, a_n-2, … , a₁ pokoušet napojovat co možná nejdelší k-klidnou podposloupnost. Když už ale máme spočítané nejdelší podposloupnosti od a_i napravo, prostě vybereme maximum z těch P_j od P_i napravo, kde se a_i a příslušné a_j neliší více než o k, (když nic napojit nejde, maximum vyjde 0) a uložíme ho zvýšené o jedničku.

Po konci výpočtu najdeme v P maximum, které je řešením. Správnost algoritmu je zřejmá už z popisu, šťouralové si ho mohou formálně dokázat indukcí. Jak je to s časovou složitostí: provádí se 1+2+3+...+(n-1) operací, což se napočítá na O(n²). Paměťová složitost je lineární, pamatujeme si P a vstup.

Krok 2. Jak je vidět, zbytečně jsme testovali i prvky, jejichž rozdíl je moc velký. Když si nyní vstupní posloupnost setřídíme, budeme mít prvky lišící se méně než k hned vedle sebe. Zase od konce vyhledáme aktuální a_i půlením intervalů v setříděné posloupnosti S a podíváme se nalevo i napravo tak daleko, dokud se nám prvky nezačnou lišit o více než k, a z nich vybereme maximum.

Na začátku si P nainicializujeme na nuly; maximum budeme zkoumat z P_k nalevo a napravo od vyhledaneho P_j včetně P_j, to když už se hodnota a_i někde vyskytla. S vynulovaným P se nemusíme ani starat o to, jestli je zkoumaný prvek skutečně napravo od a_i.

Časová složitost je O(nk+n log n), posloupnost setřídíme v O(n log n), n-krát v logaritmickém čase vyhledáme číslo v poli a prozkoumáme až 2k sousedů. (Při použití tohoto algoritmu je ještě třeba nechat v S jen jeden prvek téže hodnoty, trochu se pak zkomplikuje výpis posloupnosti.)

Krok 3. Pro jednoduchost předpokládejme, že n je mocninou dvojky a postavme si nad S dokonale vyvážený binární strom. Jeho listy tvoří hodnoty z P, ale v pořadí posloupnosti S, v jeho vrcholech je maximum celého podstromu, tedy větší ze dvou čísel o hladinu níže. Všimněte si nyní, že každý interval v S lze rozdělit na úseky, jejichž délka je mocninou dvojky, které přesně odpovídají velikostem podstromů jednotlivých uzlů. Protože nejhorší možné rozdělení intervalu na úseky (tyto úseky nazveme pokrytím intervalu) je 1,2,4,…,4,2,1, je počet úseků (tedy vlastně počet vrcholů, z nichž získáme maximum celého intervalu) úměrný logaritmu velikosti intervalu.

Binárním hledáním v S nalezneme první prvek intervalu <a_i-k;a_i+k> a poslední prvek intervalu (z S není třeba vyhazovat duplikáty, binární hledání najde k hodnotě vždy jen jeden index); promítneme si je jako l a r do spodní hladiny stromu T. Nyní budeme postupně interval ořezávat tak, že visí-li l na pravé větvi, zahrneme ho do pokrytí a posuneme v hladině o prvek doprava, visí-li r na levé větvi, zahrneme ho do pokrytí a posuneme se doleva. Pak se posuneme s l a r po příslušných hranách o hladinu výše a celý proces opakujeme, dokud se nám l s r nepotkají.

Po logaritmicky mnoha krocích tedy nalezneme maximum z intervalu. Po updatu P_i je ještě třeba správně obnovit strom, to však zvládneme postupným průchodem od odpovídajícího listu ke kořeni taktéž v logaritmickém čase. Celkový čas bude tím pádem O(n log n). Strom má 2n uzlů, paměť zůstane O(n).

Ještě zbývá vypsat nejdelší podposloupnost. Pokud jsme plnili P_j odzadu pro j od n k jedné, bude mít první prvek nejdelší podpousloupnosti maximální hodnotu v P. Všimněte si, že následující prvek je libovolný takový, který se liší o méně než k a hodnotu v P má o jedna nižší. Nepotřebujeme si pamatovat pole předchůdců ani obracet výstup, postačí jediný průchod polem P.

Pár slov k programu: n si zarovnáme na nejbližší vyšší mocninu dvojky. Pak budeme moci strom uložit do pole a indexovat ho podobně jako haldu, tj. od 1, na začátku pole budou vyšší hladiny, ke konci nižší. Princip ořezávání je stejný jako v popisu, ale l je index prvního prvku intervalu a r je index prvního prvku za intervalem. l a r jsou indexy v S a protože vrcholy stromu bez dolní hladiny včetně nultého nepoužívaného prvku zabírají právě n míst, přičtením n dostanu index v poslední hladině stromu. S tímto číslováním jsou-li l a r lichá, je třeba zahrnout je do pokrytí. O hladinu výše se posuneme vydělením l a r dvojkou. Binární hledání funguje na principu nahazování bitů od nejvyššího k nejnižšímu.

Program

Tomáš Valla

14-1-5 Turingovy stroje (Zadání)

Většina z vás zvládla oba Turingovy stroje více či méně elegantně zkonstruovat v optimální složitosti. Na co jste občas zapomínali bylo, že vstupní slovo může být i prázdné (tedy neobsahovat žádné znaky) a hlavu Turingova stroje jste v tom případě poslali hledat v nekonečnu pravý konec pásky, případně jste stroj donutili bezradně kroutit hlavou nad nedefinovaným přechodem.

A nyní stroj na půlení slova: Stroj bude pracovat tak, že vždy odmaže jednu jedničku z počátku slova, pak přejede na konec slova a zde též odmaže jednu jedničku. Pak se hlava vrací na počátek slova a odmazávání se opakuje. Po odmazání všech číslic bude hlava uprostřed slova a stačí tedy vlevo od ní dopsat jedničky. Stroj potřebuje O(n²) kroků a paměť O(n). Tento algoritmus jsem v řešení zvolil proto, že ho lze velmi snadno upravit i na případ, kdy abeceda bude obsahovat více znaků, než jen 1 a Λ. V tom případě totiž můžeme znaky z počátku slova místo mazání „čárkovat“ – přidáme si od abecedy nová písmena a', b', c'… a znak a budeme přeznačovat na a', b na b' atd.

Jan Kára