Druhá série dvacátého sedmého ročníku KSP

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

Řešení úloh

Teoretická úloha27-2-1 Systém Patriot (Zadání)

Toto je úloha, která má více než jedno správné řešení. Předvedeme si to, které vymyslela většina řešitelů. Jiná řešení však nemusí být špatně.

Střely si nastrkáme do dvou hald, A a B. Halda A bude maximová (na vrcholu sedí maximum), B minimová. Dále, všechny prvky v A budou nejvýše tak velké, jako libovolný prvek B (tedy formálněji, ∀a∈A, b∈B; a ≤ b). A počty prvků v haldách se budou lišit maximálně o 1.

K čemu nám takové komplikované podmínky budou? Celkem jednoduše nahlédneme, že medián se nachází na vrcholu jedné z hald a z velikostí hald lze vždy určit, na vrcholu které.

Nyní si rozmyslíme, jak s touto datovou strukturou pracovat. Když chceme střelu přidat, porovnáme ji s aktuálním mediánem a určíme, do které haldy ji přidáme (pokud je větší než medián, jde do B, pokud menší, tak do A, u stejných prvků je to jedno). Poté zjistíme, jestli nám tato halda příliš nevyrostla. Pokud by byla o 2 prvky větší, tak její vrchol přestěhujeme do druhé haldy, aby se to vyrovnalo.

Jak vystřelit střelu? Medián najít umíme, takže jej stačí odebrat a poté opět zkontrolovat, že haldy mají dostatečně podobnou velikost.

V každé operaci provádíme konstantně mnoho operací vložení a odebrání z hald, tedy jedna operace nám zabere O(log n) – takovou složitost má operace s haldou. Paměť nám bude stačit lineární, opět proto, že halda potřebuje lineární množství paměti s množstvím prvků v ní uložených.

Chceme ještě nahlédnout, že to opravdu funguje. Protože nalevo i napravo od hranice mezi haldami je stejné množství prvků a na vrcholu je ten prvek „k hranici“, opravdu je medián jedním z vrcholů. Nakonec si všimneme, že pravidla z druhého odstavce neporušíme ani jednou operací, a tedy medián neztratíme.

Program (C)

Michal „vorner“ Vaner

Teoretická úloha27-2-2 Prohledávání budov (Zadání)

Než pošleme záchranné týmy prodírat se hromadami trosek v budovách, nejprve učiníme několik pozorování.

Tím prvním je, že nám nezáleží na pořadí budov. Můžeme si je přeuspořádat, jak chceme, a stejně to na počtu nutných týmů nic nezmění. Pro jednoduchost si tedy budovy seřadíme podle velikosti od nejmenší po největší.

Druhým důležitým pozorováním je to, že budovy začínají všechny u země. Na tom není asi nic objevného, ale díky tomu platí, že u země jsou patra budov zastoupena nejhustěji a směrem nahoru jich jen ubývá (jak jednotlivé budovy postupně končí).

Pokud tedy chceme nějaká patra prohledat horizontálně, tak to určitě bude nějaký úsek pater začínajících u země a končící v nějakém patře K. Budovy přesahující nad toto patro pak prohledáme vertikálně. Kdyby v nějakém optimálním řešení netvořila horizontálně prohledávaná patra souvislý úsek od země, tak takové řešení můžeme bez jakéhokoliv zhoršení převést na stav se souvislým úsekem.

Našemu řešení tedy stačí jen najít toto číslo K. Všech N budov určitě umíme prohledat pomocí N týmů (do každé budovy jeden vertikálně), takže začneme s K=0 a budeme ho zkoušet zvedat. Jako V si označíme počet vertikálně prohledávaných budov (na počátku tedy V=N).

Budeme naší hranicí postupně skákat budovu po budově nahoru a budeme si pamatovat, kdy byl počet týmů (V+K) nejmenší. Vždy, když odebereme budovu, snížíme V o jedna a zvedneme K na výšku této budovy.

Hlavní část řešení zvládneme v lineárním čase vůči velikosti vstupu, ale kvůli úvodnímu třídění máme časovou složitost bohužel O(N log N). Neumíme to ještě zrychlit?

Stačí si přidat další pozorování: Budovy vyšší než N určitě prohledáme vertikálně, protože K nikdy nemá smysl zvedat nad N. Můžeme si tedy tyto budovy na začátku v lineárním čase vyřadit a uvažovat jen budovy nižší než N. A ty již umíme setřídit přihrádkovým tříděním v lineárním čase. Dostali jsme se tedy k paměťové i časové složitosti O(N).

Program (Python 3)

Jirka Setnička

Praktická CodExová úloha27-2-3 Průjezd jeřábu (Zadání)

Tato CodExovka se ukázala býti těžší než předchozí (soudě dle vámi získaných bodů). Nicméně podobně jako předchozí CodExovka, tak i tato má celkem jednoduché řešení. Ukážeme si dva možné přístupy.

Spojování komponent

Budeme si sestavovat mapu oblastí, mezi kterými křižovatkami se můžeme s jak vysokým jeřábem pohybovat. Přidání do mapy ještě nepoužité silnice, po které se dá jet s nejvyšším jeřábem, nemůže nic pokazit. Principem prvního řešení je toto pravidlo opakovaně použít na zbylé silnice, dokud nespojíme základnu se skladištěm.

Na začátku představuje každá křižovatka osamocenou komponentu, žádné silnice jsme zatím ještě nepoužili. Všechny silnice si na začátku setřídíme a poté je po jedné odebíráme a propojujeme dvě komponenty, které spojuje tato silnice. Pokračujeme, dokud nezískáme komponentu, ve které se nachází jak základna, tak sklad. Pak vypíšeme, že nejvyšší jeřáb může mít výšku odpovídající hodnotě na poslední přidávané silnici. Pak pro nalezení cesty stačí projít ze základny tu jednu komponentu do hloubky, dokud nenarazíme na sklad.

Řešení má tedy časovou složitost O(M log M), protože tak dlouho nám trvá setřídit všechny silnice, kterých je M. A pokud použijeme chytře implementovanou datovou strukturu, která umí rychle najít, zda dva vrcholy jsou v jedné komponentě, tak si tím časovou složitost nezhoršíme, protože celkem všechny testy a spojení zaberou O(M log N).

Pro podrobnosti se podívejte na datovou strukturu Disjoint-Find-Union (DFU), popsanou v kuchařce druhé série. Projití do hloubky nám zabere času nejvýše O(N + M), tedy opravdu celková časová složitost je O(M log M). Paměťová složitost je O(N + M), protože máme uložený celý vstup a DFU přidá ke každé silnici jen konstantně mnoho informací.

Program (C++) – Disjoint-Find-Union

Inspirace Dijkstrovým algoritmem

Jistě si říkáte, že předchozí řešení asi nebude nejlepší, protože se nám může mnohokrát stát, že spojujeme křižovatky, které nakonec stejně nebudou v té komponentě, kde je základna a sklad. A máte pravdu, lze udělat o trošku lepší řešení.

Začneme silnice procházet do šířky ze základny. Přitom budeme rozšiřovat oblast, do které se umíme dostat. Vždy použijeme silnici vedoucí z prozkoumané oblasti někam dál, po které může jet nejvyšší jeřáb, což je v podstatě princip Dijkstrova algoritmu. Předchozí krok opakujeme až do chvíle, kdy se dostaneme do skladu, nebo nám dojdou silnice. Pak stačí zrekonstruovat cestu, po kterých silnicích jsme šli, protože víme, že lepší cesta nemůže existovat. Důkaz platnosti tohoto pozorování necháváme na rozmyšlení si čtenářům.

Pro každou křižovatku si tak budeme pamatovat hodnotu, kterou si označíme value. Bude představovat to, jakým nejvyšším jeřábem jsme schopní dojet na tuto křižovatku. U každé silnice víme, jaký nejvyšší jeřáb jí může projet. Tuto hodnotu si označíme jako h. A nakonec v lastValue bude value křižovatky, ze které jsme přijeli.

Pak při každém použití některé silnice nastavíme na křižovatku, do které dojedeme, hodnoty takto:

value = max(value, min(h, lastValue))

Abychom zbytečně nemuseli zjišťovat, jestli jsme někdy na dané křižovatce již byli, tak na začátku všechny křižovatky mají value = 0, jen křižovatka základny (start) má nastaveno value = ∞ (v programu nějaké dostatečně vysoké číslo).

Toto řešení má časovou složitost O(M log N), pokud aktualizujeme hodnoty v haldě. Pokud pouze vkládáme, tak je časová složitost O(M log M), což je až O(M log N2) = O(2 · M log N). Tedy na soutěžích je asi rozumné nezdržovat se programováním aktualizování hodnot v haldě, protože je to asi nejsložitější operace, navíc musíte vědět, kde se který vrchol v haldě nachází. V praxi je dobré aktualizování implementovat, protože budeme mít zhruba dvakrát rychlejší algoritmus a navíc zabereme méně paměti. Asymptoticky si ale nepomůžeme, protože musíme mít uložený celý vstup. To vede na paměťovou složitost O(N + M).

Program (C) – Dijkstra s aktualizovanou haldou

Vojta Sejkora

Teoretická úloha27-2-4 Stahování map (Zadání)

Lehčí varianta

Nejprve se zastavme u lehčí varianty úlohy, kde máme jenom N=3 mapy o rozměrech R×S, kde R,S ≤ 20, a číslo W, které udává režii přenosu mapy diferencí.

Pojmenujme si mapy A, B a C. Vytvoříme si z nich vrcholy grafu. Natáhneme mezi nimi hrany, pokud DABW < RS, kde DAB je počet rozdílných políček mezi mapami A a B. Všimněme si, že DAB=DBA, hrany jsou tedy neorientované.

Hrana mezi A a B znamená, že přenést mapu B diferencí od A se vyplatí, protože to bude stát méně, než kdybychom mapu B přenášeli samostatně. Hranám přidáme ohodnocení, to bude právě DABW.

Kolik hran v grafu teď můžeme mít?

Toto by k vyřešení lehčí varianty úplně stačilo. Podívejme se ale na graf ještě trochu jinak. Představme si, že máme čtyři vrcholy, mapy A, B, C a server. Ze serveru vede do každé mapy hrana o váze RS, všechny ostatní hrany mají váhu danou počtem rozdílných políček krát W.

Z tohoto grafu potřebujeme vybrat tři hrany, protože celkem budeme provádět tři přenosy. Vybírat ale nesmíme úplně libovolně. Každý vrchol musí být připojen nějakou hranou k ostatním, protože kdyby nebyl, zůstane nějaká mapa nestažená nebo stáhneme všechny diferencí, ale nic ze serveru jako první.

Vrcholy jsou čtyři, hrany jsou tři, výsledný podgraf musí být souvislý a neobsahovat cyklus, to znamená, že to bude strom. Navíc hledáme nejlehčí strom, takový, který má součet hran nejmenší možný. Takovýto strom se nazývá minimální kostra.

Generické řešení

A je to. Máme řešení i pro plnou variantu úlohy, kde je map více než tři, ale ne víc než 500. Vytvoříme si z map a serveru graf, ohodnotíme hrany diferencí map krát W. (Tu spočítáme snadno, projdeme mapy políčko po políčku a spočítáme si počet těch rozdílných.) V tomto grafu nalezneme minimální kostru algoritmem z kuchařky. Ne nadarmo v ní byly zmíněny tři. Vyberme si třeba Kruskalův algoritmus.

(Mimochodem, když neřekneme přesně, který algoritmus na minimální kostru se má použít, bude naše řešení generické. Ten, kdo ho bude programovat, si musí sám nějaký vybrat a dosadit.)

Pořadí stahování map pak snadno vypíšeme procházením stromu od serveru do šířky nebo do hloubky v čase O(N).

Z toho vyplývá časová složitost, ta je O(N2(RS+ log N)), protože O(N2RS) trvá postavení grafu a O(M log N) zabere Kruskalův algoritmus (M je počet hran, v našem případě N2).

Paměťová složitost je O(N2+NRS), potřebujeme si pamatovat celý vstup a všechny hodnoty diferencí.

Jelikož jste mohli předpokládat, že N ≤ 500 a R,S ≤ 20, je toto řešení dostatečně rychlé na to, aby mohlo být v praxi použitelné. Většina z vás se u něčeho takového tedy zastavila a neměli jste motivaci přemýšlet nad ještě rychlejším řešením. Proto jste i za toto mohli získat plný počet bodů.

Někteří z vás si všimli, že existuje vlastně jen RS možných ohodnocení hran, počet rozdílných políček ve dvou mapách může být jedině mezi 0 a RS. To znamená, že je můžeme setřídit přihrádkově, v čase lineárním s jejich počtem, tedy v O(N2).

Kruskalův algoritmus s využitím DFU (s union by rank a s path compression) pak vytvoří minimální kostru v čase O(Mα(N)), což je v našem případě O(N2α(N)), kde α je inverzní Ackermannova funkce (její definici najdete v kuchařce, zde stačí, že roste extrémně pomalu).

Když sečteme vytváření grafu, třídění a vytváření minimální kostry, vyjde nám časová složitost O(N2(RS+α(N)).

S naším omezením je RS≤ 400 a α(N)≤ α(500)≤ 4. Můžeme tedy v klidu říct, že celková složitost je zhruba O(N2RS). Paměťová zůstává.

Program – Kruskalův algoritmus (Python 3)

Zlepšení o slepičí krok

Tím se ale nespokojíme, existuje pěkné řešení, které je asi tak o slepičí krok lepší, není „téměř“ lineární, ale „úplně“ lineární s velikostí grafu. Použijeme upravený Jarníkův algoritmus.

Ten staví kostru postupně od jednoho vrcholu a vždy k ní přidává tu nejlehčí hranu, která vede z kostry do zbytku grafu. K tomu používá nějakou datovou strukturu Q, která je vlastně množinou vrcholů schopnou vydat minimum. Ještě si připravíme dvě pole t a d indexované vrcholy; d udává nejkratší hranu z kostry do vrcholu, v t bude na konci algoritmu minimální kostra zadaná jako postup přilepování hran stromu od kořene.

Na začátku si do Q vložíme všechny vrcholy, d bude pro každý vrchol kromě startovního nekonečno, pro startovní vrchol 0, t nechť je pro každý vrchol NULL, neexistující vrchol. Tato hodnota nakonec zbude jen u startovního vrcholu.

Potom se provedou následující kroky:

  1. dokud Q ≠ ∅:
  2. u ← vyjmi minimum z Q podle d
  3. pro každého souseda v vrcholu u dělej:
  4. pokud v ∈Q a d(v) > w(u,v):
  5. d(v) ←w(u,v); t(v) ←u

    Výstup: t

Co bude datová struktura Q? Podobnou jistě znáte z Dijkstrova algoritmu, tam se používá halda. My ale využijeme toho, že hrany mají jen RS různých hodnot, a tak použijeme pole. Indexovat ho budeme od 0 do RS. Výběr minima bude trvat O(RS), pole budeme procházet od začátku do konce a v nejhorším případě najdeme první vrchol až na konci. Každý vrchol má O(N) sousedů, pro každého se bude provádět změna hodnoty, ta trvá pro každého ale jen O(1), vrchol se pouze přemístí na jiný index.

Časová složitost tedy bude O(N2RS). Kolikrát budeme potřebovat znát váhu hrany? Jen jednou. Nemusíme si ji tedy nikam ukládat, ale spočítáme si ji ve chvíli, kdy ji poprvé využijeme. Díky tomu nám stačí pouze lineární paměť k velikosti vstupu, O(N · RS).

Zbývá si už jen domyslet pár implementačních detailů. K tomu vám může pomoci zdroják:

Program – Jarníkův algoritmus (Python 3)

Dominik Macháček

Praktická opendata úloha27-2-5 Nejdelší příkaz (Zadání)

Úlohu si nejdříve zanalyzujeme. Potřebujeme v zadaných slovech najít co nejdelší žebřík, tj. posloupnost slov, kde každé další vznikne vložením právě jednoho písmene do slova předešlého. Pokud se na žebřík podíváme z druhé strany, hledáme posloupnost slov, kde každé další vznikne vyškrtnutím právě jednoho písmene.

Pro jedno konkrétní slovo můžeme zkusit všechny možnosti vyškrtnutí a kontrolovat, zda nově vzniklé slovo máme na seznamu. Pokud ano, vyzkoušíme pro něj to samé rekurzivně. Výše popsaný proces zkusíme začít v každém slově a tam, kde se dostaneme v rekurzi nejhlouběji, je naše řešení.

Pro dokončení popisu řešení ještě potřebujeme najít vhodnou datovou strukturu pro uchovávání slov a jejich hledání. Takovou je třeba trie. Pokud jste o ní ještě neslyšeli, můžete se o ní dočíst v naší kuchařce o hledání v textu.

Tím dostáváme funkční řešení. Kvůli rekurzi ale bohužel ne dost dobré. Můžeme si všimnout, že při výpočtu můžeme zbytečně spouštět výpočet vícekrát pro stejné slovo. Tomu se budeme snažit vyvarovat a výpočet pro jedno slovo vždy spouštět pouze jednou (použijeme myšlenku dynamického programování).

Trii budeme stavět od nejkratších slov po nejdelší a v koncovém vrcholu slova si budeme pamatovat délku nejdelšího žebříku pro dané slovo nebo nulu, pokud ve vrcholu trie žádné slovo nekončí.

Při přidávání slova do trie tedy nejdřív zkusíme najít všechny možné předchůdce v dosavadní trii, z nich vybereme toho s nejvyšší hodnotou žebříku a aktuální slovo přidáme s hodnotou o jedna větší. Na konci pak jen najdeme největší hodnotu v trii a je to! Z toho pak jednoduše získáme výsledný žebřík.

Časová složitost je O(NL · (složitost trie)), což je pro konstantní abecedu O(NL2), kde N je počet slov na vstupu a L je délka nejdelšího z nich. Pro každé slovo provádíme O(L) dotazů na trii, kde každý má složitost O(L).

Pro více detailů můžete nahlédnout do vzorové implementace v jazyce C++.

Program (C++)

Karel Tesař

Teoretická úloha27-2-6 Testování odezvy (Zadání)

Na vstupu máme matici A o rozměrech N×N a chceme určit, jestli to může být matice vzdáleností v ohodnoceném stromě, a najít takový strom T. Z příkladu je jasné, že nám jde o neorientovaný graf (matice je symetrická, tedy Aij = Aji) bez smyček (na diagonále jsou nuly: Aii = 0).

Pokud strom existuje, ve vstupní matici je spousta hodnot, které odpovídají cestám s více hranami. My ale potřebujeme vědět, které hodnoty odpovídají jednotlivým hranám. Kdybychom to věděli, strom už si ze seznamu hran snadno převedeme do příjemnější reprezentace a stejně snadno ověříme, že A je jeho matice vzdáleností.

Při ověřování můžeme využít toho, že cesta mezi každými dvěma vrcholy je ve stromu určena jednoznačně, takže vzdálenost všech vrcholů od jednoho pevně zvoleného jde snadno spočítat během průchodu (třeba DFS). Postupně tedy spustíme průchod z každého vrcholu stromu T a ověříme, že ve vstupní matici A jsou správné hodnoty. Strom by měl mít N vrcholů a N-1 hran (udělejte si cvičení z grafové kuchařky a dokažte to!), takže všech N průchodů by dohromady trvalo O(N2). To je lineární s velikostí kontrolované matice, kterou je potřeba projít celou, takže jsme na optimu.

Dobře, dobře, kontrolu matice vzdáleností pro daný strom jsme vymysleli, kde ale ten strom sebrat?

V lehčí variantě úlohy měl být strom T neohodnocený, lépe řečeno ohodnocený jedničkami. Stačilo tedy vzít všechny jedničkové hrany a ověřit, že tvoří strom. Žádná jedničková hrana nemůže odpovídat cestě s více než jednou hranou, protože by pak musela mít ohodnocení alespoň 2, takže jsme do T nepřidali žádnou hranu, která tam být neměla. Ze zadání a výběru hran plyne, že tam ani žádná nechybí. Ještě by se nám ale mohlo stát, že jsme dostali něco, co vůbec není strom. To můžeme zkontrolovat více způsoby, podle použité charakterizace stromů.

Strom je souvislý graf bez kružnic. Pokud prohledáním grafu (třeba DFS) najdeme všechny vrcholy, je souvislý. Kružnici detekujeme, pokud najdeme zpětnou hranu ve stromě průchodu do hloubky. (Pokud nevíte, o čem je řeč, osvěžte si paměť pohledem do již zmiňované grafové kuchařky.) Alternativně můžeme testovat, že má strom T správný počet vrcholů i hran. Oba tyto algoritmy běží v čase i prostoru O(N). Ostatní charakterizace stromů nejsou pro testování vhodné. Mimochodem, tahle část našeho algoritmu je shodná s úlohou 27-Z2-5.

V lehčí variantě tedy máme snadný tip na strom T a ověříme, že to opravdu strom je a že vzdálenosti v něm odpovídají vstupní matici A. Načíst vstup zvládneme v čase i prostoru O(N2), najít všech N-1 jedničkových hran a postavit z nich rozumně reprezentovaný strom taktéž, průchod stromem pro ověření souvislosti zabere dokonce jen čas O(N) a konečnou kontrolu matice vzdáleností jsme už spočítali na O(N2). Celkově se tedy vejdeme do času O(N2), což je lineární s velikostí vstupu, tedy zaručeně optimální. V paměti bude nejvíc místa zabírat matice A, zbytek se v tom ztratí, takže i paměťové nároky budeme mít lineární.

V těžší variantě se musíme zamyslet o trochu víc. Možná nás napadne se na matici A koukat jako na matici sousednosti úplného grafu K, kde strom T hledáme jako podgraf. Hm, a T musí mít stejný počet vrcholů jako K… takže je jeho kostrou! Nebude to minimální kostra, když už je popsaná v kuchařce k této sérii?

Úplný graf je souvislý, takže vždycky nějakou kostru má, speciálně tedy i minimální kostru T. Dokažme, že pokud má úloha řešení, je jím minimální kostra. Pro spor předpokládejme, že existuje řešení S a není to minimální kostra T. Vezmeme nejlehčí hranu uv z T, která není v S, a podíváme se na běh Kruskalova algoritmu, který v každém kroku spojí dvě komponenty souvislosti nejlehčí hranou mezi nimi.

V řešení S jsou vrcholy u a v spojené cestou S[u, v].

A máme dokázáno. Nebo ne? Celou dobu uvažujeme jen kladné váhy hran. Jestli jste předpokládali na vstupu matici sousednosti kladně ohodnoceného úplného grafu automaticky, nic se neděje, za to jsme body nestrhávali. Úloha byla zamýšlená s kladným ohodnocením a příklad tomu nasvědčoval. Přesto bychom rádi v rychlosti zmínili také rozšířenou variantu i se zápornými nebo nulovými vahami, která některé z vás napadla.

Minimální kostru pro libovolné celočíselné váhy hran zvládnou všechny standardní algoritmy, dokonce bez modifikace. Přinejhorším bychom mohli nezáporné váhy získat odečtením váhy nejzápornější hrany w- od váhy každé hrany. Tím bychom každou kostru ztížili o (N-1) · w-, takže bychom uspořádání koster podle váhy nezměnili.

Potíž je v tom, že se zápornými vahami minimální kostra neřeší naši úlohu. Představte si třeba trojúhelník s hranami 1, 2, -1, obsahující cestu 2, -1. Pro úlohu se zápornými hranami neznáme efektivní řešení. Ale ani nemáme důkaz její NP-těžkosti, takže kdybyste na jedno nebo druhé přišli, dejte nám vědět na fóru. :-)

Nulové hrany umíme bez újmy na obecnosti spravit kontrakcí na začátku a dekontrakcí na konci algoritmu. V podstatě tak uvedeme v realitu, co nulová hrana neformálně říká: že její krajní vrcholy jsou vlastně vrchol jeden. Kontrakce hrany uv se projeví vyhozením řádku v a sloupce v z matice A. Přitom kontrolujeme, že se shodují s řádkem u a sloupcem u, jinak strom neexistuje. Tato úprava se hodí jen pro účely analýzy, algoritmus poběží správně i bez ní (zdůvodnění si rozmyslete).

Celý algoritmus v pseudokódu:

  1. Načti matici A a zkontroluj, že je symetrická, má nuly na diagonále a jinak obsahuje jen kladné hodnoty. Pokud kontrola neuspěje, vrať „strom neexistuje“.
  2. Najdi minimální kostru T úplného grafu s maticí sousednosti A.
  3. Ověř, že získaná kostra T má matici vzdáleností rovnou matici A. Pokud se matice liší, vrať „strom neexistuje“.
  4. Vrať strom T.

Zbývá vybrat algoritmus pro nalezení minimální kostry. Vymýšlet vlastní nemá smysl, jen bychom znovu vynalézali kolo a mořili se s důkazem korektnosti a složitosti.

Kruskalův algoritmus máme rozebraný v kuchařce, nejdéle na něm trvá třídění hran v čase O(M log M) = O(M log N), což by pro nás bylo O(N2 log N). Hodí se pro řídké grafy a kvůli snadné implementaci, když zrovna nemáte po ruce haldu.

Pro husté grafy, kterým úplný graf bezesporu je, ale je vhodnější Jarníkův algoritmus. S Fibonacciho haldou běží v čase O(M + N log N), což by pro náš případ bylo O(N2 + N log N) = O(N2).

Kniha The Algorithm Design Manual od Stevena S. Skieny tvrdí, že Jarník s párovacími haldami je nejrychlejším praktickým řešením pro řídké i husté grafy, se stejnou asymptotickou složitostí jako s Fibonacciho haldou. Nás z knihy bude zajímat implementace Jarníka, která běží vždycky v O(N2) a ani nepotřebuje žádnou složitou datovou strukturu. V češtině ji najdete popsanou v Medvědových poznámkách z ADS.

Tato varianta Jarníka je k vidění ve vzorovém řešení. Nalezení kostry je nejtěžší částí algoritmu, tedy i těžší varianta úlohy má řešení v lineárním čase i prostoru.

Program (C)

Tomáš „Palec“ Maleček

Seriálová úloha27-2-7 Shellové skripty (Zadání)

Snad každý, kdo se do úloh pustil, vyřešil všechny – to nás těší. Řešení obsahovala většinou jen drobné nedostatky, hlavně u vypisování proměnných. Když vypisujete obsah proměnné, který může obsahovat mezery, je potřeba ji vypsat v uvozovkách, jinak se mezery ztratí během rozdělování na slova.

echo "$prom"

Teď už k řešení samotných úloh. První byla velmi jednoduchá, stačilo se podívat do manuálu k příkazu test. Častou chybou nicméně bylo, že jste se snažili testovat na neprázdnost i adresáře. Taky se často v řešení vyskyla konstrukce:

for f in $(ls)
To není špatně (ani jsme za to nestrhávali body), jen je to zbytečně pomalé. Stejnou službu umí vykonat shell sám expanzí: 
for f in *

Občas se taky v řešení objevilo testování neprázdnosti pomocí wc -c. Tuto metodu jsme použili v řešení minulé série, protože jsme ještě neznali lepší prostředky. Musí vám být ale jasné, že takový test bude ukrutně pomalý.

Jak tedy mohlo vypadat ideální řešení?

for f in *; do
	[ -f "$f" -a ! -s "$f" ] && echo "$f"
done

Druhá úloha byla trochu triková. Někteří se k tomu snažili použít pole, je to ale zbytečně silný a nepřenositelný kanón. Dnes už je situace s podporou polí v různých shellech lepší než před lety, stále se ale budeme snažit používat jednodušší prostředky.

Naproti tomu, využít k řešení malou utilitku tac, která vypíše řádky vstupu v opačném pořadí, je moc pěkný nápad:

IFS='
'
echo "$*" | tac
Slepit malé utilitky, které za nás udělají špinavou práci, je přesně filozofie programování v shellu. Jak to udělat bez ní, je zamýšlené autorské řešení: 
for arg; do
	p="$arg $p"
done
echo "$p"

Jestli budou argumenty na oddělených řádcích, nebo na jedné, nebylo důležité, stejně tak jestli se přidají apostrofy, uvozovky atp. okolo. Důležité ale bylo, aby se neztrácely mezery a argumenty tvořené pouze bílými znaky.

Třetí úloha byla jen krátký test pozornosti. Pokud použijeme rouru, odsuzujeme příkazy k tomu, aby se spustily v subshellu. Pokud v subshellu změníme nějaké proměnné, změní se jen pro subshell – a zaniknou spolu s ním. Proto musíme read a echo provést v jednom složeném příkazu.

Ve čtvrté úloze jste si měli vyzkoušet sílu proměnné IFS ve spolupráci s příkazem read. Někteří se snažili řádky zpracovávat příkazem cut, nebo ještě kostrbatěji pomocí sedu. To bohužel většinou vedlo k tomu, že jste soubor četli pro každý řádek celý znovu, a to opravdu není správný přístup.

while IFS=: read user x x x x x shell; do
	[ -n "$user" ] && echo "$shell" >"$user"
done </etc/passwd

Všimněte si pěkné zkratky na posledním řádku.

A konečně poslední pátá úloha byla na procvičení možností case. Jen málokdo to ale pochopil, proto jste do řešení často psali šílené podmínkové konstrukce. Také jste často zapomínali uvozovkovat alespoň jméno. Jinak ale nebyl na úloze žádný chyták, proto pojďme rovnou k řešení:

while read akce pohl jmeno; do
	case "$akce $pohl" in
		"prichod M")
			echo "Prisel $jmeno" ;;
		"odchod M")
			echo "Odesel $jmeno" ;;
		"prichod F")
			echo "Prisla $jmeno" ;;
		"odchod F")
			echo "Odesla $jmeno" ;;
	esac
done

Díky za pěkná řešení, těšíme se na další!

Ondra Hlavatý