První 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

• 27-1-1: Zasedací pořádek
• 27-1-2: Zbrojní sklad
• 27-1-3: Letecké koridory
• 27-1-4: Head-up display
• 27-1-5: Napájení přístrojů
• 27-1-6: Přistávací světla
• 27-1-7: Učíme se s UNIXem

Podmínkou na zisk čokolády bylo získání plného počtu bodů z některé ze dvou nejvíce bodovaných úloh první série (což byly úlohy 27-1-6 Přistávací světla a 27-1-7 Učíme se s UNIXem). To se povedlo pěti řešitelům, gratulujeme.

27-1-1 Zasedací pořádek (Zadání)

Piloti na letadlové lodi s vámi mohou být spokojeni – jak pokročilí řešitelé, tak i začátečníci přišli na správné rozsazení osob u stolu. Body jsme však museli strhávat za neúplné (nebo úplně chybějící) popisy druhé podúlohy, případně za drobnosti, jako například chybějící složitost.

Jak budou piloti u stolu rozsazeni, záleží na tom, zda je jejich počet sudý, nebo lichý. Při lichém počtu budou všichni piloti sedět vedle sebe bez mezer, přičemž na centrální židli bude sedět prostřední z nich; jinak bude centrální židle prázdná a piloti budou sedět na obě strany od ní, tvoří tedy dvě souvislé řady délky N/2.

Na řešení nebylo těžké přijít simulací rozsazovacího popisu na papíře pro malá N, jen někteří z vás se ale pokusili dokázat, že výše zmíněná pravidla platí pro jakýkoliv počet pilotů. U takto jednoduché úložky jsme za to body nestrhávali, ale pamatujte si, že komplikovanější problémy důkaz vyžadují – všechno „pouhým okem“ neuvidíte!

Správnost zde dokážeme matematickou indukcí. Pro malá N experimentálně ověříme, že náš popis funguje. Teď musíme ukázat, že se „sudá“ řada při příchodu pilota změní na „lichou“ řadu a naopak: první případ je jednoduchý, příchozí usedne na centrální židli.

Komplikovanější je přechod z liché řady na sudou: v momentě, kdy přichází nový pilot, je centrální židle obsazená – oba se přesunou na židle vedle té centrální, a pokud jsou také obsazené, proces se nutně opakuje, dokud nedojdeme k volným židlím na kraji řady, kam si piloti sednou, a řadu tak rozšíří. Aniž bychom zatím přemýšleli nad piloty, kteří se musí přesunout směrem do středu (představme si, že zatím stojí), vypadá řada takto: 1000...0001 (1 značí obsazenou, 0 volnou židli).

S piloty, kteří se musí ze svých původních míst posunout doprostřed, se řada změní na 1011...2...1101. Ouha, vše je v pořádku, kromě prostřední židle, o kterou mají zájem dva piloti – opět tedy musí nastat přesouvání, které ale dopadne podobně, jako to předchozí (jen se díky mezerám na koncích zkrátí délka řady, na které dochází k přesunům, o dva piloty, kteří sedí nyní na konci a jsou odděleni od ostatních prázdnou židlí).

Každou takovou iterací se krajní prázdná místa posunou směrem doprostřed. Přesouvání bude trvat tak dlouho, dokud se prázdná místa nesetkají na centrální židli, a řada tím pádem bude vypadat tak, jak jsme popisovali.

Nyní k řešení prvního úkolu: Kdybychom přesouvání jen simulovali podle zadaných pravidel, trvalo by nám to dlouho. Ale to není potřeba, díky výše dokázanému pozorování zvládneme vygenerovat řadu pilotů v lineárním čase a konstantní paměti, stačí sestavit jedničky a nuly podle pravidel.

Program, který ověří, zda je zadaný zasedací pořádek správně, si postupně načítá informace o obsazenosti židlí a kontroluje, zda se řada skládá buď z jedné liché řady jedniček (obsazených míst), nebo dvou stejně dlouhých a sudých řad jedniček, oddělených právě jednou nulou. To zvládneme v čase O(N), kde N je délka vstupu. Paměťová složitost je konstantní, protože nás nic nenutí řadu do paměti načítat.

Program (C)

Kuba Maroušek & Jenda Hadrava

27-1-2 Zbrojní sklad (Zadání)

Většina z řešení, která nám přišla, využívala principu hladového algoritmu a vždy vybírala palety s co největší nebezpečností, což byl správný postup. Takový výběr palety nám totiž umožní v příštím kroku dosáhnout nejvýš. Ukážeme si tedy, jak se to dá udělat efektivně.

Abychom mohli rychle hledat palety, na které dosáhneme, rozdělíme si je nejprve na malé a velké, a potom je vzestupně setřídíme podle výšky do dvou polí.

Poté si založíme dvě maximové haldy, odděleně pro malé a velké palety. V nich si budeme udržovat, jaké palety můžeme v každém kroku odebrat a která z nich má tu největší nebezpečnost. V každém kroku tedy vybereme příslušnou haldu pro velké nebo malé palety a odstraníme z ní paletu s nejvyšší nebezpečností. Nyní musíme do obou hald přidat všechny prvky, na které díky odebrání dosáhneme teď.

K tomu využijeme setřízená pole pro malé a velké palety. U každého si budeme pamatovat index prvku, který jsme přidali naposledy. Pokaždé, když budeme chtít přidat nově dosažitelné palety, jen zkontrolujeme všechny palety od tohoto indexu dále, dokud nenarazíme na paletu, která vyžaduje větší výšku, než je aktuálně dovolená. Všechny nalezené palety s výškou menší nebo rovnou dovolené budeme průběžně přidávat do příslušných hald.

Toto budeme opakovat, dokud jedna z hald nebude prázdná (tedy jsme právě narazili na omezení bezpečnostních předpisů), nebo nám v našich polích nedojdou palety (pak jsme všechny přidali do haldy, tedy na všechny dosáhneme, neboli můžeme všechny palety vyndat bez porušení předpisů).

Velká většina vás narazila na problém volby počáteční palety a mnoho z vás si závorku v zadání (velká, malá, velká) vyložilo tak, že budeme začínat velkou paletou. Po dlouhé diskusi jsme za toto nestrhávali body, ačkoli původně byla úloha myšlená tak, že nebude blíže určeno, kterou paletou začínáme. Řešením, u kterých nebylo očividné, zda si to autoři rozmysleli nebo ne, jsme to připsali do poznámky, která je s tímto vysvětlením snad již trochu jasnější.

Časová složitost algoritmu vychází jednak ze třídění, které nezvládneme obecně rychleji než v čase O(N log N), a také z hald (musíme v nich probublat až N prvků, každý v čase O(log N). Celková časová složitost je tedy O(N log N). Paměti zabereme lineárně s velikostí vstupu (každou paletu uložíme do haldy a pole jednou).

Program (C++)

Štěpán Hojdar & Jan „Oggy“ Škoda

27-1-3 Letecké koridory (Zadání)

Nejprve bychom se chtěli omluvit za určité nepřesnosti v zadání samotné úlohy. Konkrétně nebylo jasné, zda se úloha má řešit pro ohodnocený či neohodnocený graf. Plný počet bodů jsme proto udělovali za optimální řešení libovolné z těchto variant.

Stejně dlouhé koridory

Většina z vás, kteří jste brali v úvahu neohodnocený graf, přišla na to, že prohledávání do šířky je správný směr k optimálnímu řešení úlohy. Ve vašich řešeních se pak vyskytovaly nanejvýš drobné implementační chyby.

Graf tedy budeme procházet po hladinách od počátečního vrcholu. Budeme si udržovat frontu vrcholů, jež máme postupně zpracovat, do které na začátku umístíme pouze počáteční vrchol. Pro každý vrchol si navíc zapamatujeme délku nejkratší cesty do tohoto vrcholu (pokud jsme nějakou našli) a počet doposud nalezených nejkratších cest. Na začátku víme, že do počátečního vrcholu vede pouze jedna nejkratší cesta délky nula. O ostatních vrcholech nevíme nic.

Při zpracovávání každého vrcholu u vyjmutého z fronty postupně projdeme všechny jeho hrany. Cesta, která vede do u a poté po zkoumané hraně do vrcholu v, má délku rovnou délce nejkratší cesty do u zvětšené o jedničku. Tuto délku potenciálně nejkratší cesty porovnáme s délkou známé nejkratší cesty do v. Mohou nám nastat tři situace. Buď cestu do vrcholu v neznáme – v tom případě je nejkratší cesta do v právě ta námi uvažovaná (pokud by existovala kratší, přišli bychom na ni při zpracovávání předchůdce koncového vrcholu, který se na této nejkratší cestě nachází). Počet takovýchto cest je roven počtu nejkratších cest do u. Protože jsme tento vrchol ještě neviděli, přidáme jej do fronty vrcholů ke zpracování.

Pokud je délka naší navržené cesty stejně dlouhá jako známá délka nejkratší cesty do v, přišli jsme na další nejkratší cesty, které končí v tomto vrcholu. Zvětšíme tedy počet možných nejkratších cest, jež do vrcholu v vedou, o počet nejkratších cest vedoucích do vrcholu u. Do fronty vrchol v přidávat nebudeme, neboť jsme jej tam přidali, když jsme poprvé určili délku nejkratší cesty. A pokud je délka navržené cesty delší než známá délka nejkratší cesty do koncového vrcholu, nebudeme dělat nic, protože námi navržená cesta určitě není nejkratší.

V okamžiku, kdy frontu vyprázdníme, vypíšeme na výstup počet nejkratších cest vedoucích do cílového vrcholu a algoritmus ukončíme. Můžeme jej ukončit i v případě, když zpracovávané cesty jsou delší než nejkratší cesta do cílového vrcholu, v takovém případě totiž už nenalezneme žádnou další nejkratší cestu, nicméně toto nijak nezlepší asymptotickou časovou složitost. Výsledek je pak počet nalezených nejkratších cest do cílového vrcholu.

Správnost algoritmu můžeme ukázat indukcí. Na začátku vede pouze jedna cesta do počátečního vrcholu. V okamžiku, kdy vyjmeme nějaký vrchol z fronty, zpracovali jsme již všechny jeho předchůdce, po kterých vede nejkratší cesta (všechny vrcholy, které jsme dosud nezpracovali, leží na stejné hladině jako zkoumaný vrchol, nebo na hladině ještě vyšší, proto přes ně nemůže vést nejkratší cesta do zkoumaného vrcholu). Z čehož vyplývá, že pro každý vrchol vyjmutý z fronty nalezneme všechny nejkratší cesty. Z popisu algoritmu přímo plyne, že jsme žádnou cestu nezapočítali dvakrát, čímž je dokončen důkaz správnosti.

Každý vrchol přidáváme do fronty nanejvýš jednou a stejně tak každou hranu zkoumáme maximálně jednou. Časová složitost je tedy O(N + M), kde N je počet vrcholů a M je počet hran. U každého vrcholu si musíme pamatovat délku a počet nejkratších cest. Dále si musíme pamatovat všechny hrany. Dostáváme tedy i paměťovou složitost O(N + M).

Program (C++)

Ohodnocené hrany

V případě, že pracujeme s ohodnocenými grafy, řešení bude podobné tomu předchozímu. S obyčejným průchodem do šířky si však nevystačíme. Místo něj budeme vycházet z Dijkstrova algoritmu, který se prohledávání do šířky podobá, jen místo toho, aby bral nejbližší vrcholy podle počtu hran, je bere podle vzdálenosti. Hrany tedy nemůžeme uchovávat v obyčejné frontě, ale musíme je mít ve frontě prioritní, tedy haldě. V tomto řešení budeme pro jednoduchost uvažovat haldu binární. Další rozdíl mezi řešením pro neohodnocené grafy a tímto bude, že při přidání hrany do cesty nezvětšíme délku cesty o jedna, ale o celou délku dané hrany.

Při zpracování vrcholu u, který označíme jako definitivní, budeme v daných případech postupovat stejně jako při zpracovávání vrcholu v předchozím algoritmu. Tedy když neznáme cestu do sousedního vrcholu v, prohlásíme nově nalezenou cestu za nejkratší. Počet nejkratších cest vedoucích do vrcholu v tak bude stejný jako počet nejkratších cest do vrcholu u, navíc vrchol v přidáme do haldy. Když nalezneme stejně dlouhou cestu, upravíme počet nejkratších cest, a když nalezneme delší cestu, nic neděláme.

Nyní však už nemáme garantováno, že když jsme vrchol navštívili, nenalezneme ještě lepší cestu než tu, kterou jsme nalezli poprvé. Když takováto situace nastane, postupujeme stejně jako v případě, kdy bychom žádnou cestu do v neznali – zahodíme informace o počtu a délce nejkratších cest do vrcholu v, jako délku nejkratší cesty určíme nejkratší cestu do u zvětšenou o délku hrany a počet nejkratších cest do v bude stejný jako počet nejkratších cest do u. Vrchol do haldy ale přidávat nebudeme, neboť se v ní již nachází.

Nesmíme ale zapomenout změnu nejkratší cesty do haldy k vrcholu zaznamenat. Abychom daný vrchol v haldě rychle našli, budeme si navíc ještě bokem uchovávat pole, které nám říká, kde v haldě se daný vrchol nachází. Toto pole budeme aktualizovat při každé změně pozice nějakého vrcholu v haldě.

Změnou délky nejkratší cesty se nám však mění i pozice, kde by se vrchol v haldě měl nacházet. V případě, kdy tuto délku měníme, necháme vrchol probublat v haldě výš (nikdy nepotřebujeme posunovat vrchol níže, protože když měníme délku nejkratší cesty, vždy ji nahrazujeme cestou ještě kratší).

V haldě si v každém okamžiku uchováváme nanejvýš všechny vrcholy. Hloubka haldy je tedy maximálně log N. Jedno vyjmutí vrcholu z haldy nám zabere s následným přerovnáním O(log N) času. Každý vrchol odebereme nanejvýš jednou, celkově tedy O(N log N). Každý vrchol do haldy nanejvýš jednou přidáme, jedno přidání zabere logaritmický čas, dohromady tedy opět O(N log N). A konečně při změně nejkratší cesty do nějakého vrcholu musíme upravit pozici daného vrcholu v haldě. Pro každý vrchol to zabere O(log N) času a těchto operací provádíme nanejvýš M. Tyto operace tedy zaberou O(M log N) času. Celý algoritmus bude mít časovou složitost O(M log N + N log N) neboli O((M + N) log N), což je stejná složitost, jakou má běžný Dijkstrův algoritmus.

Pamatovat si potřebujeme u každého vrcholu délku nejkratší dosud nalezené cesty, počet takových cest a umístění v haldě. Dále si potřebujeme pamatovat všechny hrany. Paměťová složitost bude tedy O(N + M).

Program (C++)

Lukáš Folwarczný & Dominik „Drecker“ Smrž

27-1-4 Head-up display (Zadání)

Displej má N pixelů, každé jeho nastavení má hodnotu, do které přispívá každý pixel rozdílem kontrastu oproti původnímu nastavení. Ze všech přípustných variant změny kontrastu vybíráme tu nejmenší. Na to se můžeme dívat jako na nejkratší cestu v grafu.

Jak takový graf vypadá? Má N · K vrcholů, pro každý pixel a každou možnou hodnotu kontrastu jeden. (Ono vlastně bude stačit N-krát nejvyšší hodnota kontrastu na vstupu, je snadno vidět, že v nejkratší cestě nikdy výš nepůjdeme, ale v nejhorším případě jich stejně bude N · K.) Můžeme si představit, že jsou uspořádány v tabulce, vodorovně jich je N, svisle K.

Potřebujeme zajistit, aby se hodnoty kontrastu v sousedních sloupcích (neboli sousedních pixelech displeje) nelišily o více než o D. Přidáme proto do grafu hrany. Budou orientované, povedou zleva doprava vždy mezi vrcholy v sousedních sloupcích, a to nanejvýš o D řádků výš nebo níž. Tím pádem bude každá cesta z prvního sloupce do posledního korektní nastavení displeje. To nastavení přečteme snadno, napíšeme si za sebe navštívené řádky a ty přesně odpovídají hodnotám kontrastu jednotlivých pixelů.

Jaká bude hodnota cesty? Součet změn pixelů. Hranám dáme ohodnocení. Je-li pixel nastaven na hodnotu 10, pak všechny hrany vedoucí do 10. řádku tohoto sloupce budou mít hodnotu 0. Všechny hrany vedoucí do 11. a 9. řádku budou mít hodnotu 1, protože hodnotu pixelu měníme o jedničku. Hrany do 12. a 8. řádku budou mít dvojku a tak dále. Hodnota cesty je samozřejmě součet vah hran.

Teď už jen najít nejkratší cestu z prvního sloupce do posledního. Pokud znáte pouze algoritmus, který hledá nejkratší cesty z jednoho vrcholu do dalšího, a ne z K vrcholů do některého z jiných K vrcholů, nezoufejte, upravíme si graf, abychom ho mohli použít. Přidáme si do grafu dva speciální vrcholy. Jeden bude startovní, z něho budou vycházet hrany do všech řádků prvního sloupce, ohodnoceny budou změnou kontrastu prvního pixelu oproti jeho původní hodnotě. Druhý speciální vrchol bude ten cílový, ze všech vrcholů posledního sloupce povedou hrany do něj. Ohodnoceny budou nulou.

Náš graf je orientovaný acyklický neboli po anglicku zkráceně DAG. Pro něj existuje rychlejší algoritmus na nejkratší cesty, než je Dijkstrův. Pro každý vrchol si budeme pamatovat délku zatím nejkratší nalezené cesty (na začátku bude na startu nula, ve zbytku grafu nekonečno) a vrchol, ze kterého jsme do aktuálního vrcholu přišli (podle toho pak zrekontruujeme nejkratší cestu). Značit je budeme jako delka(u) a odkud(u).

Budeme odebírat vrcholy v topologickém pořadí, (tak se to dělá u obecných DAGů), pro nás to znamená po sloupcích zleva doprava. Vezmeme vrchol a zrelaxujeme všechny jeho hrany. Tak se říká postupu, kdy zkusíme najít kratší cesty procházející danou hranou. Pokud si budeme váhu hrany značit jako w(u,v), znamená to, že pro hranu (u,v) uděláme toto:

1. Pokud cesta(u) + w(u,v) < cesta(v):
2. cesta(v) ←cesta(u) + w(u,v)
3. odkud(v) ←u

Řečeno slovy, známe již nejkratší cestu do u, a vede-li hrana z u do v, pak se do v mohu dostat za cenu rovnou délce cesty do u a váze hrany (u,v). Pokud je to lepší než dosud nejkratší nalezená cesta, tak si novou délku uložím a zapamatuji si, odkud jsem přišel.

A to je všechno. Už jenom vypíšeme délku nejkratší cesty a díky zpětným odkazům zrekonstruujeme průběh cesty (jen ho ještě musíme obrátit, dostaneme ho totiž pozpátku).

Určíme časovou složitost. Bereme do ruky každý vrchol, těch je N · K, a každou hranu. Z každého vrcholu vede nanejvýš 2D+1 hran, takže jich je celkem O(NKD), a to je i celková časová složitost. Paměti nám ale stačí jen O(NK). Hrany totiž nemusíme mít nikde uloženy, snadno si spočítáme, která hrana existuje a která ne.

Program (C)

Program (Python)

Dominik Macháček

27-1-5 Napájení přístrojů (Zadání)

Tolik přístrojů a tolik různých požadavků na napětí… no naříkat na standardizaci můžeme jindy, teď pojďme vyřešit úlohu.

Vezměme si na chvíli požadavky na napájení jednotlivých přístrojů jako intervaly. Je jasné, že přístroje, jejichž intervaly se nepřekrývají, nemohou sdílet stejný zdroj napájení. A pokud budeme mít trojici intervalů, kde první se překrývá s druhým a druhý s třetím (ale první a třetí průnik nemají), můžeme sice vždy alespoň dva přístroje napájet z jednoho zdroje, ale třetí do toho nezařadíme. To je sice pěkné, ale co z toho?

Každý přístroj musíme z nějakého zdroje napájet. Když si vezmeme naše intervaly a podíváme se na interval (a,b), který končí nejdříve (jehož konec má nejnižší hodnotu), tak určitě musíme nějaký napájecí zdroj umístit mezi a a b, jinak bychom tento přístroj nepokryli. No ale má smysl nastavovat první napájení na menší hodnotu než b?

Protože všechny další konce intervalů jsou až za b, nemá. Nastavíme tedy první zdroj na b, připojíme na něj všechny přístroje, kterým vyhovuje, a odebereme jejich intervaly. Pak se podíváme na zbylé intervaly a budeme tento hladový postup opakovat, dokud nezapojíme všechny přístroje.

Teď je potřeba si rozmyslet dvě věci. První z nich je, jak rychle algoritmus běhá. Pokud už dostaneme intervaly setříděné podle konců, stačí nám je v čase O(N) od nejmenšího projít a postupně je označovat za zapojené, pokud je setříděné mít nebudeme, zvedne se nám čas tříděním na O(N log N).

Druhou a zajímavější otázkou je, zdali to skutečně funguje. To by chtělo dokázat. Postupným zapojováním nějakých přístrojů na vyhovující zdroje vytvoříme nějakých K množin intervalů (tvořených z původních povolených intervalů napájení přístrojů obsažených v každé množině). Každou množinku si můžeme sjednocením převést na jeden nový interval, čímž nám vznikne K různých intervalů.

No ale protože do množinky pokaždé zapojíme všechny vyhovující přístroje, jsou jednotlivé vzniklé intervaly navzájem disjunktní. A pokrýt K disjunktních intervalů určitě nejde pomocí méně než K zdrojů, tím jsme dokázali optimálnost našeho řešení.

Program (C)

Program (Python)

Jirka Setnička & Dominik Macháček

27-1-6 Přistávací světla (Zadání)

Dvojbarevná verze

Začneme jednodušší verzí úlohy, která používá dvě barvy (říkejme jim třeba X a Y) a chce po nás najít nejdelší „bílý“ úsek, tedy takový, v němž je obou barev stejně.

Úlohu převedeme na podobný problém s čísly: barvu X přepíšeme na +1 a Y na -1. Bílé úseky jsou nyní přesně ty se součtem 0. Poznáme je pomocí prefixových součtů z kuchařky: označíme p_i součet čísel na prvních i pozicích (p₀=0) a kdykoliv p_i = p_j, znamená to, že na pozicích i+1 až j leží bílý úsek.

Chceme tedy v posloupnosti prefixových součtů najít dvě stejné hodnoty, které od sebe leží co nejdále. To provedeme snadno: budeme procházet vstup zleva doprava a průběžně si počítat prefixové součty. Pro každou možnou hodnotu prefixového součtu (-n až n) si budeme v nějakém poli pamatovat, jestli jsme ji už viděli, a pokud ano, tak kde poprvé. Kdykoliv pak narazíme na hodnotu prefixového součtu, kterou jsme už viděli, spočítáme vzdálenost od prvního výskytu – to je délka nejdelšího bílého úseku končícího aktuálním prvkem – a započítáme ji do průběžného maxima.

Časová složitost bude lineární: O(n) na inicializaci pomocného pole a pak O(1) na zpracování každého prvku. Paměti nám také stačí O(n).

Program (C)

Od dvou barev ke třem

„Plnotučná“ verze úlohy pracuje se třemi barvami (třeba R, G a B) a chce po nás úseky, kde je všech třech stejně.

Pomůžeme si drobným úskokem: bílý úsek je ten, ve kterém je stejně R jako G a současně G jako B. To nám dává dvě instance dvojbarevné verze, které chceme vyřešit současně.

Vstup proto budeme překládat na posloupnost dvojic čísel (dvojsložkových vektorů): R bude (1,0), G bude (-1,1) a konečně B přeložíme na (0,-1). Bílé úseky teď budou ty, které mají součet (0,0), přičemž sčítáme zvlášť první složku všech vektorů a zvlášť druhou.

Opět do práce zapřáhneme prefixové součty – co na tom, že teď to nebudou čísla, ale dvojice čísel, fungovat budou stejně.

Jen už nemůžeme hodnotami prefixových součtů indexovat pole: muselo by být dvojrozměrné, takže by jeho inicializace trvala O(n²) a zkazila nám jinak lineární složitost.

Místo pole si proto pořídíme chytřejší datovou strukturu, třeba vyvážený vyhledávací strom (dvojice porovnáváme lexikograficky). Dvojic je ve stromu nejvýše n, takže každá operace se stromem trvá O(log n), a celý algoritmus tudíž potřebuje O(n log n) času a O(n) prostoru.

Kdybychom si místo pole pořídili hešovací tabulku, bude jedna operace s dvojicemi trvat průměrně O(1), takže celý algoritmus poběží v čase průměrně O(n) a prostoru O(n).

Skutečně lineární řešení

Existuje ovšem řešení, které má lineární složitost i v nejhorším případě. Inspirujeme se přechozí úvahou o prefixových součtech, ale stejné dvojice nebudeme hledat on-line pomocí datové struktury, nýbrž dávkově tříděním.

Vytvoříme posloupnosti trojic: kdykoliv má i-tý prefixový součet hodnotu (a_i,b_i), přidáme trojici (a_i,b_i,i). Tyto trojice pak setřídíme lexikograficky, čímž se nám dostanou k sobě všechny výskyty stejných prefixových součtů. Snadno pak mezi nimi najdeme ty nejvzdálenější.

No dobrá, třídění trvá O(n log n) a takhle rychlý algoritmus jsme už měli. Nenechte se mýlit, třídit jde i rychleji. V našem případě jsou složky trojic malá celá čísla, takže zafunguje přihrádkové třídění, které to zvládne v lineárním čase. Pokud ho ještě neznáte, je nejvyšší čas podívat se do kuchařky o třídění.

Zde ho popíšeme aspoň stručně: pořídíme si přihrádky indexované od -n do n (rozsah možných hodnot složek). Nejprve trojice rozházíme do přihrádek podle poslední složky a zase je vysbíráme (v pořadí od nejnižší přihrádky k nejvyšší). Pak provedeme totéž podle druhé složky a nakonec ještě jednou totéž podle první. Přitom u trojic, které padnou do téže přihrádky, stále zachováváme pořadí z předchozích průchodů. Proto nám nakonec vyjde přesně lexikografické pořadí.

Pokaždé strávíme čas O(n) rozhazováním trojic do přihrádek a O(n) jejich vysbíráváním. To provedeme celkem třikrát a pak ještě sekvenčně projdeme setříděné trojice, což nám všechno zabere O(n) času. Paměti nám stále postačí O(n) buněk.

Dodejme ještě, že kdybychom měli b barev namísto tří, použijeme b-tice a vše nám bude trvat O(bn) s pamětí O(bn). Též bychom k barvám mohli přidat i „anti-barvy“, které se chovají opačně – tím se bychom se přiblížili k prapůvodní fyzikální inspiraci úlohy teorií kvarků.

Program (C)

Poznámka o rekurzi

Existuje i jiné lineární řešení, také založené na dvojím použití dvojbarevné verze úlohy.

Nejprve řešíme úlohu pro R a G. Tím nám vzniknou nějaké prefixové součty a pro každé dvě pozice i,j se stejným prefixovým součtem chceme vyřešit úlohu pro G a B mezi těmito pozicemi.

Rozházíme si tedy pozice ve vstupu do přihrádek podle hodnoty prefixového součtu pro R a G. Pro každou přihrádku pak spustíme novou instanci úlohy pro G a B; nebudeme-li pořád dokola inicializovat datové struktury a počítat prefixové součty, zvládneme to lineárně s množstvím pozic v této přihrádce. V součtu přes všechny přihrádky tedy O(n).

Implementační detaily nejsou triviální, ale pokud se jimi prokoušeme, uvědomíme si, že jsme právě popsali přihrádkové třídění „naruby“, tedy od nejvyššího řádu k nejnižšímu. Nic nového pod sluncem.

Poznámka o komplexních číslech

Ještě zmíníme jeden mírně bláznivý způsob, jak řešit tříbarevnou úlohu. Je zajímavý tím, že pro 4 barvy by už nefungoval a že v něm hrají hlavní roli komplexní čísla.

Pořídíme si komplexní třetí odmocniny z jedničky, totiž čísla c₁=1, c₂ = -1/2 + i · √3/2 a c₃ = -1/2 -i · √3/2. Tato tři čísla jsou rovnoměrně rozmístěna po jednotkové kružnici po násobcích 120°.

Nyní přeložíme R, G a B na čísla c₁, c₂ a c₃ a nahlédneme, že bílé úseky jsou přesně ty se součtem 0. (Rovnost imaginárních částí vynucuje, že všech G je stejně jako B. Z rovnosti reálných částí pak dostaneme, že R je stejně jako G i B.)

Tato úvaha dále vede na podobná lineární řešení.

Martin „Medvěd“ Mareš

27-1-7 Učíme se s UNIXem (Zadání)

Jsme velmi rádi, že jste se UNIXu nezalekli a přišlo nám tolik vašich řešení. Většina úkolů byla jednoduchá, ale sem tam se objevily nějaké zrádnosti nebo zbytečně obtížné konstrukce.

Často bylo bodování obtížné, ale pokoušeli jsme se hodnotit praktičnost a jednoduchost vašich řešení a podle nich přidělovat nějaké zlomky bodů.

Pokusíme se tedy v autorském řešení ukázat, jaký je podle nás nejlepší přístup ke všem úkolům.

Úkol 1 – složky

Zde bylo správné podívat se do manuálových stránek příkazů mkdir a rm. Když se pokusíte pomocí prvního zmíněného vytvořit složku ve složce, která ještě neexistuje, vynadá vám. Pokud ale zavoláte mkdir -p, přepínač -p způsobí vytvoření všech složek po cestě.

Při mazání je možné mazat také pomocí rmdir -p, ale předtím je nutné vymazat vytvořený soubor. Pokud ale použijeme rm -r (-r jako zkratka za rekurzivní), můžeme rovnou vymazat všechno.

mkdir -p ~/a/b/c/d
touch ~/a/b/c/d/test
rm -r ~/a

Úkol 2 – head a tail

Zde bylo řešení velmi jednoduché. Rychlým pohledem do manuálových stránek jde zjistit, že příkazy head i tail mají oba přepínač -n K, který vypíše prvních, respektive posledních K řádků ze souboru. Jak ale vypsat všechno až na prvních K řádků?

Pečlivějším pročtením manuálových stránek se dá přijít na to, že zavoláním tail -n+K (všimněte si, že ani není potřeba mezera mezi přepínačem a jeho hodnotou) vypíše celý soubor začínající od K-tého řádku. My ale chceme K řádků vynechat, tedy chceme začít až od (K+1)-ního:

head -n15
tail -n15
tail -n+16

Úkol 3 – escapování

Problém zapisování podivných znaků se dá vyřešit dvěma způsoby: escapováním speciálních znaků nebo uzavřením do uvozovek. Při escapování musíme zrušit význam znaků jako závorka, mezera nebo otazník, při zavírání do uvozovek nám stačí dávat si pozor na jiné uvozovky. Správným řešením tedy mohlo být:

rm a\?c
rmdir "adresar[567]"

Úkol 4 – wildcardy

Toto byl první trochu více tvůrčí úkol a jsme rádi, že nám na něj přišla spousta různých elegantních řešení. Nakonec jsme se rozhodli hodnotit vaše wildcardové výrazy podle toho, jak efektivně jste použili dostupné prostředky.

Asi nejkratší rozumný výraz, který odpovídá zadaným pravidlům je tento:

*{[0-9]*[0-9],[a-zA-Z]*[a-zA-Z]}*/*.{jp{e,}g,gif}

Část {[0-9]*[0-9],[a-zA-Z]*[a-zA-Z]} říká to, že se někde v názvu musí nacházet buď dvě čísla, nebo dvě písmena oddělená libovolnými jinými znaky mezi sebou. K nim přidáme libovolné množství znaků před a za (obalení hvězdičkami) a tím máme část složky hotovou.

Název souboru může být libovolný a pak následuje přípona {jp{e,}g,gif}. Všimněte si hlavně elegantně použité vnořené složené závorky: ta nám říká, že se zde může nacházet buď e, nebo nic.

Přišlo nám i několik málo ještě šílenějších konstrukcí, ale výraz uvedený výše považujeme asi za optimální vzhledem k jeho složitosti a plně nám dostačoval.

Úkol 5 – datum v souboru

Hlavní věcí, na které byl tento úkol postaven, bylo přesměrování výstupu. Použití jedné šipky vždy soubor přepisuje celý, ale použití dvou šipek pouze přidává na konec. Správným řešením tedy bylo:

echo "Dnes je:" > datum
date >> datum

Poznámka: U příkazu echo by uvozovky ani nebyly potřeba, echo opíše na výstup všechny své parametry. Ale přijde nám, že s použitím uvozovek je příkaz přehlednější.

Úkol 6 – počítání složek a adresářů

V tomto případě stačilo přesměrovat výstup z příkazu ls do příkazu wc a tím spočítat řádky:

ls | wc -l

Část z vás možná zmátlo to, že ls vypisuje všechny soubory na jeden řádek a používali jste s ním přepínač -1. To ale není potřeba, jelikož ls je trochu speciální příkaz. Při spuštění si totiž „osahá“ svoje okolí a zjistí, jestli je spuštěný v rouře, nebo zobrazuje výstup uživateli. V tom druhém případě se pokusí svůj výstup zkrátit a vypisuje soubory na jednu řádku, v tom prvním je ale vypíše všechny normálně pod sebou.

Častou chybou v tomto úkolu bylo použití přepínače -w u wc namísto přepínače -l. Na první pohled se může zdát, že oba vracejí správný výsledek, ale to jen do chvíle, kdy se objeví soubor obsahující v názvu mezeru. V tom případě -w počítající slova již dá špatný výsledek.

Úkol 7 – kombinace head a tail

Hlavní kouzlo spočívalo v tom správně si spočítat řádky a pak nakombinovat příkaz. Jedenáctou až třicátou řádku získáme pomocí některého z následujících příkazů:

head -n30 < soubor.txt | tail -n+11 | wc -w
tail -n+11 < soubor.txt | head -n20 | wc -w

Zde se ale také objevila jedna z nejpodivnějších věcí na celém řešení, zhruba dvě pětiny z vás totiž místo třicáté řádky přečetli v zadání řádku třináctou a podle toho jste pak psali příkaz. Přivedlo nás to k zajímavému lingvistickému rozhovoru o čtení velmi podobných slov. :-)

Úkol 8 – velikosti souborů

V posledním úkolu jsme jasně nespecifikovali, že chceme jen soubory v aktuálním adresáři a nemusíte vypisovat rekurzivně všechny soubory v podsložkách (na což stejně v tomto dílu seriálu ještě ani nebyly ukázány vhodné příkazy a konstrukce). Omlouváme se za to.

Těm, kteří ale pro řešení použili nějaké složitější ještě nevysvětlené příkazy a povedlo se jim správně vyřešit obtížnější verzi, jsme také dávali plný počet bodů. Pokud jste ale zbytečně komplikované příkazy použili na řešení jen lehčí verze, o nějakou tu desetinku bodu jste přišli.

Nejtěžší na celém úkolu bylo zkonstruovat ten správný wildcard, kterému by vyhovovaly i skryté soubory (wildcardová hvězdička se totiž normálně na skryté soubory uvedené tečkou nerozexpanduje). Šlo to udělat například jako {.,}*[0-9]* (tuto konstrukci se složenou závorkou jsme mohli potkat už ve čtvrtém úkolu).

Na spočítání velikosti souborů pak šel využít příkaz wc -c a pokud jsme chtěli jen celkový součet (který wc -c vypisuje na poslední řádek), mohla celá konstrukce vypadat třeba takto:

wc -c {.,}*[0-9]* | tail -n1

Doufáme, že UNIXu zůstanete věrní i v další sérii.

Jirka Setnička & Marek Dobranský