První série dvacátého třetího ročníku KSP

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

Řešení úloh

23-1-1 Básníkův deník (Zadání)

Podúloha najít nejvyšší místo, kde spal, splnila svůj účel: vyřešili jste ji všichni. Stačilo si jen počítat nadmořské výšky přičtením toho, co za den ušel, k výsledku včerejšího dne a při tom si v proměnné aktualizovat nejvyšší místo, kam došel. Času to zabere O(n) a stejně tak paměti (n je počet dnů, po které psal deník).

Nalezení nejčastějšího místa, kde přespal, šlo řešit různými způsoby. Nejoblíbenější byl pomocí třídění.

V setříděných nadmořských výškách už stačí najít tu, která je nejdelší. To jste zvládli při jednom projití. Průběžně si pamatovat, kolik stejných čísel za sebou bylo viděno, a srovnávat to se zatím nejdelším viděným úsekem. Třídění trvá lepšími algoritmy O(n log n) a projití O(n). Celkově tedy O(n log n).

Hodně z vás taky využívalo vyhledávacího stromu, někdy převlečeného za mapu či slovník, ale bylo podstatné si při tom uvědomit, že se o vyhledávací strom jedná. Složitosti při tom zůstávají stejné.

Program (C)

Jitka Novotná

23-1-2 Jedna geometrická (Zadání)

Nejprve pár slov k došlým řešením. Mnozí z vás se u této úlohy pokoušeli hledat dva nejvzdálenější body a sestrojit nad nimi Thaletovu kružnici. To však obecně nefunguje, viz obrázek 1. Hledaný střed kruhu dokonce ani nemusí ležet na ose dvou nejvzdálenějších bodů (není tedy pravda, že oba tyto body leží na jeho obvodu) – protipříklad si zkuste vymyslet sami.

Obrázek 1: protipříklad na hledání 2 nejvzdálenějších bodů. Mezi bodem nahoře a oběma body na obvodu je menší vzdálenost než mezi samotnými body na obvodu.

Pouze pár řešení fungovalo a z nich jen jedno pracovalo optimálně. Gratulace putuje k Jakubu Zíkovi, jenž nastudoval lineární algoritmus nezaložený na pravděpodobnosti (těžší na pochopení než zde prezentované řešení pracující lineárně jen v průměru) a pak ho popsal. Jak vidno, ne každá úloha s krátkým zadáním má i krátké a jednoduché řešení.

Jedná se však o problém starý (poprvé se jím zabýval anglický matematik Sylvester v roce 1857) a v praxi využitelný. Vezměte si například firmu, která má po zemi rozmístěné klienty a hledá místo pro své středisko tak, aby k němu žádný klient neměl moc daleko. Říká se mu také „problém bomby“ (chceme zjistit, kde odpálit výbušninu a jak má být velká, abychom zničili všechny cíle).

První pozorování

Nyní k tomu, jak se úloha řeší. Nejmenší kruh obsahující všechny body si označíme K. Při řešení úlohy se budou hodit následující pozorování:

Pohled do ZOO algoritmů

Algoritmů řešících takovouto úlohu je více, zde si letmo představíme ty jednodušší a letmo ten „nejhustější“, ale kdo chce, ať rovnou přeskočí na sekci randomizovaný algoritmus, kde bude pořádně vysvětleno v průměru lineární řešení.

O kousek výše je v pozorováních zmíněno, že kruh K je určen 2 nebo 3 body. Co prostě vzít všechny dvojice a trojice bodů, opsat jim kružnici, zkontrolovat, jestli v ní leží všechny body, a vybrat nejmenší? To bude určite fungovat, jen časová složitost je nepěkných O(N4).

Existuje celkem přímočaré (geometricky myšleno) řešení bežící v čase O(N2). Skládá se z následujících kroků:

  1. Na začátku vezměte nějaký kruh, který bude určitě obsahovat všechny body (je jedno jaký).
  2. Najděte nejvzdálenější bod A od středu kruhu a zmenšete poloměr na vzdálenost mezi A a středem. Kruh se očividně zmenší a stále bude obsahovat všechny body.
  3. Pokud na obvodu leží jen bod A, posunujte střed po přímce mezi A a středem směrem k A a zároveň zmenšujte jeho poloměr, aby A stále ležel na obvodu. Pokračujte, dokud se obvod kruhu nedotkne jiného bodu B.
  4. Nyní tedy leží na obvodu minimálně 2 body. Dle našich pozorování potřebujeme zjistit, jestli jsou mezi nimi 3 tvořící ostroúhlý trojúhelník. Lze nahlédnout, že takové 3 body neexistují právě tehdy, když na obvodu lze najít část neobsahující body, která je delší než půlka obvodu (podívejte se na poslední obrázek u pozorování). Ta také může být vždy maximálně jedna.
  5. Pokud tam taková část není, můžeme skončit. Jinak vezměme dva body na okrajích této části bez bodů (nazveme je D a E), zmenšujme poloměr kruhu a posouvejme střed tak, že D i E jsou stále na jeho obvodu. Mohou nastat dva případy:
    1. Průměr kruhu je vzdálenost mezi D a E: pak jsme nalezli nejmenší kruh obsahující všechny body.
    2. Na obvod kruhu se dostane bod F, máme tedy alespoň 3 body na obvodu a můžeme opět přejít na bod 4 (tj. zkusit najít část bez bodů delší než půlka obvodu a případně opět zmenšovat kruh).

Implementace tohoto geometrického postupu je trochu obtížná. Například zmíněné zmenšování kruhu bude opět hledání jistým způsobem nejvzdálenějšího bodu (přesněji řečeno třeba pro krok 2, pokud jsou dány dva body na obvodu a přímka, po níž se pohybuje střed, je třeba vypočítat, kde bude ležet střed, z toho se získají poloměry a vybere se ten největší).

Kroky 1, 2 a 3 zaberou lineární čas, samotný krok 4 také, ale může se stát až (N - 2)-krát, že se bude krok 4 opakovat. Proto je časová složitost v nejhorším případě O(N2).

Toto řešení bylo objeveno až v roce 1972 pány Elzingou a Hearnem, potom následovaly těsně po sobě nápady na první O(N log N) algoritmy (Shamos a Hoey v r. 1975, Preparata v r. 1977 a Shamos v r. 1978).

Zajímavý algoritmus vychází z pozorování, že konvexní obal určuje hledaný nejmenší kruh. V čase O(N log N) (resp. O(N), máme-li body seřazené), najdeme konvexní obal, jeho velikost budiž H, a na něj prostě pustíme kvadratický algoritmus, což dává složitost O(N log N + H2).

Až v roce 1983 vymyslel Nimrod Megiddo k překvapení všech lineární algoritmus založený na metodě prořezávej a hledej (anglicky prune and search). Podstatou algoritmu je na základě několika geometrických triků odstranit v lineárním čase n/16 bodů bez změny nejmenšího kruhu obsahujícího všechny body.

Na zbylých 15n/16 bodů je pušten algoritmus znovu a tak dál, dokud nezbyde jen celkem málo bodů (např. 15), pro než lze úlohu rychle vyřešit i kvadratickým algoritmem. Vtip je v tom, že složitost jednotlivých kroků algoritmu se posčítá díky vlastnostem geometrické řady na lineární složitost, přesněji řečeno: n + 15n/16 + 225n/256 + …= 16n. Jelikož úplné vysvětlení by zabralo pěkných pár stránek, raději si přečtěte původní anglický článek.

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm, N. Megiddo, Linear-Time Algorithms for Linear Programming in R3 and Related Problems, SIAM Journal on Computing, Vol. 12, 759–776, dostupné na https://epubs.siam.org/doi/abs/10.1137/0212052.

Randomizovaný algoritmus

Jak jsme slíbili, teď předvedeme randomizovaný algoritmus (randomizovaný znamená založený na náhodě, v tomto případě náhoda ovlivňuje časovou složitost), běžící v průměru lineárně. Vymyslel ho Welzl v roce 1991. Ten začne s 2 body, jimž opíše kružnici, a poté postupně přidává bod po bodu a upravuje nejmenší kruh K obsahující všechny dosud přidané body, je-li to nutné. Náhodné pořadí přidávaných bodů zajistí onu lineární složitost, jak později ukážeme.

Na začátku je tedy vhodné náhodně uspořádat body v čase O(N), aby „zlý“ uživatel nezadal pořadí, na němž program poběží pomalu (třeba i body setříděné dle souřadnice x způsobí pomalý průběh, jak se za chvíli ukáže). Tohle můžeme udělat například tak, že vybereme náhodný prvek z pole (tedy vygenerujeme číslo od 1 do N), ten prohodíme s posledním, pak vezmeme náhodný prvek, ale už jen od 1 do N-1, prohodíme s předposledním… A takto postupujeme, dokud nedojdeme na začátek.

Nyní přijde trocha geometrických hrátek s body. Začněme tedy prvními dvěma a opišme jim kruh, jež nazveme K2. Obecně pak Ki bude nejmenší kruh obsahující body 1…i. Co dělat, když přidáme i-tý bod a máme kružnici Ki-1? Pokud bod náhodou padne do kruhu Ki-1 (nebo na jeho obvod), pak Ki = Ki-1, tedy kruh se nezměnil a můžeme pokračovat vesele dál.

Mnohem zajímavější je případ, kdy přidávaný bod leží mimo kruh Ki-1. Označme tento bod Bi. Je zřejmé, že Bi musí ležet na obvodu kruhu Ki, jinak by už ležel uvnitř Ki-1 (neurčuje kruh, můžeme ho tedy vynechat beze změny kruhu). Takže nyní máme za úkol spočítat nejmenší kruh pro i-1 bodů s Bi na obvodu. A jak? Zavoláním stejné funkce pro i-1 bodů jen navíc s informací, že jistý bod má být na obvodu.

Obrázek 5: bod Bi leží mimo Ki-1, takže je třeba zvětšit kruh.

Naším řešením bude funkce, která v parametrech dostane množinu bodů M (ty, pro něž počítá nejmenší kruh) a seznam bodů, jež musí ležet na obvodu (body na obvodu nemusí být v množině M). Funkce nejprve zkontroluje, jestli už na obvodu nemusí ležet 3 body (pak je kruh jednoznačně určen a dopočítá se) nebo není M prázdná (v tom případě se kruh opíše bodům na obvodu, jsou-li nějaké). Poté se rekurzivně zavolá s množinou M o jeden bod B menší (to je ten přidávaný bod), uloží si vrácený kruh K a následně zjistí, zdali bod B leží v kruhu K nebo ne. Pokud ano, vrátí kruh K, jinak se rekurzivně zavolá s množinou M o bod B menší a s B na obvodu.

Kdo se v tomto odstavci ztratil, může se najít v následujícím pseudokódu (O je množina bodů na obvodu):

function nejmensiKruh(M, O) {
    if (|M| == 0 nebo |O| == 3) {
        Vrať kruh spočtený přímo z množiny O
    }
    Bod B = Vezmi náhodný bod z M
    Kruh K = nejmensiKruh(M - B, O)
    if (B neleží v K) {
        Přidej B do O
        Vrať nejmensiKruh(M - B, O)
    }
}

Náhodný výber z množiny, díky němuž už za chvíli získáme průměrnou lineární složitost, zajistíme náhodným seřazením pole. Pak prostě budeme brát poslední prvek.

Tak a nyní k časové složitosti. Prostým pohledem na pseudokód by člověk řekl, že bude O(N3) (pro každý přidaný bod spustíme rekurzivně tu samou funkci s jedním bodem na obvodu navíc), což je také nejhorší možný případ. Jenže nás teď zajímá průměrná časová složitost, k níž nám dopomůže náhodné seřazení bodů.

První rekurzivní volání minimalniKruh(M - B, O) teď budeme tiše ignorovat (ono se totiž provede vždy) a budeme předpokládat, že body postupně přidáváme. Zajímá nás tedy, jaká je pravděpodobnost, že se s novým přidaným bodem B zavolá funkce rekurzivně s B na obvodu navíc. Uvažujme nejmenší kruh K obsahující už bod B. Všimněte si, že rekurzivní volání při přidávání bodu B je podobné zmenšení kruhu K po odebrání bodu B, tedy pravděpodobnost „drahého“ rekurzivního volání je stejná jako pravděpodobnost, že se kruh K po odebrání bodu B zmenší.

Někde vysoko nahoře v tomto textu jsem zmínil, že nejmenší kruh je určen 2 nebo 3 body. Hledaná pravděpodobnost při přidávání i-tého bodu tak vyjde 2/i nebo 3/i (pro jednoduchost budeme dále uvažovat jen 3/i, není težké si rozmyslet, že pro 2/i vše vyjde stejně).

Obrázek 6: kruh se zmenší právě tehdy, když odebereme jeden ze dvou konkrétních bodů.
Obrázek 7: To samé pro 3 body na obvodu, jež tvoří ostroúhlý trojúhelník.

Dále budeme rozebírat časovou složitost podle počtu bodů, jež musí být na obvodu. Pro 3 je to triviálně O(1), takže začněme se 2 body na obvodu. Rekurzivní volání algoritmu už nás stojí pouze O(1) (na obvodu musí být 3 body) a počet bodů na obvodu se nikdy nezmenší, takže N bodů se dvěma danými body na obvodu zvládne algoritmus vždy v O(N).

Zajímavější je situace, je-li dán jen jeden bod na obvodu. Nyní využijeme před chvílí spočtenou pravděpodobnost (zde 2/i a ne 3/i, protože máme jeden bod předem daný na obvodu), a tak můžeme napsat časovou složitost po přidání i-tého bodu takto:

i-2
i
 O(1) +
2
i
 O(i) = O(1)

Pro N bodů s jedním daným na obvodu se časová složitost posčítá na O(N). A co N daných bodů a žádný, který by byl určitě na obvodu? To je přeci naše původní úloha. Znovu využijeme pravděpodobnost, takže na přidání i-tého bodu spotřebujeme:

i-3
i
 O(1) +
3
i
 O(i) = O(1)

Při součtu ještě přidáme počáteční náhodné zamíchání pole bodů:

O(N) + ∑
N
i=1
O(1) = O(N).

Sláva! Tak máme dokázánu i časovou složitost. Paměťová je zjevně vždy lineární.

A poučení do příště? U některých úloh, jestliže si s nimi lámete hlavu už docela dlouho, se vyplatí zeptat se vyhledávače, zdali nezná řešení, jež pak případně přečtete, pochopíte a popíšete vlastními slovy.

Program (C++)

Pavel Veselý

23-1-3 Jedna maticová (Zadání)

K této úloze nám došla spousta řešení, téměř každé fungovalo, ale problém byl ve složitosti. Některá řešení byla příliš pomalá, u jiných byl problém se špatně určenou složitostí. Nezapomínejte, že pro dobré hodnocení je potřeba mít správný a srozumitelný popis vašeho algoritmu a také správnou časovou a prostorovou složitost.

První řešení spočívá v prohledání celé matice řádek po řádku a kontrole každého prvku. Takové řešení samozřejmě funguje, dokonce funguje i pro obecné matice. A to je právě kámen úrazu.

Protože toto řešení nevyužívá vlastností matice, musí se podívat na každý prvek. Jeho složitost je tedy O(n ·m) pro matici velikosti n ×m. To ani zdaleka není to, co bychom chtěli a za co bychom byli ochotni dát celých 11 bodů.

Někteří si uvědomili, že když je posloupnost čísel v řádku ostře rostoucí, dalo by se využít binární vyhledávání. A tak jde zlepšit složitost z O(n ·m) na O(n log m). Ale věřte tomu nebo ne, ani to nám nestačí.

Když nestačí použít na každém řádku binární vyhledávání, co ještě provést? Správné řešení používá binární vyhledávání na hlavní diagonále matice (tak se říká úhlopříčce vedoucí doprava dolů). Před uvedením algoritmu si musíme uvědomit, že platí dvě důležité věci:

Z těchto dvou pozorování plyne, že pokud se podíváme na prvek uprostřed matice, tak mohou nastat tři možnosti. Mohli jsme narazit na správný prvek. To znamená, že můžeme skončit. Nebo je nalezený prvek větší než součet jeho souřadnic, pak můžeme zapomenout pravou dolní čtvrtinu matice, případně je prvek menší a zapomeneme levou horní čtvrtinu matice.

Takže budeme provádět binární vyhledávání na hlavní diagonále, buď najdeme správné řešení, nebo nám nakonec zůstane jen pravá horní a levá dolní čtvrtina matice. Na ty zavoláme rekurzivně stejný algoritmus. Právě tento způsob je použit ve vzorovém kódu.

Toto řešení nám přišlo několikrát, ovšem pouze jednou u něj byla uvedena správná časová složitost. Pojďmě si ji tedy rozebrat detailně. Čas potřebný pro nalezení řešení je definován rekurzivně: T(n2) = 2T(n2/4) + log2 n (pro jednoduchost předpokládáme čtvercovou matici).

Každý správný programátor je hlavně hrozný lenoch, využijeme tedy kuchařkovou metodu pro počítání složitosti rekurzivních algoritmů. Ta se jmenuje Master Theorem a řeší rekurzivní vztahy ve tvaru T(N) = aT(N/b) + f(N), kde a ≥ 1, b>1. Dále tvrdí, že pokud f(N) = O(N logb(a)-ε) pro nějaké ε> 0, tak T(N) = Θ(N logba).

Pro naši rekurenci tohle všechno platí:

a = 2, b=4, log2 n = O(n2 log4 2- ε),

takže výsledná složitost je Θ(n). Prostorová složitost je logaritmická, protože používáme zásobník.

Existuje i jednodušší řešení, které také vede k cíli. Pro něj si stačí uvědomit, že pokud se podíváme na prvek v levém dolním rohu, tak buď jsme našli správné řešení, nebo je větší než součet souřadnic, pak můžeme zahodit celý poslední řádek, nebo je menší než součet souřadnic a můžeme zahodit celý první sloupec. Nakonec se posuneme buď nahoru, nebo doprava, podle toho, čeho jsme se zbavili, a pokračujeme stejně.

Takto se v každém kroku zbavíme buď celého sloupce, nebo řádku. V nejhorším případě tedy provedeme O(n+m) operací. Prostorová složitost je zde konstantní.

Pokud bychom chtěli najít všechny prvky matice, které odpovídají zadání, tak je snadné uvedené dva algoritmy upravit, víme totiž, že pokud najdeme jedno řešení, budou s ním další sousedit, nebo budou v zatím neprozkoumané části matice.

Program (C)

David Marek & Karel Tesař

Vida, to je zvláštní druh algoritmu – rychlejší než lineární ve velikosti vstupu (ta je m×n), protože si ani celý vstup nemusí přečíst. Také vám vrtá hlavou, jestli by nestačilo si ze vstupu přečíst ještě méně? Pojďme dokázat, že nestačilo.

Nejdřív si úlohu převedeme na jinou, ekvivalentní, aby se nám o ní snáze přemýšlelo. Místo zadané matice budeme uvažovat stejně velkou matici Bi,j = Ai,j - i - j. Jelikož A byla v řádcích i sloupcích rostoucí, B bude alespoň neklesající (rozmyslete si, proč). A hledané políčko Ai,j=i+j odpovídá políčku Bi,j=0. Pokud tedy umíme vyřešit původní úlohu, dokážeme vyřešit i tuto, a naopak.

Nyní uvažujme matici B, která bude mít na hlavní diagonále a nad ní hodnoty +1 a pod diagonálou samé -1. To je neklesající matice, v níž žádné nulové políčko neexistuje. Kdykoliv ale změníme některou z +1 na diagonále na 0, matice bude pořád neklesající, ale řešení v ní už bude existovat:

( +1+1+1+1+1)
-1+1+1+1+1
-1-1+1+1+1
-1-1-1 0+1
-1-1-1-1+1

Pokud tedy libovolný algoritmus řešící úlohu spustíme na naši matici B, musí přečíst alespoň všechna políčka na diagonále, aby si ověřil, že v matici žádné nulové políčko není.

Martin M. Mareš

23-1-4 Ale co trapné numerické chyby? (Zadání)

Na této úloze nebylo mnoho těžkého, a tak spousta řešitelů dostala zasloužených 10 bodů. Blahopřejeme, příště už to tak snadné nebude!

Přejděme k úloze samotné. Periodu racionálního čísla nelze poznat jen tak, že se v desetinném zápisu opakuje řetězec (začátek 0.88 neznamená periodu 8, například u 15/17). Když dělíme čitatel a jmenovatel na papíře, poznáme periodu tak, že se „zacyklíme“ – dělíme už jednou to samé číslo, ten samý zbytek. Tak proč to tak neimplementovat? Zbytky po dělení jmenovatele nám budou sloužit jako odkazy do pole, uvnitř pole si zapamatujeme první výskyt odkazovaného zbytku – abychom věděli, kde zapsat závorku. Hotovo!

Poznamenejme, že paměťová složitost je O(N), kde N je velikost jmenovatele, tedy počet možných zbytků, a časová je lineární vůči velikosti výstupu. (V některých případech je pro dokázání optimality užitečnější měřit časovou složitost nikoli podle vstupu, ale podle velikosti výstupu. Nakonec, i kdybychom uměli dělit rychleji než na papíře, stejně musíme výstup vypsat.)

Program (C)

Martin Böhm & CodEx

23-1-5 Adina knihovna (Zadání)

Očíslujme si N knih po řadě zleva doprava 1 až N. Podívejme se na knihu s číslem 1, která je jistě na kraji. Lze ji přesunout na jediné místo, a to na pozici 1+K. Dalším pohledem zjistíme, že knihu z pozice 1+K musíme přesunout na pozici 1, protože jinou tam dát nesmíme.

Podívejme se na knihu s číslem č ≤ K. Lze ji přesunout na jediné místo, a to na pozici č + K, odkud přesuneme knihu na pozici č.

Tedy prvních 2K knih povyměňujeme mezi sebou a zbyde nám N-2K knih, na které můžu použít stejný argument. Tohle opakujeme i kroků, až nám zbyde 0 ≤ N-2iK < 2K. Buďto platí, že N-2iK = 0, pak jsme hotovi (a tedy platí, že 2K dělí N, protože N/2K = i ∈N). Nebo máme nenulový zbytek, ale v tom jistě umíme najít knihu, kterou neumíme přesunout ani vlevo, ani vpravo (třeba tu úplně uprostřed), tedy knihovnu s takovým K nelze přeskládat.

Zbývá tedy první varianta, a tedy bereme pouze taková K, která dělí N/2 (pro lichá N úloha nemá řešení). Zjevně je jen jeden způsob, jak knihy přeskládat, což byla druhá věc, na kterou se zadání ptalo.

Někteří řešitelé ještě uvažovali triviální případ, kdy K=0, to funguje pro všechna N (i lichá). Někdo také řešil možnost K < 0. To bylo možné, i když jsme to nijak extra nehodnotili.

Jan „Moskyto“ Matějka & Pali Rohár

23-1-6 Babbageova cesta (Zadání)

Píšeme-li v zadání „Pro jednoduchost předpokládejme, že použití takového spojení trvá jednotkový čas.“, můžeme tím myslet různé věci. Takové omezení zjednodušuje popisování zadání, zjednodušuje načítání vstupu…

Může se stát, že bychom zjednodušovali práci procesoru, že by asymptotická časová složitost řešení s takto omezeným zadáním byla nižší, než složitost řešení, kde by použití spojení zabralo zadaně vteřin?

Je to tak a většinu z vás jsme na to nachytali. Použití Dijkstrova algoritmu je v daném případě triviálně možné: stačí měřit vzdálenost v uspořádané dvojici (počet použitých hran, součet cen na použitých hranách), kde při porovnávání klademe důraz na druhé složky pouze v případě rovnosti prvních složek.

Do časové složitosti takového řešení se však nevyhnutelně vloudí logaritmy, které tam zaneslo použití haldy coby rozumné implementace prioritní fronty, kterou Dijkstrův algoritmus prostě potřebuje.

Poodstoupíme o krok zpátky: dokud jsme nevěděli, co to Dijkstrův algoritmus je, uměli jsme měřit nejkratší cesty pouze co se počtu hran týče, a to prohledáváním do šířky.

To nám přirozeně rozdělí vrcholy do vrstev podle vzdálenosti od vrcholu, ze kterého jsme prohledávat začali, stačí si k vrcholu tuto vzdálenost připsat (výchozímu vrcholu nastavit nulu) a při vkládání nezpracovaných vrcholů do fronty jim ji přidělovat o jednotku zvýšenou.

Naše úloha je složitější o to, že druhotné kritérium v zadání mluví o ohodnocení hran. S tím se ale vyrovnáme snadno lehkou úpravou prohledávání do šířky: kdykoliv dostaneme z fronty vrchol v s přiřazenou hranovou vzdáleností n, rozhlédneme se po sousedních vrcholech (tj. těch, se kterými v spojuje hrana), vybereme jen ty, které jsou ve vrstvě vzdálené n-1 (od výchozího bodu), a vrcholu v nastavíme coby minimální cenu minimum ze součtu cen vrcholů z této vrstvy a příslušných cen přepravy (ohodnocení hran) z těchto vrcholů do našeho v. A samozřejmě, abychom mohli posléze zrekonstruovat cestu, si uložíme, který že to vrchol z vrstvy vzdálené n-1 byl pro náš v takto výhodný.

Bude to fungovat? Do daného vrcholu prostě musíme přijít z vrcholu v nejvýše vrstvě vzdálené n-1, chceme-li dodržovat hranovou vzdálenost coby úhlavní kritérium – a z vrstvy s menším pořadovým číslem nám do vrcholu ve vrstvě n samozřejmě žádná hrana vést nemůže. Pokud tedy věříme, že máme ceny v nižších vrstvách spočítány správně, budeme je mít dobře i ve spočítaném vrcholu. No a protože cena v počátečním vrcholu je dobře (0), roznese nám matematická indukce tuto správnost po všech vrcholech v grafu.

Samozřejmě nepotřebujeme všechny cesty, ale to už je ta potíž s algoritmy pro hledání nejkratší cesty z bodu A do bodu B, že toho většinou musí mimoděk spočítat o hodně víc. Časová složitost našeho řešení je každopádně O(n+m) a paměťová stejně tak.

Program (C)

Lukáš Lánský

23-1-7 Regulární výrazy (Zadání)

Sešlo se nám přes 30 řešení různé kvality a přístupu. Bylo nelehkým úkolem je opravit a alespoň pseudospravedlivě obodovat, takže pokud vám bude připadat, že jsme zrovna k vám byli nespravedliví, tak se ozvěte e-mailem opravujícím, nebo třeba na fóru. Prostoru pro dotazy je dost, ty nejvíce očekávané se zde pokusíme zodpovědět rovnou.

Autorským řešením úkolu 1 byl výraz ((b?a)*b)? – ten přijímá opravdu stejné řetězce jako zadaný b?(a+b)* – za každým b musí nutně následovat alespoň jedno a, pokud tedy není na konci řetězce. Musí vyhovovat i prázdný řetězec, což bylo často opomínáno.

Řešení spočívající v náhradě a+ za aa* nebo b? za b{0,1} jsme hodnotili stylově desetinou bodu. On je to totiž vlastně stejný výraz.

V řešení úkolu 2 jste se mohli odvážit dál. Mnoho z vás zůstalo u výrazu (a+|b+)*, který šlo po krátkém rozmyslu zredukovat na [ab]*, což je také autorské řešení.

Úkol 3 byl poněkud šílený. Na něm jste si mohli vyzkoušet tvorbu rozsáhlých regexů, na kterých je poznat každá nesystematičnost, každá výjimka. Zde jsme strhávali body i za používání (0|2|4|6|8) místo [02468]. Ono to má stejný význam, akorát to první se čte výrazně hůř.

Mnoho řešitelů jednoduše vypsalo všechna koncová trojčíslí dělitelná 8. To je sice hezké, ale pomalé. Každý znak navíc je zpomalení. Porovnejte s autorským řešením (mezery a konce řádků ignorujte):

(0|-?(8|[48][08]|[159]6|[26]4|[37]2|
[2468]([048][08]|[159]6|[26]4|[37]2)|
([1-9][0-9]*)?[13579]
	([048]4|[159]2|[26][08]|[37]6)|
[1-9][0-9]*[02468]
	([048][08]|[159]6|[26]4|[37]2)))

Nelíbila se nám čísla, která začínala řadou nul, stejně tak drobné chyby jako neuvažování nuly nebo záporných čísel, nicméně jsme za ně strhávali výrazně méně než za false positives nebo false negatives.

Následovalo cvičení z exaktního vyjadřování. V úkolu 4 bylo za úkol popsat, co danému výrazu vyhovuje. Obyčejný popis stylu „sudý počet nul, pak nula, nebo jednička, a potom sudý počet jedniček“ vyfasoval bod.

Nápaditější řešitelé, kteří napsali „sudý počet nul, pak lichý počet jedniček, nebo lichý počet nul a pak sudý počet jedniček“, získali body dva.

Hodí se zmínit, že nula je také sudé číslo. Mnoho z vás si to neuvědomilo a řešili nulu zvlášť.

Nakonec trochu přiblížení reality. Úkol 5 vyžadoval opravu zadaného výrazu, což je nejčastější problém, se kterým se při práci s regexy setkáte. Zadanému regexu měly vyhovovat právě ty řetězce, ve kterých je sudý počet jedniček, sudý počet nul a nic jiného.

Zadaný výraz byl dost mimo. Jedna z možností, jak ho opravit, spočívala ve zhruba dvojnásobném natažení výrazu, neboť kromě bloku 0(00|11)*1(00|11)* bylo potřeba ještě zahrnout blok 1(00|11)*0(00|11)*. Lepší variantou bylo zadaný výraz zahodit a vymyslet úplně nový.

Má-li řetězec sestávat ze sudého počtu nul a sudého počtu jedniček, pak musí mít také celkem sudý počet znaků, tedy nám rozhodně nebude vadit, že jej budeme kontrolovat po dvojicích.

Prázdný řetězec rozhodně vyhovuje. Pokud nyní přečteme dvojici (00|11), bude rozhodně vyhovovat taky. Naopak kdybychom měli řetězec, který nevyhovuje, tak po přečtení dvojice (00|11) vyhovovat také nebude. Tedy nás nezajímá, kdy, kde a v kolika exemplářích se nějaká tato dvojice objeví.

Přesně obráceně to platí pro dvojici (01|10). Ta vždy přepne mezi vyhovujícím a nevyhovujícím řetězcem. Té tedy potřebujeme sudý počet. Po poskládání všech požadavků máme výraz (00|11)*(((01|10)(00|11)*){2})*

První část spolkne začátek sestávající z (00|11)*, další část vždycky přejde do stavu „nevyhovující řetězec“, spolkne (00|11)*, přejde do stavu „vyhovující řetězec“ a zase spolkne (00|11)*. Jednoduché a účinné.

Jozef Gandžala & Jan „Moskyto“ Matějka