Čtvrtá série začátečnické kategorie dvacátého devátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 29-Z4-1: Šíření viru
- 29-Z4-2: Vybírání atrakcí
- 29-Z4-3: Želva v akváriu
- 29-Z4-4: Hledání součtu
- 29-Z4-5: Hanojské věže jinak
- 29-Z4-6: Tajná síť taháků
29-Z4-1 Šíření viru (Zadání)
Úloha se šířícím se počítačovým virem byla hezká simulace na úvod letošní poslední série. V zadání jsme slíbili, že v každém vstupu se všechny počítače nakazí, takže stačilo jen počítat, za jak dlouho to nastane. Jak na to?
U každého počítače si budeme pamatovat, v jakém kroku byl nakažen (maximum z těchto čísel pak bude finální odpovědí) a kolik má nakažených sousedů (na počátku u všech počítačů nula). Zatím nezpracované nakažené počítače si budeme držet ve frontě, do které na počátku vložíme nakažené počítače ze vstupu (a nastavíme jim krok, ve kterém byly nakaženy, na nulu).
Pak nám stačí postupně vybírat počítače z fronty a zpracovávat je. Každému zatím nenakaženému sousedovi zpracovávaného počítače zvedneme počítadlo nakažených sousedů o jedna a pokud tím soused přesáhne kritickou mez (jeho počítadlo nakažených sousedů dosáhne alespoň poloviny počtu jeho sousedů), nakazíme ho taky – vložíme ho na konec fronty nakažených počítačů a nastavíme mu krok nakažení o jedna vyšší, než má aktuálně zpracovávaný počítač.
Tímto postupem postupně nakazíme všechny počítače (zastavíme se ve chvíli, kdy už ve frontě nebude žádný nezpracovaný nakažený počítač) a díky tomu, že na ukládání nezpracovaných nakažených počítačů používáme frontu, spočítáme správně i krok nakažení – počítače zpracováváme jakoby „ve vlnách“, nejprve zpracujeme všechny počítače, které se nakazí v kroku k (což může vést k nakažení nějakých počítačů v kroku k+1), než postoupíme dál. Pro nalezení odpovědi si tak stačí průběžně pamatovat maximální krok, ve kterém nakazíme nějaký z počítačů.
Přidáme ještě drobný implementační tip: Lepší, než porovnávat, že A ≥ B/2 je porovnávat 2A ≥ B, vyhnete se tak hloupým zaokrouhlovacím chybám.
29-Z4-2 Vybírání atrakcí (Zadání)
Tato úloha šla efektivně řešit hladovým algoritmem. Hlavní trik spočívá v tom, že před samotným přiřazováním atrakcí si vše setřídíme. Atrakce setřídíme jednoduše podle jejich rychlosti. Osoby setřídíme vzestupně podle nejvyšší snesitelné rychlosti a v případě rovnosti je dále setřídíme podle snesitelné rychlosti nejnižší.
Setřízené atrakce nyní přesuneme do seznamu nepoužitých atrakcí. Dále pro každou osobu nalezneme pozici nejlehčí nepoužité atrakce, kterou již zvládne. Od této pozice vybereme K za sebou jdoucích atrakcí a ty osobě přidělíme. Přidělené atrakce poté odstraníme ze seznamu nepoužitých atrakcí. Takto postupujeme, dokud nevyužijeme všechny atrakce.
Proč tohle může fungovat? Vezměme prvního člověka v popsaném pořadí, pojmenujme ho A. Nemáme příliš volnosti, nějakých K atrakcí mu přidělit prostě musíme. Každopádně má smysl uvažovat pouze ty, které snese. Mezi nimi náš algoritmus zvolí ty, jejichž rychlost je nejmenší. Klíčové v tuto chvíli je, že horní mez osob už pouze poroste – mezi lidmi, pro které tyto atrakci nejsou příliš pomalé, má osoba A nejnižší horní mez. Pokud bychom tyto atrakce přidělili komukoli jinému, mohlo by se stát, že všechny další atrakce budou na A příliš těžké. Naopak nikoli, tedy můžeme atrakce přidělit právě osobě A.
V algoritmu bychom dvakrát tvrdě narazili, pokud bychom neměli zaručeno, že řešení existuje. Poprvé tehdy, kdy přidělujeme K po sobě jdoucích atrakcí osobě, o které víme, že zvládne tu nejpomalejší z nich. Díky způsobu přidělování atrakcí ale víme, že pokud by osoba na nějakou atrakci nestačila, znamená to, že v seznamu nepoužitých už není více atrakcí, na které by osoba stačila – řešení nemůže existovat. Podruhé pak když předpokládáme, že s dokončením seznamu atrakcí jsme přiřadili K atrakcí každému člověku.
Nyní se zaměřme na časovou složitost. Počet atrakcí si označíme M = NK. Jelikož třídíme osoby i atrakce, nedostaneme se na složitost lepší, než O(M log M).
Jak to je ale s vybíráním atrakcí? Většina operací závisí na správném výběru datové struktury pro ukládání zatím nepoužitých atrakcí.
Mohli bychom použít pole a v něm vždy vyhledat první použitelnou atrakci binárně. Bohužel, jedno odebrání (i více najednou) prvků v poli trvá O(M) – po odebrání musíme zacpat vzniklou díru přesunutím všech prvků napravo. Složitost bychom si tím pohoršili na O(NM + M log M).
Každopádně, na plný počet bodů tento postup už stačil. Komu to ale nestačí, a věří že to musí jít lépe, nechť čte dál.
Na reprezentaci seznamu místo pole použijeme vyhledávací strom.
Po setřídění atrakcí z nich sestavíme vyvážený strom, to nám stačí i v O(M log M).
Vyhledání prvku i jeho odstranění je rovněž rychlé, obě tyto operace
vyhledávací strom zvládne v O(log M). Prvních K prvků od daného místa
vybereme jednoduše pomocí hledání následníka, které trvá rovněž O(log M).
Podotkněme, že není potřeba žádný speciální samovyvažovací strom. Stačí strom na začátku programu postavit rozumně vyvážený a později z něj jen odebírat. Tím se strom sice znevyváží, pořád ale bude mít hloubku nejvýše O(log M).
Celkem v algoritmu provedeme M vložení a odstranění, to nám celkově zabere O(M log M) času. N atrakcí jsme vyhledali, zbylých M-N jsme našli jako následníky. Po sečtení všech operací nám tudíž vyjde, že časovou složitost udržíme na O(M log M).
29-Z4-3 Želva v akváriu (Zadání)
Želva nás provázela všechny čtyři série a doufáme, že pro vás byla stejně dobrým společníkem jako pro Kevina. Tentokrát jste si za ni mohli vysloužit dokonce o dva body více, protože orientace v 3D prostoru může být náročná.
Jak jsme psali v zadání, tentokrát nestačí pamatovat si jen směr, kterým se želva dívá. Je potřeba si pamatovat ještě alespoň jeden. Například, kterým směrem má natočený krunýř, nebo kam míří její pravý bok.
Z těchto tří směrů si stačí pamatovat jen libovolné dva – třetí se dá vždy dopočítat. Úplně nejsnáze si ale řešení úlohy pořídíte, pokud si budete pamatovat všechny tři směry. Přepočítávat totiž stačí vždy pouze dva – směr v ose, okolo které se želva otáčí, se nikdy nemění. Jinými slovy, při každém otočení se změní pouze dva směry.
Všechny směry si budeme pamatovat jako vektory jednotkové délky. Takový vektor má tři složky, každou v jedné ze tří souřadných os. Každá složka obsahuje buď 0, 1 nebo -1, navíc je právě jedna složka nenulová. Například vektor ukazující na sever (směr pohledu želvy na začátku programu) si zapamatujeme jako [1, 0, 0] – stejně jako v zadání.
Představme si nejprve jednoduché otočení želvy doprava. Směr nahoru, tedy kam míří krunýř, se touto rotací nezmění. Směr, kam se želva dívá, stačí nahradit za ten, kam byl předtím natočen pravý bok. Zbývá už jen spočítat nový směr pravého boku. Ten je rovnoběžný s tím, kam se předtím želva dívala – jen je opačným směrem.
Pro celou operaci otočení doprava tedy stačí prohodit směr pohledu a pravého boku, a následně pravý bok obrátit – každou složku vektoru vynásobit -1. Ostatní rotace jsou už jen variací na stejné téma. Vždy stačí jen některé dva směry prohodit a jeden z nich obrátit.
29-Z4-4 Hledání součtu (Zadání)
Zadání úlohy po nás chtělo najít v posloupnosti N čísel takovou její souvislou podposloupnost, že součet prvků této podposloupnosti bude co nejblíže zadanému číslu C. Pro vyřešení několika prvních vstupů postačil jednoduchý přístup k řešení – stačilo vyzkoušet všechny možné podposloupnosti a z nich vybrat tu s nejmenším rozdílem jejího součtu a čísla C. Úloha se ale dá snadno vyřešit v lineárním čase, jak si za chvíli ukážeme.
Zkusme si nejprve úlohu trochu zjednodušit. Nebudeme hledat podposloupnost s nejbližším součtem k číslu C, ale podposloupnost, jejíž součet je roven právě C. Každá souvislá podposloupnost začíná a končí na nějakých indexech původní posloupnosti. Označme si tato místa jako zac a kon, přičemž vždy platí zac ≤ kon. Na začátku položíme zac = kon = 0. Tyto indexy budeme při běhu programu postupně zvyšovat. Zavedeme si dále proměnnou S, ve které budeme mít uložen součet prvků zadané posloupnosti mezi místy zac a kon.
Provedeme nyní několik pozorování. Pokud je S > C, nemá cenu zvyšovat kon a raději zvýšíme zac. Zadání předpokládá pouze kladná čísla, pokud bychom kon o 1 zvýšili, zvýšilo by se nám i S o nově přidaný prvek. My ale chceme, aby S = C. Pokud naopak zvýšíme o 1 index zac, S se nám sníží, což je v této situaci žádoucí. Obdobně, pokud je S < C, nemá cenu zvyšovat zac. Raději zvýšíme kon o 1. A nakonec, pokud je S = C, máme nalezeno řešení a můžeme skončit.
Tato pozorování nám dávají přímý návod na sestavení algoritmu pro zjednodušenou verzi úlohy. Jak toto řešení rozšířit tak, aby zvládlo i úlohu ze zadání? Velmi jednoduše! Stačí si při běhu ukládat dosud nejlepší nalezené řešení a v každé iteraci pak kontrolovat, jestli aktuální řešení není náhodou lepší, než to doposud nejlepší nalezené. O tom, které řešení je lepší, lze rozhodnout velmi jednoduše – z absolutní hodnoty rozdílu S a C. Máme-li dvě řešení A, B a k nim příslušné SA respektive SB, porovnáme |SA - C| s |SB - C| a vybereme menší z nich. Výpočet můžeme ukončit ve chvíli, kdy máme S = C nebo kdybychom zac zvýšili na N. (pozn. indexujeme od 0, poslední prvek posloupnosti má index (N-1).)
Povšimněme si, že způsob manipulace s indexy v podstatě odpovídá přidávání prvků zadané posloupnosti do fronty a jejich odebírání z ní. Každý prvek se přitom může do fronty dostat maximálně jednou. Odtud nám plyne i časová složitost řešení O(N).
29-Z4-5 Hanojské věže jinak (Zadání)
Dostali jsme nějaké rozestavení, jak máme vlastně začít? Dobrým prvním krokem by bylo rozmyslet si na jaké tyči chceme věž postavit. Všimněte si, že je vždy nejlepší věž postavit na tyči, kde už je největší disk. Proč tomu tak je? Kdybychom chtěli věž postavit jinde, musíme uvolnit největší disk (nesmí na něm být žádné další disky) a celou tyč, kde chceme věž postavit, na poslední tyč tedy musíme vyskládat všechny zbylé disky. Pak přesuneme největší disk a pokračujeme ve stavbě. Nicméně krok přesunu největšího disku si můžeme odpustit a a rovnou stavět na největším disku, nijak si nepohoršíme.
Nyní jsme si vybrali tyč, kde budeme stavět věž a navíc tam máme už první, největší disk. Dřív než než na něj začneme skládat menší disky musíme na něj nějak dostat druhý největší. Představme si, že největší disk neexistuje. Snažíme se tedy vystavět věž s výškou o jeden disk menší než původně, tentokrát ale na konkrétní tyč – na tu, kde se nachází disk největší. Poznamenejme, že tím, že je největší disk největší, se nám nic nezmění tím, že ho budeme ignorovat – můžeme na něj dát libovolný disk, stejně jako na prázdnou tyč.
Pomohli jsme si tedy vůbec? Stále máme za úkol postavit věž, byť o kousek menší, navíc na konkrétní tyč. Ukážeme si, že ano. Označme si druhý největší disk (popř. největší, který neignorujeme) jako D. Jako první musíme dostat D na cílovou tyč. Můžeme mít štěstí a D tam už bude, pak můžeme tento krok přeskočit, pokud máme ale smůlu, chce to trochu úsilí, pojďme se na to podívat.
Abychom mohli přesunout D na cílovou tyč, musí být cílová tyč prázdná (až na ignorovaný disk) a D volná (nesmí na něm být žádný další disk). Všechny ostatní disky tedy musí být vyskládané do věže na poslední tyči. Poté můžeme přesunout disk D a poté celou vyskládanou věž na cílovou tyč.
To vypadá, jako bychom se zase nikam nedostali. Abychom vyřešili problém přeskládání věže, musíme vyřešit problém přeskládání dvou věží (nejprve na uvolnění cílové tyče a D, poté na přeskládání zbylých disků na cílovou tyč). Nicméně klíčové je, že tyto věže jsou opět o jeden disk nižší. Můžeme je vyřešit právě tím samým algoritmem! Abychom uvolnili cílovou věž a D, můžeme na chvíli ignorovat D a jako D dočasně označit další největší disk. Pak necháme proběhnout celý algoritmus, poté přesuneme naše původní D a pak znova necháme náš algoritmus pracovat.
Jenže skončí toto někdy? Vždyť v každém průběhu algoritmu vytváříme dva další. Musíme si uvědomit, že až budeme pracovat s jedním diskem, nepotřebujeme vůbec spouštět nějaký složitý algoritmus, stačí přesunout disk na správné místo, pokud tam ještě není. Ti zkušenější z vás v tomto postupu zcela správně vidí analogii s tzv. rekurzí.
Nakonec ještě připomeneme, proč toto vyskládání je nejrychlejší možné. Na začátku jsme opatrně vybrali tu nejlepší tyč, na které věž stavět. Poté už všechny kroky byly nutné (uvolnit disk a cílovou tyč, přeskládat zbylé disky), takže jsme tento postup nemohli vůbec urychlit.
29-Z4-6 Tajná síť taháků (Zadání)
Nejprve si zkusíme problém trochu formalizovat. Místo tajné sítě taháků si můžeme rovnou představit graf. Jeho vrcholy budou Kevinovi spolužáci, hrany povedou mezi těmi spolužáky, kteří si mezi sebou předávají taháky napřímo.
Nebude to ale jen tak ledajaký graf – v zadání jsme vám slíbili, že nebude obsahovat cykly. Navíc, protože jde o jednu síť, můžeme předpokládat, že jde o graf souvislý. Graf, který je souvislý a neobsahuje cykly, je strom.
Bez újmy na obecnosti si strom libovolně zakořeníme. Nyní se podívejme, co se stane, pokud ze stromu odtrhneme libovolný vrchol v. Strom se rozpadne na několik podstromů: jeden za každého syna v, a jeden navíc za otce v. Tyto části mají dohromady |V| - 1 vrcholů. Jak také jinak, že :)
Na pomoc si přizveme obyčejné prohledávání do hloubky. Budeme postupovat stejně, jako bychom chtěli spočítat počet vrcholů ve stromě: z rekurze do listů vrátíme 1, jinak součet hodnot vrácených ze synů zvýšený o jedna.
Tento algoritmus jednoduše modifikujeme. Během návratu z rekurze víme, jaká je velikost všech podstromů. Pokud odečteme jejich součet od celkového počtu vrcholů (a odečteme ještě jedničku navíc), získáme velikost zbylé části grafu. Není-li žádná z nich větší než polovina, vyhráli jsme, hledaným vrcholem je ten aktuální.
Takto najdeme toho správného spolužáka v lineárním čase. Najdeme ho ale vždy?
Tak, jak byla úloha zadána, se může stát, že žádný takový neexistuje. Vezměte si třeba strom tvořený dvěma vrcholy spojenými hranou. Ať odebereme libovolný z nich, zbylý podstrom bude mít vždy alespoň polovinu původního počtu vrcholů.
Protože ale náš algoritmus projde nakonec všechny vrcholy, tak si můžeme být jistí, že pokud ten správný vrchol existuje, tak jej najdeme.
Kdybychom ale požadovali ostře více než polovinu původního počtu vrcholů, aby síť zůstala v provozu, situace by byla zajímavější. O tom zas ale někdy příště…