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

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

Řešení úloh

• 25-2-1: Vytíženost dopravy
• 25-2-2: Sekání trávy podruhé
• 25-2-3: Doplňování operátorů
• 25-2-4: Organizace vykládky
• 25-2-5: Sbírání papírů
• 25-2-6: Optimalizace v redakci
• 25-2-7: Zaléváme dokument

Čokolády

Oproti první sérii, ve které získali čokoládu jen 4 řešitelé, se v této sérii roztrhl s čokoládami pytel. Pro tuto sérii jsme čokoládu rozdávali za vyřešení některé ze tří nejvíce bodovaných úloh na plný počet bodů. Tedy buď za 25-2-1 Vytíženost dopravy, 25-2-4 Organizace vykládky (CodExová úloha), nebo za 25-2-7 Zaléváme dokument (seriál).

Jen za CodEx získalo čokoládu 10 lidí. Celkem pak čokoládu dostává 11 z vás. Gratulujeme a užijte si sladkou odměnu.

---

25-2-1 Vytíženost dopravy (Zadání)

---

Na tuto úlohu přišla spousta vašich řešení. Jedním z největších problémů některých z vás se ale ukázalo být to, jak správně rozdělit čas mezi předvýpočet a mezi odpovědi na dotazy. Zaveďme značení N pro počet zastávek (vrcholů našeho stromu) a K pro počet dotazů.

Správné rozdělení času

Zamysleme se nejdříve nad dvěma extrémy: Pokud bychom očekávali malý (konstantní) počet dotazů, bylo by asi nejlepší odpověď pro každý dotaz vyhledat samostatně (třeba jednoduchým procházením do šířky – BFS) a zabralo by nám to čas O(N) na dotaz a O(N) celkem. Druhým extrémem by bylo K≥ N². V takovém případě si můžeme předvypočítat pomocí BFS cesty z každé zastávky na každou v O(N²) a odpovídat pak už jen v konstantním čase na dotaz. Tím se dostaneme na celkovou složitost O(N² + K).

My jsme se ale zabývali nejzajímavějším případem, a to když K je řádově stejně velké jako N. Pak je druhý postup příliš pomalý. Ukážeme si, jak udělat předvýpočet v čase O(N log N) a odpověď na dotaz v čase O(log N).

Lehčí varianta

Nejdříve se zamyslíme nad lehčí variantou s pouhou cestou. To je jako situace přímo stavěná pro maximové intervalové stromy. Intervalový strom je stromová struktura postavená nad nějakou posloupností, která je schopná vracet hodnotu (součet, maximum a podobně) v nějakém intervalu. Dělá to tak, že kořen drží hodnotu celé posloupnosti, jeho synové hodnotu levé a pravé poloviny a tak dále, až na úroveň jednotlivých prvků posloupnosti.

Každý interval jsme pak schopni poskládat z maximálně log N menších intervalů zastoupených vrcholy a dotaz na intervalový strom tedy trvá O(log N), strom se dá vystavět v lineárním čase. Toť řešení jednodušší varianty. Pokud si chcete přečíst něco více, podívejte se do naší kuchařky o intervalových stromech.

Složitější varianta

Nyní se pokusíme některé myšlenky intervalových stromů zobecnit, aby fungovaly nejenom na graf tvaru cesty. Strukturu ale nebudeme potřebovat aktualizovat, stačí nám ji pouze jednou vybudovat a pak nad ní pokládat dotazy. Tím se bude lišit od intervalových stromů, které umožňují rychle provádět i aktualizace.

Zakořeníme si naši grafovou síť zastávek v libovolném vrcholu a postavíme strom. Ve chvíli, kdy dostaneme dotaz na úsek A-B, můžeme ho složit (vzít maximum) z dotazů na úseky A-P a L-P, kde P je společný stromový předchůdce obou vrcholů (tedy nejvýše umístěný vrchol, přes který cesta z A do B musí jít). K rychlému hledání P se vrátíme později.

Tím jsme si problém zredukovali na nalezení maxima nějaké vertikální cesty ve stromě. To bychom mohli udělat tak, že bychom jí celou prošli, ale to může trvat až lineárně dlouho vzhledem k N (například v grafu tvaru cesty). My bychom ale chtěli dosáhnout času O(log N). Zaveďme si tedy v každém vrcholu zpětné odkazy různých úrovní. Zpětný odkaz úrovně 0 bude odkaz na otce, zpětný odkaz úrovně 1 bude odkaz na otce otce (tedy o 2 výš) a obecně zpětný odkaz úrovně m povede o 2^m vrcholů výše. Takových zpětných odkazů bude v každém vrcholu maximálně log n a každý si navíc bude pamatovat maximum na úseku, který pokrývá.

Když budeme chtít vystoupit od A k P, dokážeme tento úsek pokrýt jen pomocí těchto zpětných odkazů a použijeme jich jen O(log N) (jednoduchým argumentem: když budeme skákat po největším možném zpětném odkazu, tak každým skokem zmenšíme vzdálenost alespoň o polovinu). Obdobně úsek od B k P. Pokud tedy dostaneme takovouto strukturu, dokážeme odpovědět na libovolný dotaz v O(log N).

Teď se vrátíme ke slibovanému hledání P. V každém vrcholu si budeme pamatovat, v jaké je hloubce, a budeme stoupat od A a B zároveň. Nejdříve vystoupáme po zpětných odkazech z toho hlubšího do stejné hloubky (v O(log n) krocích) a pak zkoušíme stoupat z obou vrcholů naráz. Vezmeme postupně všechny délky zpětných odkazů (od největších po nejmenší) a když se přes takto dlouhé zpětné odkazy ještě nedostaneme do stejného vrcholu (mohl by to totiž být až nějaký předchůdce P), vystoupáme po nich. Tímto nalezneme snadno P a současně si nerozbijeme logaritmickou délku cest od A a od B k P.

Jak si takovou strukturu rychle pořídit? To už je jednoduché. Zakořenění stromu můžeme udělat pomocí prohledávání do hloubky od libovolného vrcholu, to nám zabere lineárně kroků. V každém vrcholu pak zkonstruujeme maximálně log N zpětných odkazů a s využitím předchozích odkazů nám každý nový odkaz zabere jen konstantní čas. Vzdálenost od A k B překlenutá zpětným odkazem délky 2^m je totiž překlenutá dvěma zpětnými odkazy: od A k C délky 2^m-1 a od C k B délky také 2^m-1. Když vezmeme z těchto dvou odkazů maximum, máme maximální počet cestujících i na zpětném odkazu délky 2^m.

V každém vrcholu tedy strávíme O(log N) a celou strukturu zvládneme vystavět v O(N log N). Celkově předvýpočet i odpověď na K dotazů trvá O((N+K) log N), což je ideální.

Program (C++)

Jirka Setnička

Heavy-light dekompozice

Datová struktura z našeho vzorového řešení má jednu nevýhodu: pro strom na N vrcholech zabere řádově N log N buněk paměti. Načrtneme ještě jeden způsob, jak úlohu vyřešit, který si vystačí s lineární pamětí. Použijeme k tomu takzvanou heavy-light dekompozici stromu neboli rozklad stromu na lehké a těžké hrany.

Strom zakořeníme a pro každý vrchol v spočítáme T(v), což bude počet vrcholů v podstromu, jehož kořenem je v. Za těžké prohlásíme ty hrany, které vedou z nějakého vrcholu v do jeho syna w, přičemž T(w) > T(v)/2. Všechny ostatní hrany budou lehké. Dobře je to vidět na následujícím obrázku (čísla udávají velikosti podstromů, těžké hrany jsou nakresleny tučně):

Povšimneme si, že z každého vrcholu může dolů vést nejvýše jedna těžká hrana. Těžké hrany proto tvoří cesty, kterým budeme říkat těžké cesty a jejich nejvyšším vrcholům stopky cest. Pokud stopka cesty není kořen, vede z ní nahoru lehká hrana, která ji napojí na nadřazenou těžkou cestu (ta ovšem může být triviální – jednovrcholová).

O lehkých hranách platí jiná zajímavá věc: kdykoliv se vydáme z kořene do listu, projdeme po nejvýše  log₂ N lehkých hranách. To proto, že kdykoliv projdeme po lehké hraně, velikost podstromu, v němž se nacházíme, klesne alespoň na polovinu.

Teď popíšeme, jak pomocí naší dekompozice hledat nejbližšího společného předchůdce dvou vrcholů. Stačí si pro každou těžkou cestu zapamatovat pole všech vrcholů, které na ní leží, a naopak si pro každý vrchol zapamatovat, na jaké těžké cestě leží a kolikátý v pořadí je.

Když nám nyní někdo zadá vrcholy x a y, půjdeme z nich do kořene a podíváme se, kde se obě cesty poprvé potkaly. Do kořene přitom vyskáčeme tak, že pokaždé určíme stopku těžké cesty, na níž se nacházíme, a z té vystoupíme po jedné lehké hraně. To může nastat nejvýše O(log N)-krát a pokaždé nás to stojí konstantní čas.

Podobně zvládneme hledání maxim na cestách. Pro každou těžkou cestu postavíme intervalový strom, pomocí kterého budeme umět rychle nalézt maximum v libovolném úseku cesty.

Kdykoli nám pak někdo zadá cestu z x do y, rozdělíme ji na úsek z x nahoru do nejbližšího společného předchůdce a úsek z něj dolů do y. Stačí tedy umět počítat maxima pro „svislé“ cesty ve stromu. Každá svislá cesta ovšem obsahuje O(log N) lehkých hran; těmi jsou spojeny úseky těžkých cest, takže úseků musí být také O(log N).

Pro každou těžkou cestu se zeptáme příslušného intervalového stromu, jaké je maximum z příslušného úseku, a vypočteme maximum z těchto maxim a z ohodnocení lehkých hran spojujících těžké úseky. To dává celkem O(log N) dotazů na intervalové stromy, z nichž každý trvá O(log N). Dohromady O(log ² N), což je příliš.

Učiníme tedy ještě jedno pozorování: skoro všechny dotazy, které intervalovým stromům klademe, se týkají intervalů od nějakého vrcholu těžké cesty k její stopce. Jedinou výjimku tvoří nejvyšší cesta, na kterou se zeptáme. Můžeme si tedy navíc pro každou cestu předpočítat maxima úseků od stopky do ostatních vrcholů. Pak položíme O(log N) dotazů trvajících O(1) a jeden trvající O(log N). To je dohromady O(log N) na celé nalezení maxima cesty z x do y.

Celá struktura nám přitom zabere O(N) buněk paměti a jsme ji schopni vystavět v lineárním čase.

Dodejme ještě, že trochu složitější struktury tohoto druhu jde i aktualizovat. To si ale necháme na jindy; pokud jste zvědavi, zkuste si najít něco o Sleatorových-Tarjanových stromech, známých také pod názvem Link-Cut Trees.

Martin „Medvěd“ Mareš

---

25-2-2 Sekání trávy podruhé (Zadání)

---

Řešení této úlohy je krátké, jednoduché, ale je třeba uznat, že i nemálo trikové. Pro úplnost zadání budeme předpokládat, že startovní políčko již je posekané. Pak má vyhrávající strategii první hráč. A jaká tedy bude jeho strategie?

Hrací plocha se skládá ze sjednocení obdélníků se sudým obsahem. Tedy alespoň jeden z rozměrů každého obdélníku je sudý. Tedy je možné celý herní plán vyskládat dominovými kostkami. Jak se to přesně udělá, si každý jednoduše rozmyslí.

Nyní k samotné strategii. Hráč jedna začíná na nějaké poloposekané dominové kostce. Tak jediné, co udělá, je, že přejde do druhé části této kostky. Nyní druhý hráč buď už nemůže nikam táhnout, nebo přejde do jiné dominové kostky. Tato kostka zatím nebyla použita, a tedy má volnou druhou půlku. Takže první hráč zas jen přejde do druhé poloviny. Tuto strategii bude opakovat až do doby, kdy druhý hráč nebude mít kam táhnout.

Na závěr ještě poznamenejme, že obecně se této taktice říká Párovací strategie a funguje ve všech grafech, které mají perfektní párování (tj. vrcholy grafu lze rozdělit do dvojic, kde každá dvojice je spojena hranou).

Karel Tesař

---

25-2-3 Doplňování operátorů (Zadání)

---

---

25-2-4 Organizace vykládky (Zadání)

---

V této praktické úloze byly vstupy rozděleny do čtyř sad podle očekávané efektivity řešení.

Hledaný součet vzdáleností od daného bodu ke všem ostatním v maximové metrice nazveme cenou vykládky pro daný bod. Nejjednodušším řešením úlohy je přímý výpočet ceny vykládky pro každý bod tak, že projdeme všechny ostatní body a sečteme vzdálenosti podle vzorečku. Takové řešení má časovou složitost O(N²) a stačilo pro vyřešení prvních dvou sad.

Ve druhé sadě se hodnoty nevlezly do 32-bitových proměnných, museli jste tedy použít 64-bitové celočíselné typy. Co jsem do úlohy nevkládal, ale doporučuji k promyšlení (a nejlépe i naprogramování), je případ, kdy by se čísla nevlezla ani do 64-bitových proměnných a váš jazyk by nepodporoval celočíselné typy s dynamickou délkou. A jak byste postupovali, pokud by čísla nebylo potřeba pouze sčítat a porovnávat, ale provádět i další operace jako například násobení a dělení?

Ve třetí sadě již byl počet zadaných bodů vysoký (N≤ 100000), ale počet navzájem různých bodů byl stále nízký (K≤ 1000). Taková situace se dala vyřešit seskupením shodných bodů do jediného bodu, u kterého byla udána jeho násobnost. Lze to provést třeba setříděním bodů (nejpřirozenější způsob je asi lexikografický – nejprve podle souřadnice x, v případě shody podle souřadnice y).

Setřídění vede k tomu, že se shodné body umístí v poli na souvislém úseku. Pak lze pole projít a pro každý bod zkontrolovat, zda je shodný s předchozím prvkem pole. V případě shody je zvýšena násobnost naposledy přidaného bodu, v opačném případě je přidán nový bod. Protože má (rozumné) třídění časovou složitost O(N log N), je výsledná časová složitost O(N log N + K²). (Použitím vyhledávacích stromů lze docílit O(N log K + K²), což ale není příliš atraktivní vylepšení.)

Efektivní řešení

Problém dosavadního přístupu tkví v tom, že kvůli nepříjemné formuli pro vzdálenost mezi dvěma body nedokážeme cenu vykládky počítat nějak hromadně. Možností, se kterou jsem původně počítal, je zametat body podél y-ové souřadnice a vhodně si v intervalových stromech udržovat body tak, aby se daly efektivně pro zpracovávaný bod spočítat 4 součty – součty souřadnic všech bodů, pro které se bude: přičítat a odečítat x-ová souřadnice a přičítat a odečítat y-ová.

Asymptoticky stejně efektivní, ale jednodušší je použít trik převzatý z řešení Ondry Hübsche. Trik spočívá ve využití vztahu

ověřte si jej například rozborem případů. Vzdálenost dvou bodů d=max(|x₁-x₂|,|y₁-y₂|) pak můžeme zapsat jako

Budeme pracovat s novými souřadnicemi u a v, které vzniknou jako:

Vzdálenost dvou bodů nám pak bude vycházet jako

Celou dobu budeme počítat dvojnásobné vzdálenosti a pouze na konci výsledek vydělíme dvěma.

Jaká je výhoda tohoto převodu? Zbavili jsme se nepříjemné operace maxima. Součet už dokážeme počítat efektivně, provedeme to ve dvou krocích – oddělíme |u₁-u₂| a |v₁-v₂|. V prvním kroku setřídíme body vzestupně podle souřadnice u a spočítáme si prefixové součty pro toto setříděné pole. Pro aktuálně zpracovávaný prvek p pole je pak |u_p-u_i|=u_p-u_i pro všechny prvky i před ním a |u_p-u_i|=u_i-u_p pro prvky za ním.

S prefixovými součty dokážeme započítat všechny body do ceny vykládky pro bod p v konstantním čase. (Pole P prefixových součtů je takové pole, které na i-té pozici obsahuje součet prvních i prvků. Dokážeme jej předpočítat v lineárním čase pomocí vztahu P[i]=P[i-1]+Q[i], kde Q je původní pole. Součet prvků na pozicích k až l je pak P[l]-P[k-1].)

Analogicky postupujeme pro souřadnici v. Nyní máme pro každý bod spočtenou cenu vykládky a stačí vybrat nejmenší z nich. Jedinou složitější operací je třídění, ostatní operace jsou pouhé lineární průchody. Časová složitost řešení je tak O(N log N), paměťová O(N).

Program (C++) – N kvadratický

Program (C++) – K kvadratický

Program (C++) – N log N

Lukáš Folwarczný

---

25-2-5 Sbírání papírů (Zadání)

---

Než se vrhneme na řešení úlohy, učiňme několik stěžejních pozorování. Ta nám už řešení úlohy dají takřka zadarmo.

Novinářka se nesmí vracet dolů. Tím pádem před přechodem na další řádek (nahoru) musí vybrat všechny papíry na řádku.

Zároveň nemá smysl uvažovat jiné papíry než ten nejvíce vlevo a vpravo. Všechny ostatní papíry totiž novinářka sebere automaticky při pohybu mezi nimi.

Dále je důležité uvědomit si, že po sebrání posledního papíru nemá smysl se na tomto řádku dále pohybovat. Stejné kroky totiž lze provést o řádek výše s výsledkem přinejhorším stejným (na aktuálním řádku už žádný další papír nesebereme).

Musíme ještě vyřešit, jak se na řádku pohybovat. Označme si index papíru položeného nejvíce nalevo l a index toho nejvíce napravo r. Index políčka, na které vstupujeme při přechodu na řádek, označme c. Nyní nastávají tři možnosti.

l ≥ c Nemá smysl se pohybovat jinak než pořád doleva. r ≤ c Nemá smysl se pohybovat jinak než pořád doprava. l < c < r Můžeme jít nejdříve k l a následně k r. Také je možné jít nejdříve k r a poté k l. Obě varianty mohou dát jinou délku cesty.

V tuto chvíli mnoho z řešitelů sáhlo po hladovém algoritmu. Tedy vždy se podívat, zda je výhodnější z c jít nejdříve do l a až poté do r, nebo opačně. Následně lepší z výsledků vzít jako součást řešení a pokračovat stejným způsobem na řádku výše. Tento postup je však chybný. Zkuste si ho například odsimulovat na následujícím vstupu:

3 8
Řádek 3: 0 1 0 0 0 0 0 0
Řádek 2: 0 1 0 0 0 0 0 1
Řádek 1: 0 0 1 0 0 0 0 0

Z toho plyne, že je třeba počítat s oběma variantami průchodu řádkem a obě si uložit. Všech možných cest je tak sice exponenciálně mnoho, lze ale využít přístupu z dynamického programování a ukládat si mezivýsledky.

Buďme v nějakém řádku i. V řádku i-1 jsme dostali dvě optimální řešení. Jedno pro l_i-1 a jedno pro r_i-1. Pro spočítání řešení v l_i tedy vyzkoušíme oba z výsledků pro předchozí řádek a lepší z nich si uložíme. Totéž provedeme pro r_i, čímž dostaneme opět dvě možné varianty. V posledním řádku pak z těchto dvou variant vybereme tu s kratší délkou cesty.

Speciálním případem je první řádek, a to v tom, že musíme vždy dojít do r₁ a optimální řešení je zde tak pouze jedno (o délce r₁). V programu toto snadno ošetříme.

Že je řešení správné si lze snadno rozmyslet přes matematickou indukci. Řešení pro první řádek je indukčním předpokladem. Řešení pro i-tý řádek pak indukčním krokem.

Ještě však nekončíme. Jelikož chceme také zpětně rekonstruovat cestu, musíme si navíc ukládat pole předchůdců a směry pohybu. Pak lze již cestu rekonstruovat. Směr pohybu se navíc bude měnit pro řádek maximálně dvakrát, tedy paměťová složitost uložení cesty je O(N). Taková je i paměťová složitost celého algoritmu, jelikož není třeba ukládat si celou matici. Pozorní čtenáři si jistě dokážou rozmyslet proč.

Ke zjištění indexů l a r pro každý řádek stačí jednou matici v O(NM) projít. Následná dynamika nám zabere O(N) kroků, tedy celková časová složitost je lineární – O(NM).

Zdrojový kód je z větší části přepisem programu Rastislava Rabatina. Děkujeme.

Program (C++)

Jan Bok

---

25-2-6 Optimalizace v redakci (Zadání)

---

Naším úkolem je pro každou hranu zadaného ohodnoceného grafu určit, zda se vyskytuje ve všech, v pouze některých, nebo v žádných minimálních kostrách. K řešení využijeme upravený Kruskalův algoritmus. Z kuchařky budeme potřebovat především poznatek o jeho správnosti a také poznatek o tom, že v případě více hran stejné váhy může být pořadí zpracování hran libovolné (algoritmus může vydat různé kostry, ale všechny budou minimální).

Popis algoritmu

Algoritmus si bude, stejně jako ten původní, budovat les T – část výsledné kostry. Hrany stejné váhy w_k budeme zpracovávat najednou. Hranu, jejíž oba vrcholy leží v jedné komponentě, rovnou označíme za hranu, která se v žádné minimální kostře nevyskytuje, a dále s ní nepracujeme.

Pro ostatní hrany rozhodneme, zda se vyskytují ve všech, nebo jen některých minimálních kostrách. Ve skutečnosti zjistíme, zda Kruskalův algoritmus hranu (v závislosti na pořadí zpracování) přidá vždy, nebo jen někdy. Později dokážeme, že je obojí ekvivalentní.

Uvažme pro tento účel graf G, který vznikne tak, že do T vložíme všechny hrany váhy w_k. Pokud se odebráním hrany e (váhy w_k) z grafu G sníží počet komponent, přidal by algoritmus hranu ve všech případech, neb nemá jinou hranu téže váhy, jíž by spojil příslušné komponenty. Pokud se naopak počet komponent nezmění, existuje další hrana, kterou lze použít místo e.

Hrana, po jejímž odebrání vzroste počet komponent grafu, se nazývá most. Algoritmus na hledání mostů je detailně popsán v kuchařce o grafech, zde si jej popíšeme pouze stručně. Upravíme algoritmus průchodu do hloubky (DFS) tak, aby u vrcholů počítal tzv. hladinu. Graf si zakořeníme, pro lepší představu umístíme kořen „dolů“ a přidělíme mu hladinu 0. Hladina pak ukazuje to, jak vysoko při průchodu vystoupáme, tedy počet hran na cestě od kořene při průchodu do hloubky.

Pro každý vrchol se určí nejnižší hladina, do které se lze z něj dostat při průchodu do hloubky (hrana, po které jsme do něj přišli je přirozeně zapovězena). Každý vrchol si tuto hodnotu spočte rekurzivně jako minimum z hladin vrcholů, do kterých se z něj lze dostat.

Nyní, když se v DFS stromu vracíme z vrcholu w zpátky do jeho otce v, nastávají dvě možnosti: z vrcholu w se lze dostat pouze do hladin vyšších než v, pak je hrana vw most, neb po odebrání se už z w do nižších hladin nijak nedostaneme. Pokud se lze dostat alespoň do hladiny vrcholu v, pak se o most nejedná, protože i po odebrání hrany vw bude existovat cesta z v do w a graf tak bude souvislý.

Časová složitost průchodu do hloubky je O(N+M), kde N je počet vrcholů a M počet hran. Počet skupin hran různé váhy označme jako ℓ a počty hran v těchto skupinách jako m₁ až m_ℓ. V jednom průchodu procházíme pro každou skupinu graf, ve kterém je nejvýše N-1+m_i hran (kostra grafu na N vrcholech má N-1 hran). Časová složitost je tak O(ℓ · N+∑_i m_i), což je v nejhorším případě O(MN).

Pro vylepšení si uvědomíme, že vrcholy a hrany uvnitř už existujících komponent nás ve skutečnosti vůbec nezajímají. Zajímá nás pouze to, jak propojují aktuálně zpracovávané hrany. Graf proto budeme konstruovat tak, že jeho vrcholy budou tyto komponenty. Navíc komponenty, do kterých nevede žádná z aktuálně zpracovávaných hran, do grafu nezahrneme.

Takový graf už nemusí být klasickým grafem, ale mohou v něm existovat i násobné hrany (více hran mezi dvěma vrcholy, tzv. multihrany). To nevadí, uvědomíme si, že multihrany nemohou být mosty a nic jiného není ovlivněno. Takový graf bude mít m_i hran a nejvýše 2m_i vrcholů, kde m_i je počet hran i-té váhy.

Celková složitost hledání mostů bude O(m₁+m₂+… +m_ℓ)=O(M). V Kruskalově algoritmu hrany na začátku setřídíme nějakým efektivním algoritmem, např. QuickSortem, a pak používáme strukturu Disjoint-Find-Union. To nám dává časovou složitost O(M log M), což je i složitost celého algoritmu. Paměťová složitost je O(M).

Důkaz správnosti

Zatím jsme pro hrany nějaké váhy w_i rozhodli pouze to, zda se objeví v nějaké kostře za předpokladu, že už je určena částečná kostra T, která vznikla během Kruskalova algoritmu na všech hranách menší váhy. Dokážeme, že hrana, která spojuje 2 vrcholy stejné komponenty v průběhu našeho algoritmu, se neobjeví v žádné minimální kostře.

Předpokládejme pro spor, že existuje minimální kostra, ve které se vyskytuje tato hrana e. Odeberme tuto hranu – vzniknou dvě komponenty. Uvažme všechny hrany původního grafu, které vedou mezi komponentami (z vrcholu jedné komponenty do vrcholu druhé komponenty). V průběhu našeho algoritmu byly tyto komponenty spojeny lehčí hranou než e, tedy mezi vybranými hranami je tato hrana. Když ji přidáme místo e do kostry, vznikne nová kostra s menší váhou – to je spor s tím, že se jednalo o minimální kostru.

O ostatních hranách víme, že se vyskytují v alespoň jedné minimální kostře. Předpokládejme, že existuje minimální kostra, ve které se nevyskytuje hrana e=uv, o které jsme prohlásili, že se vyskytuje v každé kostře. Uvažme cyklus, který vznikne přidáním hrany e do této kostry.

Pokud mají všechny hrany na tomto cyklu menší váhu, pak bychom hranu e do kostry vůbec nepřidávali, místo toho bychom vrcholy u a v spojili těmito levnějšími hranami. Pokud se na cyklu vyskytuje ostře větší hrana, je možno ji za e vyměnit, tím ale vznikne lehčí kostra, což je spor.

Zbývá případ, kdy se na cyklu vyskytuje alespoň jedna hrana f=wx stejné váhy. Pak se ale dvojice (u,w), (v,x) nebo (u,x), (v,w) dají spojit hranou váhy nejvýše stejné jako e a v algoritmu bychom vyhodnotili, že ani e ani f nejsou mosty, to je opět spor.

Pro zbývající hrany jsme přímo ukázali, jak sestrojit minimální kostru, kde se vyskytují, i minimální kostru, kde se nevyskytují. Důkaz je tímto hotov.

Závěrem si dovolím malou poznámku. Jak asi vidíte, tento důkaz je dosti nepěkný a nepřehledný. Kolem koster existuje zajímavá teorie, pomocí které lze tvrzení podobná tomu našemu dokazovat daleko příjemněji. Doporučuji nahlédnout do učebního textu Martina Mareše Krajinou grafových algoritmů. Lze tam nalézt například i to, že pro zavedení minimální kostry vlastně vůbec nemusíme umět váhy hran sčítat – stačí je umět porovnávat. (Což lze možná i odtušit z toho, že Kruskalův algoritmus sčítání nevyužívá.)

Program (C++)

Lukáš Folwarczný

Teorie minimálních koster

Z té zmíněné teorie minimálních koster si ostatně můžeme malý kousek ukázat. Uvažme nějakou minimální kostru T a hranu e=uv, která v této kostře neleží. Víme, že vrcholy u a v jsou v kostře T spojené nějakou cestou T[u,v]. Označme f nejtěžší hranu této cesty.

Rozlišíme tři případy:

• f je těžší než e – tento případ nemůže nastat. Tehdy bychom totiž mohli z kostry T odebrat hranu f a vzniklé dvě komponenty spojit přidáním hrany e. Tím bychom získali lehčí kostru, než byla minimální kostra T.
• f je stejně těžká jako e – pak můžeme použít tentýž trik a získat jinou kostru stejně těžkou jako T (tedy též minimální), která obsahuje hranu e. Tím pádem hrana e v některých minimálních kostrách leží a v jiných ne.
• f je lehčí než e – dokážeme, že tehdy se e nemůže vyskytovat v žádné minimální kostře. K tomu se nám bude hodit následující lemma (použijeme ho na cyklus tvořený cestou T[u,v] a hranou e).

Cyklové lemma: Nechť C je cyklus v grafu a e=uv jeho hrana, která je těžší než všechny ostatní hrany cyklu C. Potom se e nevyskytuje v žádné minimální kostře.

Důkaz: Pro spor předpokládejme, že existuje nějaká minimální kostra K, která obsahuje hranu e. Odebereme-li z K tuto hranu, kostra se rozpadne na nějaké dva stromy K_u a K_v (označíme je tak, aby u∈K_u a v∈K_v). Budeme obcházet cyklus C: začneme ve vrcholu u, půjdeme vzdálenější cestou k vrcholu v (tedy ne po hraně e) a budeme sledovat, ve kterém stromu se zrovna nacházíme. Na začátku to je strom K_u, na konci K_v, takže někde cestou musíme potkat nějakou hranu h, jejíž jeden konec leží v K_u a druhý v K_v. Tato hrana se ovšem nevyskytuje v kostře K a je lehčí než hrana e (protože hrana e byla nejtěžší na cyklu). Proto nahrazením e za h získáme kostru lehčí než K, což je spor s minimalitou K.

Naše tři pravidla nám tedy říkají, jak pro každou hranu, která neleží ve zvolené minimální kostře T, rozhodnout, zda leží v nějaké / všech / žádné minimální kostře. Stačí umět hledat nejtěžší hrany na cestách v T, na což se dá elegantně použít datová struktura z druhé úlohy této série.

Zbývá dořešit, jak je to s hranami, které leží v T, ale to už si zkuste rozmyslet sami. Opět pomůže Cyklové lemma.

Martin „Medvěd“ Mareš

---

25-2-7 Zaléváme dokument (Zadání)

---

Nepřišlo sice tolik vašich řešení jako v první sérii, ale stále se jednalo o úlohu s největším počtem odevzdaných řešení. Vypadá to, že vás TeX zaujal a to je dobře.

Úkol 1

Řešení tohoto úkolu jste se zhostili velmi úspěšně a vynalézavě. Podívejme se, jakým způsobem se dal řešit. Nejprve bylo potřeba nadefinovat bílá a černá pole.

\def\bile#1{\hskip #1}
\def\cerne#1{\vrule height #1 width #1}

Objevily se i jiné, stejně dobré definice bílého pole:

\def\bile#1{\hbox to #1{\hfil}}
\def\bile#1{\vrule height 0cm width #1}

Pak je potřeba políčka nějak poskládat do šachovnice. Ondra Hlavatý přišel s nápaditým a čistým řešením – definovat oblasti 2×2.

\def\ctyrka#1{\vbox{%
  \hbox{\bile{#1}\cerne{#1}}%
  \hbox{\cerne{#1}\bile{#1}}%
}}

Tyto oblasti pak naskládáme do šachovnice a orámujeme.

\def\sachovnice#1{\vbox{\offinterlineskip%
  \hrule\hbox{%
    \vrule\vbox{%
      \hbox{\ctyrka{#1}\ctyrka{#1}%
	    \ctyrka{#1}\ctyrka{#1}}%
      \hbox{\ctyrka{#1}\ctyrka{#1}%
	    \ctyrka{#1}\ctyrka{#1}}%
      \hbox{\ctyrka{#1}\ctyrka{#1}%
	    \ctyrka{#1}\ctyrka{#1}}%
      \hbox{\ctyrka{#1}\ctyrka{#1}%
	    \ctyrka{#1}\ctyrka{#1}}%
    }\vrule
  }\hrule
}}

Šachovnici vykreslíme zavoláním \sachovnice{20mm}.

Vypnutí meziřádkové mezery (\offinterlineskip) jste si mohli najít na fóru, případně jste mohli nastavit rozměry \baselineskip a \lineskip na nulu.

Typickou chybou bylo vynechání vypnutí meziřádkových mezer, což vytvořilo ošklivé bílé pruhy mezi řádky. To jsem penalizoval obvykle jedním bodem. Drobné penalizace jste se také mohli dočkat za nečitelný kód.

Úkol 2

Druhý úkol bylo prosté cvičení na vyloženou látku. Někteří jej hrubě odflákli, objevilo se nezarovnání počtu bodů na pravou stranu nebo ošklivě malá mezera pod textem.

Takto vypadá vzorová implementace používaná v KSP (jen máme okolo přidané ještě nějaké mezery, aby nám nadpisy úloh lépe sedly do sazby):

\def\thrule{\hrule height 0.8pt depth 0pt}
\def\dblrule{\thrule\nobreak\vskip 1pt\thrule}
\def\taskheading#1#2#3{\vtop{%
  \dblrule\line{%
    \strut\bf #1 \enspace #2 \hfil #3}
  \dblrule}%
}

Makro \thrule definuje čáru, \dblrule definuje dvojčáru. Makro \enspace je definováno v Plainu jako mezera velká přesně 0.5em.

Asi dva z vás použili i \strut, což je zkratka definovaná v Plainu za podlý trik (leč naprosto běžný a standardní): \vrule width 0pt height 8.5pt depth 3.5pt\relax

Účel použití této konstrukce naleznete ve třetí sérii. Ti, kdo na to přišli sami, u mě mají malé bezvýznamné plus.

Úkol 3

Toto byl nejtěžší úkol. Definice vlastního prostředí typu verbatim dala mnohým zabrat. Objevilo se několik variant, obvykle jste si zvolili nějaký znak nebo fixní sekvenci, která prostředí verbatim ukončí. Zde uvádíme vzorovou implementaci, ve které si můžete zvolit ukončovací řetězec sami.

Příkaz \verbatim je vstupní rozhraní celého prostředí. Otevře se skupina, přestaví se kategorie speciálních znaků, změní se práce s mezerami a předá se řízení do dalšího makra.

\def\verbatim{%
  \begingroup
  \verbcats
  \verbspaces
  \verbwork
}

Přestavení speciálních tisknutelných znaků se provede s výjimkou složených závorek, které ještě budeme potřebovat, aby nám orámovaly ukončovací řetězec.

Všimněte si speciální sekvence ^^I a ^^M. Když TeX potká dva stejné znaky kategorie 7 za sebou, spolkne je a následujícímu znaku přehodí šestý bit. Operace se provádí před tokenizací (takže \^^I je token (TAB, 0), tedy řídící sekvence se jménem TAB).

Takže ^^I je znak s kódem 9, tedy tabulátor; ^^@ je znak s kódem 0; ^^. je znak n; ^^? je znak s kódem 127, zvaný též DEL, jediný znak, který je běžně kategorie 15. Tento zápis se hodí pro přehlednost, aby se v kódu jen tak nepoflakovaly netisknutelné znaky.

Ještě pro úplnost, pokud se za ^^ objeví dvě malé hexadecimální číslice (0 až 9, a až f), nahradí se celá čtveřice za znak s uvedeným hexadecimálním kódem.

\def\verbcats{%
  \catcode`\\=12
  \catcode`\$=12
  \catcode`\&=12
  \catcode`\#=12
  \catcode`\^=12
  \catcode`\_=12
  \catcode`\%=12
  \catcode`\~=12
  \catcode`\ =13
  \catcode`\^^I=13
  \catcode`\^^M=13
}

Nyní nastavíme chování verbatimu na bílých znacích.

Mezera, tabulátor a konec řádku se stanou aktivními znaky s významem \verbspc, \verbtab a \verbcr. Konec řádku zajistí, že se vstoupí do odstavcového módu a vynutí se vysázení odstavce. Odstavec musí obsahovat nějaký materiál, jinak se nevysází, proto ten \hskip.

Mezera se vysází jako explicitní mezera. Tabulátor vysázíme jako čtyři mezery. Pokud odkomentujete šestý řádek, budou mezery vysázeny viditelně. Mezery na koncích řádků se ořezávají ještě před tokenizací, takže je vysázet neumíme.

\catcode`\ =13\catcode`\^^I=13\catcode`\^^M=13
\def\verbspaces{\let \verbspc\let
\verbcr\let^^I\verbtab}
\catcode`\ =10\catcode`\^^I=10\catcode`\^^M=5
\def\verbspc{\ }
%\chardef\verbspc 32
\def\verbtab{\verbspc\verbspc\verbspc\verbspc}
\def\verbcr{\noindent\hskip 0pt\par}

Nakonec se přečte ukončovací řetězec (který může obsahovat libovolné znaky, jen musí být dobře uzávorkovaný, co se týče složených závorek), nastaví se i kategorie složených závorek na 12, zruší odsazení prvního řádku odstavce a provede finální magie.

\def\verbwork#1{%
  \catcode`\{=12%
  \catcode`\}=12%
  \parindent 0pt%
  \def\verbdo^^M##1#1{\tt##1\endgroup}%
  \verbdo
}

Makro \verbatim se volá takto:

\verbatim{EOV}
Nějaký zdrojový kód
   odsazený mezerami
	nebo tabulátorem

s prázdnými řádky
a obsahující různé speciální znaky
jako jsou { a } nebo %
EOV

Nyní vysvětlíme magii okolo \verbdo. Parametr {EOV} se přečte až při volání makra \verbwork. To pak definuje \verbdo vlastně takto:

\def\verbdo^^M#1EOV{\tt#1\endgroup}

Pak se makro zavolá, spolkne konec řádku za {EOV} a zbytek až do EOV vysází. Pak uzavře skupinu, čímž všechny zběsilé změny kategorií zruší a můžeme zase sázet klasicky dál. Místo EOV můžeme použít libovolný jiný řetězec, který bude verbatim ukončovat.

Za rozumně funkční řešení jsem dával plný počet bodů. Za vážnější prohřešky jsem pak něco strhával.

Balíky maker

Čím více budete používat TeX, tím více budete mít pocit, že si na začátek souboru kopírujete děsnou spoustu věcí. TeX umí vkládat externí soubory primitivem \input, za které uvedete jméno souboru. Můžete si tedy například vytvořit svůj soubor se spoustou maker, který si pak vložíte do každého sázeného textu. Například všechny letáky KSP začínají příkazem \input kspmac3.2.tex, tedy vložením souboru s makry KSP, verze 3.2.

Na spoustu různých úkolů pak existují specializované balíky, které si uživatelé můžou vyměňovat přes CTAN (Comprehensive TeX Archive Network). Na adrese http://www.ctan.org/ tedy najdete několik tisíc různých balíků všeho druhu.

A to je pro dnešek vše. Děkuji vám všem za hezká řešení a těším se na příští sérii.

Jan „Moskyto“ Matějka

Menu