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

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

Řešení úloh

22-3-1 Falešná mince (Zadání)

Nad úlohou budeme uvažovat trochu pozpátku. Co nám asi může říct lékárník? Z každého vážení mohou přijít tři různé výstupy. Buďto se váhy naklonily vlevo, nebo vpravo, nebo zůstaly v rovnováze. Tedy máme celkem 3K možných odpovědí pro K vážení. Kdybychom věděli, že mince je BÚNO (bez újmy na obecnosti) lehčí, pak máme naprosto triviální situaci. Podíváme se, která mince byla na všech miskách, které byly prohlášeny za „lehčí“, a nebyla na žádných jiných. Umíme zvážit 3K mincí a finito.

Nicméně my víme jen to, že mince je různé hmotnosti, a tedy musíme uvážit obě možnosti. Nalezneme minci, která byla buďto na všech lehčích, nebo na všech těžších miskách a při rovnovážných váženích ležela stranou. Tedy sestavíme takovou sadu vážení, aby se toto dalo jednoznačně určit. Uvědomme si však, jak se liší výsledky pro stejnou minci falešnou, ovšem jednou lehčí a jednou těžší – výsledek každého vážení se prostě obrátí (a vznikne inverzní výsledek) s výjimkou případu, kdy byly váhy vždy v rovnováze, ten je inverzní sám sobě – a tedy můžeme určit maximální počet mincí, které umíme zvážit K váženími, na (3K+1) / 2.

Každé minci tedy můžeme přiřadit jeden řetězec znaků <=>, znamenajících „levá strana je lehčí“, „váhy jsou v rovnováze“, „pravá strana je lehčí“. Z každého můžeme získat jemu inverzní vzájemným nahrazením znaků <>.

Takový řetězec také říká, jak ve kterém vážení mince figuruje. Jsou-li váhy v rovnováze, zjevně na nich falešná mince zrovna není, jinak se nachází na jedné z misek. Uvažme tedy i-té vážení: Existuje právě 2 ·3K-1 různých řetězců délky K majících na i-tém místě < nebo >. Z nich ale právě polovinu vyškrtáme – jsou v nich totiž samé dvojice duálních řetězců. Takže na dvě misky v i-tém vážení potřebujeme rozmístit 3K-1 mincí, to ale není možné (neumíme nedestruktivně rozdělit lichý počet mincí na poloviny) – jeden řetězec zjevně nevyužijeme, a tedy neumíme zvážit (3K+1) / 2 mincí, ale jen (3K-1) / 2 mincí.

Nyní přichází nejtěžší úkol – jak zkonstruovat rozložení mincí na váhy. Pro N=1 si můžeme být jisti, že ta mince, kterou držíme v ruce, je falešná. Pro N=2 to naopak určit vůbec nelze. Pro ostatní N vytvoříme N řetězců délky K ze znaků <=> tak, že pro každou pozici i ∈{1 …K} bude platit, že existuje stejný počet řetězců majících na i-té pozici < jako počet řetězců majících na i-té pozici > (dále označuji jako Podmínka). Pak jednoduše rozložím mince na váhy při jednotlivých váženích tak, že při < položím minci na levou misku, při > na pravou a při = odložím stranou.

Příklad: vážení pro N=4 se dá zapsat jako 1–2, 2–3, ale také jako MN = {<=, ><, =>, ==}, což pak přečteme jako předpis: „První minci polož při prvním vážení na levou misku a při druhém ji odlož stranou; druhou minci polož při prvním vážení na pravou misku a při druhém na levou; třetí minci nejdříve odlož stranou a při druhém vážení polož na pravou misku a čtvrtá mince nechť se vah ani nedotkne.“

Zkonstruujme nejprve rozložení pro N = NK = (3K-1) / 2 a z nich potom všechna ostatní rozložení. To uděláme rekurentně – konstrukcí z předchozího. Pro K=2, N2 = 4 máme předchozí příklad. Všimněme si, že v něm není řetězec <<. Lze jednoduše ukázat, že NK+1 = 3NK + 1. Vezměme tedy množinu MNK, odstraníme z ní řetězec ==…= a do množiny MNK+1 ji vložíme třikrát – jednou ke všem řetězcům přidáme na začátek <, jednou > a jednou =. Chybí nám ještě 4 řetězce: trojice =>>>…>, ><<<…<, <===…= a „odložená mince“ ===…==. Je jednoduše ověřitelné, že množina MNK+1 splňuje Podmínku a zároveň neobsahuje řetězec <<<<…<<.

Nakonec si ještě rozmyslete, že z každé takto zkonstruované množiny lze vyškrtnout správný počet řetězců, abychom získali MN, pro všechna N s výjimkou N=2. Jde totiž rozdělit MNK na trojice splňující Podmínku: Označíme-li v MNK-1 nějakou existující trojici řetězců jako A, B, C, tak v MNK máme následující trojice: (<A, =B, >C), (=A, >B, <C), (>A, <B, =C). Zbytek je jedna trojice a „odložená mince“.

Tedy pokud potřebuju MN pro N = NK - 3φ, tak odstraním φ trojic, pro N = NK - (3φ+ 1) odstraním φ trojic a „odloženou minci“. Zbývá podlý trik podle Mirka Olšáka (díky!) pro N = NK - (3φ+ 2): Z řetězců =<<<<…<<=, <>>>…>>=, =<<<…<<< udělám řetězec <<<<…<<, který v MNK nebyl, čímž jsem se zbavil dvou řetězců, a následně ještě odstraním φ dalších trojic.

A tedy počet vážení, které potřebujeme k určení falešné mince z množiny N mincí, je roven K = ⌈ log3 (2N)⌉.

Jan "Moskyt" Matějka

22-3-2 Dětská hra (Zadání)

Jednalo se o grafovou úlohu. Děti představují vrcholy a pokud má dítě u chytat dítě v, pak existuje hrana (u,v). Dítě d se může dostat do pozice, kdy by muselo chytat samo sebe, pouze v případě, že vrchol d leží na kružnici. Z každého vrcholu vede právě jedna hrana, takže počet vrcholů (n) je roven počtu hran (m). Díky tomu víme, že v každé komponentě je právě jeden cyklus. Pokud m = n-1, tak je graf stromem (každý vrchol kromě kořene je zavěšen jednou hranou ke svému předkovi). Pokud přidáme n-tou hranu, tak nám vznikne kružnice.

Kružnice budeme hledat prohledáváním do hloubky. V každé fázi si vybereme vrchol x, který jsme ještě neprošli, a spouštíme prohledávání z něj. U každého vrcholu si značíme „čas“ prvního příchodu (např. číslo fáze) in(vrchol). Postupujeme po hranách, dokud nenarazíme na hranu (u,v), která vede do prozkoumaného vrcholu v. Pokud je čas příchodu do v menší než čas příchodu do x, tak jsme se jen dostali k již prozkoumané části grafu, v opačném případě jsme nalezli kružnici délky in(u)+1-in(v). Poznačíme si délku nalezeného cyklu a pokračujeme další fází, dokud existují neprozkoumané vrcholy. Nakonec jsou všechny vrcholy navštívené a výsledný počet dětí, které mohou chytat samy sebe, je součtem nalezených cyklů.

Při procházení navštívíme každý vrchol právě jednou a ještě jedenkrát se do něj můžeme podívat, pokud leží na cyklu, anebo na cestě, kterou jsme začali procházet až od něj. Časová složitost tedy je O(n), paměťová složitost je taktéž O(n) – pro každý vrchol si pamatujeme jeho následníka.

Program

David Marek

22-3-3 Kurýrní služba (Zadání)

Na první pohled je vidět, že úloha je grafová, města tvoří vrcholy a kurýři orientované grafy (komu nic tyto pojmy neříkají, doporučuji přečíst kuchařku o grafech na našich stránkách). Počet měst (vrcholů) si označíme N a počet kurýrů (hran) M. O husitském orientovaném grafu chceme zjistit, zda-li existuje cesta mezi každými dvěma vrcholy alespoň jedním směrem, tedy z A do B nebo z B do A pro každé dva vrcholy A a B. Takový graf se nazývá polosouvislý.

To bude určitě Floyd-Warshallův algoritmus, zazní v hlavě první návrh. Ten přece počítá nejkratší cestu v orientovaném grafu mezi všemi vrcholy. Používá dvourozměrné pole velikosti N ×N, přičemž prvek na pozici [i,j] obsahuje nejkratší cestu mezi vrcholy i a j. Na začátku jsou všechny prvky inicializovány „nekonečnem“ nebo ohodnocením hrany a v N krocích se vylepšuje odhad na délku nejkratší cesty. Pro podrobnější popis odkazuji opět na naše kuchařky na webu, konkrétně na dynamické programování. Jen dodám, že tento algoritmus má časovou složitost O(N3) a paměťovou O(N2).

S časem O(N3) by však mohli husiti prohrát válku, než by zjistili, že se mezi městy nedají posílat zprávy – mají pomalé dřevěné počítače a spoustu dobytých měst. Navíc nepotřebujeme nutně počítat nejkratší cestu, ani neznáme ohodnocení hran (vzdálenost mezi městy). A zatřetí, dávali bychom pouze za použití algoritmu z kuchařky 13 bodů? Zkusíme tedy postupovat lépe.

Nejprve si dokážeme, že v polosouvislém grafu musí existovat sled procházející všemi vrcholy (sled je cesta, ve které se mohou opakovat vrcholy i hrany). Kdyby totiž neobsahoval všechny vrcholy, vezmeme vrchol V, jenž v něm neleží. Aby byl graf polosouvislý, musí pro každý vrchol U ze sledu existovat buď cesta z U do V nebo z V do U. Podle toho, jestli z vrcholu existuje cesta z nebo do V, si rozdělíme vrcholy na dvě skupiny (tyto skupiny mohou mít nějaký překryv) a seřadíme je podle toho, jak leží na sledu. Potom ovšem můžeme V přidat do sledu mezi poslední vrchol, z něhož se lze dostat do V, a první vrchol, do něhož vede cesta z V, anebo kamkoliv do překryvu těchto dvou skupin.

Aby se nám sled lépe hledal, odstraníme si z grafu orientované cykly, respektive sloučíme je do jednoho vrcholu. Jinými slovy, najdeme silně souvislé komponenty (SSK), což jsou maximální podgrafy, ve kterých mezi každými dvěma vrcholy vede orientovaná cesta oběma směry. Pro představu, SSK mohou tvořit jednotlivé cykly, soustavy více spojených cyklů, ale i samotné vrcholy. Jak je vidět, v nich skutečně nemusíme zjišťovat, jestli existuje cesta mezi každými dvěma vrcholy. Netřeba vymýšlet kolo, na nalezení silně souvislých komponent se používá Kusarajův či Tarjanův algoritmus. My si zde popíšeme Tarjanův, jenž najdete i na anglické Wikipedii pod heslem Tarjan's strongly connected components algorithm.

Tarjanův algoritmus je modifikací prohledávání do hloubky. Oproti standardnímu prohledávání si navíc budeme vrcholy číslovat podle toho, kdy do nich vstoupíme (seřadíme je prohledáváním do hloubky), a při zpětném průchodu hledáme, do jakého vrcholu s co nejnižším číslem se můžeme dostat. Je-li to nejnižší nalezené číslo rovno číslu vrcholu, našli jsme cyklus a tedy SSK. Všimněte si, že každou SSK zaznamenáme právě jednou, protože všechny její vrcholy obdrží stejné číslo – to nejnižší z celé SSK – a rovnost tedy nastane jen u jednoho vrcholu. Tento vrchol si nazveme kořenem SSK.

Jak zjistit, jaký potomek vrcholu má nejnižší číslo? Jednoduše, stačí se podívat, do jakého nejnižšího čísla se dostali potomci vrcholu, do nichž z něj vede hrana. Pokud narazíme na cyklus a tedy na vrchol, u něhož dosud tuto hodnotu neznáme, vezmeme prostě jeho číslo (což se dá zařídit lehce – na začátku bude mít každý vrchol inicializován nejnižšího potomka svým číslem).

Díky nalezení SSK v kořeni (vrcholu s nejnižším číslem v SSK) máme jistotu, že jsme získali maximální SSK, tedy že k ní už nelze žádný vrchol přidat, aby zůstala silně souvislá. Pro určení, které vrcholy náleží do nalezené SSK, použijeme zásobník, do nehož přidáváme vrcholy při vstupu do nich. Po objevení SSK se vrcholy ze zásobníku odebírají, dokud se nenarazí na kořen.

Máme tedy silně souvislé komponenty. Co s nimi? Sloučíme je do jednoho vrcholu a vytvoříme si nový, acyklický graf, tzv. kondenzaci původního grafu. V tomto grafu již stačí otestovat, jestli v něm existuje cesta obsahující všechny vrcholy (důvod je podobný tomu, že v původním grafu je sled se všemi vrcholy). Nový graf se ale nemusí skládat jen z cesty, může obsahovat tzv. dopředné hrany, jež vedou z nějakého vrcholu A do jiného vrcholu, jež je na cestě dále než A. Test, který se pokusí takovou cestu najít a rozhodne o výsledku, může být například nalezení vrcholu, do nějž nevede hrana (ten existuje, máme acyklický graf a musí být právě jeden), a průchod do šířky, při kterém si budeme pamatovat, přes kolik vrcholů jsme již přešli.

Jaká je časová a paměťová složitost algoritmu? Jak již bylo řečeno, Tarjanův algoritmus je modifikované prohledávání do hloubky. Má-li tedy operace zjištění, jestli je prvek v zásobníku, konstantní časovou složitost (což se dá zařídit polem, jehož prvek na místě i určuje, jestli je i-té město v zásobníku), složitost Tarjanova algoritmu vyjde O(N+M). Na následné nalezení vrcholu, do kterého nevede hrana, spotřebujeme opět řádově N+M operací. Složitost prohledávání do šířky nám už hezkou lineární časovou složitost O(N+M) nezkazí. Asymptoticky rychleji úlohu určitě nevyřešíme, nepřečetli bychom ani celý vstup. Algoritmus zabere také jen O(N+M) paměti, takže jsme zachránili husity s pomalými dřevěnými počítači.

Jiné řešení

Celkem elegantní řešení poslal Mirek Olšák. Všiml si, že stačí modifikovat Tarjanův algoritmus, takže si vystačíme pouze s jedním prohledáváním do hloubky. Použijeme následující pozorování: když se vracíme při prohledávání acyklického grafu, jež nám vyrobil Tarjanův algoritmus, z nějakého vrcholu, musí z něj vést hrana do vrcholu, z něhož jsme se vraceli předtím (pro lepší představu si zkuste na chvíli vypustit z grafu cykly). Při návratu z vrcholu tedy uložíme vrchol do nějaké globální proměnné a v každém vrcholu zkontrolujeme, jestli do něj vede hrana. Že graf není polosouvislý, objeví tento algoritmus ve vrcholech, z nichž nevede hrana do žádného dosud neprošlého vrcholu, zkuste si rozmyslet proč.

Nejlépe půjde algoritmus pochopit asi z následujícího pseudokódu vycházejícího z implementace Tarjanova algoritmu na Wikipedii:

Pseudokód

Program

Pavel "Paulie" Veselý

22-3-4 Rukavice (Zadání)

Trošku nás mrzelo, jak málo jste se snažili dokazovat správnost svých řešení. Není vůbec těžké na nějakou strategii přijít, ale vrací taková opravdu požadované, tj. vzhledem k L a P minimální výsledky? K nočním můrám opravovatelů KSP patří divná, složitá a odvážná řešení, která skoro určitě nefungují, ale je třeba přijít na potřebný protipříklad – v případě této úlohy byla ale většina špatných řešení vyvratitelná krátkým kritickým náhledem, kterého byste měli být schopni i sami. Nebojte se nám napsat, že slabinu svého postupu znáte: chápeme, že na dobré řešení není snadné přijít.

Jednoduchý, nesprávný, ale slibný pohled vypadá takto: pokud bych měl jistotu, že z levé truhly vytáhnu od každého páru alespoň jednu rukavici, mohlo by mi stačit z pravé bedny vytáhnout libovolnou. Takovou jistotu však nemohu získat nikdy, protože mi nic nezaručuje, že neexistují pravé rukavice bez levého ekvivalentu (bezlevé): proto budu chtít zajistit, abych z levé bedny vytáhnul alespoň jednu rukavici od každé zastoupené barvy a z pravé vytáhnu tolik rukavic, abych měl jistotu, že mezi nimi bude nějaká, která má v levé bedně souputníka.

Kolik tedy? Inu, pokud necháme Tomáše z pravé bedny vytáhnout tolik rukavic, kolik je tam bezlevých a ještě jednu navíc, nemůže se ani v tom nejhorším případě stát, že by Tomášův výběr obsahoval samé bezlevé pravé rukavice. Podobně pokud v levé bedně vybereme tolik rukavic, kolik jich je tam celkem bez počtu nejméně zastoupeného druhu plus jednu navíc, určitě se nám nemůže stát, že by se v takovém výběru nevyskytovala libovolná varianta. (Rozmyslete si! Proč to musí být „nejméně zastoupeného druhu“?)

Nyní nás může napadnout, že při nahrazení levé bedny za pravou a naopak by nám tento postup mohl vrátit lepší výsledek, kupříkladu kdyby napravo bylo velmi mnoho bezlevých rukavic. Je propočítání obou variant a navrácení té lepší správné řešení?

Ne.

(Přestaňme nyní uvažovat bezlevé a bezpravé rukavice – obecně jejich výskyty stejně nemůžeme řešit jinak, než že jejich počet přičteme k počtu rukavic k vytáhnutí.)

Rozhodli jsme se z jedné bedny vytáhnout zaručeně všechny barvy a z druhé zaručeně jednu, z čehož jsme si logicky odvodili, že získáme jednobarevnou dvojici. Co kdybychom chtěli z levé bedny zaručeně vytáhnout k různých barev a z pravé n-k+1? Dirichletův princip praví, že i pak bychom měli zaručeno, že vytáhneme alespoň jeden stejný pár. Může se pro nějaké k stát, že dosáhneme lepšího výsledku než v krajních případech k=0, k=n? (Uvědomte si, že to jsou přesně dvě možnosti zvažované v odstavci před „Ne.“)

Nejdříve: jak zajistíme vytáhnutí k barev? Stačí vytáhnout počet všech rukavic bez n-k+1 nejméně častých plus jednu navíc, podobně jako jsme to dělali výše. Teď si je třeba rozmyslet, jaký rozdíl v počtu tažených rukavic způsobí přechod od nějakého k ke k+1: z levé bedny budeme muset vytáhnout navíc rukavice (n-k+1)-ní nejméně zastoupené barvy, z pravé naopak nebudeme muset táhnout rukavice k-té nejméně zastoupené barvy. V obecném případě nevíme nic o tom, jestli si tím polepšíme nebo pohoršíme, musíme tedy získat minimum přes všechna k.

No a triviální postup, jak ho získat, je seřadit si počty rukavic jednotlivých barev a pak k projít cyklem. Trvat to bude O(n log n), místa zabereme O(n). Detaily najdete v autorském zdrojáku.

Je to tak správně? Jde si snadno představit, že nastavili-li bychom pro určité množství L rukavic P menší, než jak to děláme, tj. takové, pro které nám Dirichlet už nezaručuje, že vytáhneme dvě opačné rukavice stejné barvy, šel by sestavit výběr rukavic, který skutečně takovou dvojici neobsahuje. Teď je otázka, zda neexistuje L, které jsme nezkoušeli a které dává lepší řešení: počet všech levých rukavic je ostře větší než n, takže jsme těch propočtů přešli docela hodně.

A vtip je v tom, že pro L, které Lk < L < Lk+1 (kde Lk odpovídá počtu levých rukavic, které musíme vytáhnout pro dané k), bude P = Pk, protože jsme oněch L-Lk rukavic vytáhli nadarmo: nezaručili jsme jimi vytažení většího množství barev.

Program

Mária Vámošová & Lukáš Lánský

22-3-5 Reklama (Zadání)

Na začiatku riešenia si dopomôžeme menším trikom. Celú situáciu bodov v rovine otočíme o 45 stupňov proti smeru hodinových ručičiek. To spravíme jednoducho tak, že nahradíme x' = x+y a y' = x-y, a ďalej budeme pracovať už len s týmito transformovanými súradnicami. Teraz platí, že všetky body (x1,y1), ktoré môžu byť spojené s nejakým bodom na súradniciach (x2,y2), musia mať x1 ≤ x2 a y1 ≤ y2 alebo x1 ≥ x2 a y1 ≥ y2.

Najskôr sa zamyslime, čo to znamená, nakresliť čo najmenej čiar, aby obsahovali všetky body. Ak si predstavíme čiaru ako postupnosť úsekov spájajúcich dva body, tak to znamená, že minimum sa dosiahne práve vtedy, keď je celkový počet úsekov všetkých čiar dohromady maximálny.

Jeden úsek čiary je teda spojenie dvoch rôznych bodov p1 = (x1,y1), p2 = (x2,y2) také, že x1 ≤ x2 a y1 ≤ y2. Takéto usporiadané dvojice (p1,p2) bodov budeme ďalej volať pár a množinu párov, v ktorých každý bod vystupuje maximálne 2 krát (raz ako p1 a raz ako p2), budeme volať párovanie, ktorého veľkosť sa snažíme maximalizovať.

Na ďalšie uvažovanie si úlohu trocha preformulujme: Sú dané dve množiny bodov S a P, pričom S obsahuje kópie bodov, ktoré môžu vystupovať v párovaní ako body p1 a P obsahuje kópie bodov, ktoré môžu vystupovať v párovaní ako body p2.

Pochopiteľne, naša pôvodná úloha je špeciálnym typom tejto preformulovanej úlohy, keď S = P = { pôvodné body }.

Ak si množiny S a P predstavíme ako partity bipartitného grafu, kde každý korektný pár reprezentujeme hranou medzi príslušnými dvoma vrcholmi v S a P, potom veľkosť najväčšieho párovania vieme nájsť pomocou obecného algoritmu na hľadanie maximálneho bipartitného párovania. O tomto algoritme si môžete prečítať viac na anglickej Wikipedii alebo na stránkach Martina Mareše a za jeho použitie ste mohli získať maximálne 10 bodov.

K lepšiemu algoritmu bolo nutné učiniť dôležité pozorovanie: označme bod p = (x0,y0) ∈P ako bod množiny P s najväčšou y-ovou súradnicou (a spomedzi tých s najmenšou x-ovou súradnicou). A skúmajme, s ktorými bodmi v S môže tvoriť pár v nejakom optimálnom (maximálnom) párovaní.

Pre všetky body, s ktorými môže tvoriť pár, platí x ≤ x0 a y ≤ y0. Keďže p je bod s maximálnou y-ovou súradnicou, dostávame, že to môže byť ľubovoľný bod, spĺňajúci podmienku x ≤ x0. Ak žiaden takýto bod neexistuje, potom je samozrejmé, že v žiadnom optimálnom riešení nie je tento bod spárovaný. Inak označme bodom q = (x1,x2) ∈S bod s maximálnou y-ovou súradnicou spĺňajúci x1 ≤ x0 a ak je takých viac, tak spomedzi tých bod s najväčšou x-ovou súradnicou.

Ukážeme, že existuje optimálne riešenie, keď je bod p spárovaný s bodom q.

Nech existuje ľubovoľné optimálne riešenie, v ktorom to neplatí. Potom môžu v tomto párovaní nastať len tieto situácie:

Vidíme, že nič nepokazíme, keď bod p spárujeme s bodom q. Vykonaním tohto kroku sme si vlastne zredukovali náš problém veľkosti N na problém veľkosti N-1. Pretože bod p už nemôže vystupovať v žiadnom párovaní, môžeme ho z množiny P odstrániť a rovnako bod q odstrániť z množiny S. A na nový problém použijeme rovnaký algoritmus.

Jednoduchým aplikovaním uvedeného postupu, keď N-krát opakovane nájdeme bod s maximálnou súradnicou y v čase O(N) a k nemu príslušný bod q tiež v O(N), dostávame kvadratický algoritmus, za ktorý ste mohli získať 12 bodov.

Na finálny vzorový algoritmus bolo nutné trocha zmeniť pohľad na úlohu.

Začneme body v množine P prechádzať v poradí rastúcej x-ovej súradnice (a body s rovnakým x podľa y-ovej súradnice). Pričom vždy, keď navštívime bod, určíme, s ktorým bodom v množine S bude spárovaný. Za týmto účelom si budeme pamätať množinu Q ⊆ S doteraz nespárovaných bodov.

Budeme sa pri tom riadiť pravidlom, že aktuálny bod p = (x0,y0) ∈P spárujeme s bodom q = (x1,y1) ∈Q, ktorý má zo všetkých bodov v Q najväčšiu y-súradnicu, avšak menšiu ako y0. Ak takýto bod neexistuje, tak bod p zostane bez páru. Následne odstránime z množiny Q bod q a zaradíme tam bod p.

Treba však ukázať, že takýto algoritmus vedie k optimálnemu riešeniu, teda najmenšiemu počtu nutných čiar.

Pri tomto spracovávaní platí invariant, že v každom kroku existuje optimálne párovanie, ktoré páruje spracované body P rovnako, ako sme to spravili my.

Ak takýto invariant platí v kroku n, potom spárovanie bodu p s bodom q nám takýto invariant nepokazí a bude platiť aj v kroku n+1. Pretože v tomto optimálnom riešení, ktoré spárovalo prvých n bodov množiny rovnako ako my, môžu nastať len situácie rovnaké ako rozoberané situácie v našom kvadratickom algoritme. Teda spárovaním p s q zachováme invariant o existencii optimálneho riešenia.

Algoritmus sa dá efektívne implementovať tak, že na začiatku si utriedime body P v čase O(N log N) a pri spracúvaní si budeme množinu Q udržiavať v utriedenom poradí podľa súradnice y, napr. pomocou vyvažovaného binárneho stromu, čím dokážeme v čase O(log N) hľadať v tejto množine bod, ktorý má najväčšiu súradnicu menšiu ako dané y0 a v tomto čase tiež vymazať bod q s Q a vložiť tam bod p.

Šikovnejšiu implementáciu dostaneme, ak si všimneme, že bod p sa vkladá na rovnaké miesto v utriedenej množine Q, z ktorého bol vymazaný bod q (ak existoval). Alebo ak neexistoval, tak vloženie sa uskutočňuje vždy na koniec, čím sa nám ponúka jednoduchá možnosť udržiavať si množinu Q v poli a na ňom hladať požadovaný prvok binárnym vyhľadávaním.

Pamäťová zložitosť je O(N), stačí si nám pamätať len prvky P a množinu Q.

Poučenie na záver: Táto úloha spadá do kategórie „Greedy algoritmy“ alebo tiež „hladové“. V týchto úlohách platí, že v každom kroku máme možnosť vykonať operáciu, ktorá nám zaručene nezabráni nájsť optimálne riešenie, čo implikuje, že ak takú operáciu spravíme v každom kroku, dostaneme optimálne riešenie,

V tomto prípade to bolo operácia spárovania bodu s maximálnou y-ovou súradnicou.

Pri týchto úlohách je však vždy nutné overiť, či náš krok je skutočne tým, ktorý nám našu cestu k optimálnemu riešeniu neodstrihne a či máme možnosť nejakú takúto operáciu spraviť v každom kroku.

Program

Peter Ondrúška

22-3-6 Kolejní výtahy (Zadání)

V této sérii byla leckterá úloha pořádně vypečená, jednoduchost jsme skryli právě do praktické úložky.

Ochotu jednotlivých studentů, kteří chtějí vyjet nahoru výtahem, můžeme chápat jako intervaly na celočíselné ose od 1 do n, kde n je výška kolejí. Některé intervaly se mohou překrývat, a našim cílem je vybrat takovou množínu čísel, že pokryjeme všechny intervaly. Počet intervalů označme k.

Pojďme na to od lesa. Tedy … od začátku. První student (tedy ten, který je ochoten vystoupit v nejnižším patře) bude muset někde vystoupit, ale může zastavit tak, aby pomohl více lidem. Moc nového jsme se nedozvěděli. Co když se ale podíváme na prvního studenta, který musí vystoupit – jehož konec intervalu je ze všech konců nejblíže 1. Víme, že tohoto studenta musíme někde z výtahu vystrčit, ale navíc víme, že to klidně můžeme učinit právě na tomto místě.

Můžeme to udělat proto, neboť jsme ho chytře vybrali – může se stát, že jeho interval protíná intervaly jiných studentů, avšak žádný z těch, kdo s jeho intervalem ochoty mají průnik, ještě nemusí vystupovat – jinak řečeno, všichni takoví mohou vystoupit právě v tomto patře.

Necháme tedy z výtahu odejít všechny studenty, kteří jsou na konci intervalu prvního studenta ochotni. A máme základ algoritmu! Zbytek dořešíme obdobně – nalezneme dosud neprobraného studenta, jehož konec intervalu je nejblíže poslednímu místu, a necháme s ním vystoupit všechny ostatní, kteří jsou v tom patře ochotni.

Pokud na začátku algoritmu data setřídíme podle konců intervalů (v čase O(k log k)), zbytek dořešíme se složitostí O(k) a celkově to tedy stihneme v čase O(k log k).

Máme za sebou složitost, ale je algoritmus správně? Postupem výše zmíněným určitě dojdeme k nějaké korektní posloupnosti zastávek, nemusí nám být ale zcela jasné, že taková posloupnost je minimální. Podívejme se na posloupnost intervalů, které jsme vždy vybrali jako další „koncové“, a označme její velikost p. Protože jsme na každém konci poslali z výtahu všechny studenty, kteří vystoupit mohli, tyto intervaly jsou disjunktní. Tím pádem každé přípustné rozložení zastávek musí zastavit alespoň p-krát – na každém intervalu alespoň jednou. Nícméně p je právě počet zastávek, které vykonal náš algoritmus, a výsledek je tedy vskutku optimální. Howgh.

Tím skončíla indiánská část řešení. Ještě zmíníme, že pokud si nakreslíme jednotlivé intervaly na reálnou osu a budeme se na tuto strukturu dívat jako na graf (intervaly = vrcholy a dva vrcholy jsou spojeny hranou, protínají-li se dva intervaly), dostaneme speciální typ grafu, jménem „průnikový graf“. Takovéto grafy (nejen přímkové) jsou často studovány v teorii grafů a již se o nich leccos ví, například že leckteré „těžké“ problémy pro obecné grafy na nich lze vyřešit v polynomiálním čase.

Program

Martin Böhm

22-3-7 Pavouci internetu (Zadání)

Přehled

V našem vzorovém řešení je situace mírně komplikovaná – dohadují se mezi sebou 3 druhy procesů. Podívejme se tedy napřed na jednodušší situaci, kdy nic nepadá. Jak bude vypadat pracovní cyklus?

Klient si vybere server a zadá mu práci, počká na potvrzení o jejím přijetí. Někdy mezi tím se někde jinde objeví pracující proces a připojí se také na server. Když se tedy na serveru sejdou oba, server je seznámí – předá práci pracujícímu procesu, společně s PID toho, kdo ji zadal. Více se o ně nestará. Pracující provede zadaný úkol, odešle výsledek (přímo zadávajícímu, nikoliv přes server) a znovu se přihlásí na server. Mezitím server seznamuje další pracující s prací. Zatím jednoduché?

Jak je ale řešené, když se pracující přihlásí na jiný server, než na který je uložen úkol? Servery mezi sebou komunikují také. Ve chvíli, kdy na některém serveru dojde k přebytku libovolného druhu (přebývají buď pracující a nebo úkoly), oznámí to server všem ostatním. Ti si buď řeknou o přesun pracujícího nebo nabídnou svého pracujícího. Tomu je poté sděleno, aby se připojil na onen jiný server.

Jak budeme řešit havárie? Podívejme se na jednotlivé části podrobněji.

Zadávání

Když chceme zadat úkol, spustíme nový proces. Jeho úkolem bude sledovat, co se s úkolem kde děje.

Ten se pokusí odeslat práci prvnímu serveru z nastavení. Bohužel, ten nemusí běžet, proto čekáme na odpověď jen nějakou dobu. Pokud ale běží, linkne si náš proces a příjem potvrdí.

Ve chvíli, kdy máme potvrzení o přijetí, čekáme na přiřazení. Až server najde vhodného pracujícího, dá nám o tom vědět (a také jeho PID). My si ho linkneme a budeme čekat na odpověď od něj (a serveru už si nebudeme všímat, co se s ním děje, je nyní nezajímavé).

Když přijde výsledek, vše proběhlo, jak mělo, my můžeme poslat výsledek do původního procesu a spokojeně skončit.

Pokud se nedočkáme odpovědi od serveru, zkusíme další server v seznamu a s ním provádíme totéž. Jestliže selže cokoliv dalšího (server či pracující umře, když čekáme na něco od něj), tak začneme zcela od začátku – od prvního serveru a v novém procesu. (Kdo si má pamatovat, co všechno by bylo potřeba unlinknout? Navíc, pokud by některý server žil, ale nestihl odpovědět včas, pak by měl uloženou naši práci – skončením ji u něj zrušíme.)

Pracující

Každý pracující má dvě vývojová stádia. První stádium je čekající. Podobným způsobem jako klient se pokusíme spojit se serverem (tedy, pošleme mu své PID a on buď odpoví, že nás bere, nebo, když se nedočkáme odpovědi, zkusíme další server). Až nás některý přijme, tak si nás linkne a my jen budeme poklidně čekat, až nám přidělí nějakou práci.

Až nějakou dostaneme, tak si nás unlinkne server, ale linkne si nás klient. My práci pustíme, ale to uděláme v novém procesu (samozřejmě, také s námi slinkovaném) a čekáme na výsledek. Až skončí, pošleme výsledek klientovi, sami se pokusíme znovu přihlásit k serveru, ale to opět v novém procesu (abychom zničili všechny stará spojení).

Nyní, co se může stát? Když spadne proces s prací, který ale běží na stejném stroji, jako my, znamená to, že je v něm chyba. Nahlásíme to tedy klientovi a práci považujeme za splněnou. Obdobně když se nedočkáme výsledku v požadovaném čase (ale předtím proces s prací ukončíme).

Pokud spadne buď server nebo klient, pak jen ukončíme případnou probíhající práci a zkusíme se opět na některý server připojit. To je zcela v pořádku – pokud spadl server (a my se o tom dozvěděli), pak ještě nemáme žádnou práci a nic se neztratí. Jediný případ, kdy zničíme nějakou práci, je, když umře klient, ale v tom případě není komu poslat výsledek, je tedy zbytečná.

A co když umřeme my? Buď se tak stalo ještě před připojením na server a v tom případě to nezpůsobí žádnou škodu. A poté až do dokončení práce s námi je vždy někdo slinkovaný, takže se o tom dozví a může provést nápravná opatření (v případě serveru si nás jen smazat, v případě klienta zadat práci znovu, někomu živějšímu).

Server

Nyní, co dělá server? Na chvíli si odmysleme poněkud krkolomné předávání pracujících procesů. V tom případě je celý server velmi jednoduchý. Sbírá úkoly a pracující procesy, ve chvíli, kdy se sejde od každého jeden, tak je spáruje a dál se o ně nestará.

Po dobu uložení úkolu i pracujícího procesu je s ním prolinkován. Ve chvíli, kdy druhý konec spadne, smaže si jej ze seznamu (nefungující pracující je k ničemu, práce pro neexistující proces je zbytečná). Když spáruje požadavek s pracujícím, tak je oba unlinkne – pro server jsou již nezajímají, vyřídí si vše mezi sebou.

Co když spadne server? Potom se o tom dozvědí všichni klienti i všichni pracující. Pracující se jen přepojí na jiný server a klienti pošlou práci znovu, někam jinam.

Předávání pracujících

Není problém se dohodnout, že někdo jiný potřebuje pracujícího – stačí si navzájem posílat zprávy o tom, že se jedna z množin stala neprázdnou. Problémem je, jak pracujícího předat bezpečným způsobem. Aby se někde „neztratil cestou“, je potřeba, aby s ním vždy byl někdo prolinkovaný, a pokud cestou umře, říct si o nového.

Napřed se tedy dva servery, které si ho předávají, nalinkují spolu a dohodnou si předání. Přijímající server si nalinkuje pracujícího a potvrdí předávajícímu, ten ho v tuto chvíli může unlinkovat a říci mu, aby se přesunul. Pracující se připojí na nový server a přesun je hotový.

Co může spadnout? Inu, cokoliv. Když spadne pracující, dozví se o tom přijímající server (linkne si ho) a může požádat o nového. Když umře přijímající server při dohadování, dozví se o tom předávající. V tom případě nic neodešle (není komu). Nakonec, může umřít i předávající, o tom se ovšem dozví přijímající a nebude tedy čekat na pracujícího. (Kdyby náhodou přišel, tak se nic zlého nestane, přijmeme ho tak jako tak. Pokud nepřijde, stejně si od mrtvého serveru nemůžeme vyžádat nového.)

Program

Michal "vorner" Vaner