Čtvrtá série začátečnické kategorie třicátého prvního ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 31-Z4-1: Nejosamělejší kamarád
- 31-Z4-2: Závažíčka na druhou
- 31-Z4-3: Probíhání bludištěm
- 31-Z4-4: Ohnivý únik
- 31-Z4-5: Naplnění nádob
- 31-Z4-6: Sčítání škod
31-Z4-1 Nejosamělejší kamarád (Zadání)
Nejlehčí úloha série v sobě neskrývala žádná překvapení, ale alespoň trochu se zamyslet bylo potřeba, přímočaré „dřevorubecké“ řešení nestačilo.
Takovým „dřevorubeckým“ řešením by mohlo být to, které si pro každého kamaráda samostatně najde nejbližšího jiného a pak mezi všemi kamarády najde maximum (tedy toho nejosamělejšího). Toto řešení pro každého z N kamarádů projde všech N-1 zbývajících kamarádů a celkový čas bychom tak mohli vyčíslit jako O(N2) – to by na menší vstupy ještě stačilo, ale na největší vstupy to již bude příliš pomalé.
Trik, který nám řešení vylepší, je setřídění kamarádů podle pozice. Pokud jste
zaslechli něco o třídění nebo jste se podívali třeba do naší
kuchařky o třídících algoritmech, tak tušíte, že rychlé
třídící algoritmy umí seřadit seznam N prvků v čase O(N log N). V Pythonu
můžete použít takové rychlé třídění, které už naprogramoval někdo jiný,
jednoduchým zavoláním funkce sorted na seznam.
A jak nám setřídění kamarádů pomůže? Díky němu víme, že pro každého kamaráda je jeho nejbližší jiný kamarád v setříděném seznamu buď těsně nalevo nebo těsně napravo od něj. Pak nám stačí jenom kamarády jednou projít, pro každého si v konstantním čase spočítat vzdálenost k nejbližšímu jinému kamarádovi, a přitom si průběžně udržovat maximum. Tím se dostaneme na čas O(N) za tento průchod a O(N log N) celkově i s tříděním.
31-Z4-2 Závažíčka na druhou (Zadání)
Začněme pozorováním: pro každou velikost závaží je jednoznačně dáno, na kterou váhu přijde a jak ovlivní rozdíl vah. Když použijeme závaží váhy 2i, tuto váhu k rozdílu přičteme či odečteme v závislosti na sudosti či lichosti i. Obecně, i-tá váha (počítáno od nuly) ovlivní rozdíl hodnotou (-2)i. Výstup úlohy určuje, které mocniny -2 je třeba použít, aby jejich součet byl roven požadované hodnotě na vstupu. Tohle není nic jiného než zápis čísla na vstupu v mínus dvojkové soustavě, takže úloha je vlastně převod čísel do této soustavy.
Jak to provést? Všimněme si další věci: (-2)0 = 1 je jediná lichá mocnina (mínus) dvojky, tedy pokud je číslo na vstupu liché, určitě se v jeho zápisu v mínus dvojkové soustavě objeví. Pokud je vstup kladný, můžeme do výstupu hodnotu 1 rovnou zahrnout, ale pokud je záporný, tak její použití posune výstup směrem do kladných čísel, což je opačně, než chceme. V takovém případě do výstupu zahrneme i následující mocninu (-2)1 = -2, neboť -2 + 1 = -1. Přesněji, nemusíme použít přímo -2, ale úplně stačí, když celková hodnota zbytku bitů výstupu bude o jedna menší než číslo na vstupu, neboť musí kompenzovat první bit, jehož hodnota je nyní jedna.
Umíme určit hodnotu prvního (nejmenšího) bitu výstupu. Pokud byl vstup sudý, první bit jsme ponechali na nule, takže celková hodnota zbytku bitů výstupu musí být rovna vstupu. Pokud byl vstup lichý, tak od zbytku jeho bitů chceme, aby součet jejich mocnin byl roven vstupu mínus jedna, a to ať už byl vstup kladný nebo záporný. Hodnota zbytku bude díky tomuto postupu vždy sudá.
| (-2)1 |
| -2 |
V každém kroku algoritmu se hodnota zbytku zmenší v absolutní hodnotě na polovinu, takže těchto kroků může algoritmus provést nejvýše logaritmicky mnoho, než tato hodnota klesne na nulu (dělíme celočíselně). Časová složitost na převod jednoho čísla do mínus dvojkové soustavy je tedy O(log N), kde N je velikost převáděného čísla, neboli je lineární s délkou binárního zápisu tohoto čísla.
31-Z4-3 Probíhání bludištěm (Zadání)
Úlohu s místnostmi v bludišti můžeme zkusit vyřešit hrubou silou tak, že si pro každou místnost odsimulujeme všech K kroků, ale to narazí už třeba při zadání obsahujícím dvě místnosti a K v řádu miliard – prosté odsimulování je příliš pomalé, musíme vymyslet něco lepšího.
Než se pustíme do vymýšlení rychlejšího řešení úlohy, tak nejprve udělejme krok stranou a podívejme se na labyrint místností trošku jinak. Prvním krůčkem může být představit si labyrint jako graf, neboli jako vrcholy (místnosti) a hrany spojující tyto vrcholy (dveře). Kdo se v grafech moc neorientujete, můžete pro lepší vysvětlení nahlédnout do grafové kuchařky.
S různými grafy jste se už v minulých sériích mohli v některých úlohách potkat, ale tento graf má několik speciálních vlastností. První vlastností je, že hrany jsou orientované (takže si je můžeme představit jako šipky mezi místnostmi), a druhá vlastnost je, že do každé místnosti právě jedna šipka vchází a právě jedna z ní vychází. Když se nad tím zamyslíme víc, tak lehce uvidíme, že šipky mezi místnostmi tak musejí tvořit nějaké okružní trasy (jednu nebo více), těm budeme říkat cykly. Musí to tak být, protože když z nějaké místnosti začneme, tak skončit můžeme opět jenom v ní – z každé jiné místnosti existuje pokračování do zatím nepoužité místnosti (kdyby dveře vedly do místnosti, do které jsme již vstoupili odjinud, tak by tato místnost musela mít dva vstupy, což nemá) a místností není nekonečně. Takže dříve či později dojdeme opět do místnosti, odkud jsme začali cyklus procházet.
Teď bychom se již mohli vrhnout přímo na řešení, ale dovolíme si ještě udělat druhý krůček stranou a podíváme se na náš graf s cykly ještě jinak. Takovýto graf totiž popisuje nějakou permutaci, neboli promíchání prvků. Jeden krok této permutace si můžeme představit tak, že do každé místnosti postavíme člověka s číslem odpovídajícím číslu místnosti a každého necháme právě jednou projít dveřmi. Přesně tak máme vlastně i zadaný vstup.
Poznámku o permutacích jsme tu ale uvedli spíše na rozšíření obzorů, nám teď bohatě stačí představa, že místnosti tvoří několik cyklů. Když si pro každý cyklus najdeme všechny místnosti, které ho tvoří, a spočítáme si velikost cyklu, můžeme finální místnost po K krocích určit jednoduše. Předně pokud je K větší než velikost cyklu, tak můžeme vzít jenom zbytek po dělení K velikostí cyklu a pak si jen odkrokujeme zbylý počet kroků po cyklu. Toto řešení potřebuje čas O(N) pro nalezení cyklů a pak si pro každou z N místností odkrokuje nejvýše N kroků, čímž dostaneme finální časovou složitost O(N2).
Proč si ale kazit časovou složitost tím, že musíme po cyklu krokovat? Když máme cyklus uložený v nějakém seznamu, velikost cyklu je S a máme udělat K kroků, tak pro i-tou místnost cyklu určíme výslednou lokaci jako cyklus[(i + K) mod S] (kde mod je operace modulo, neboli zbytek po dělení). To pro každou místnost umíme udělat v konstantním čase, takže dosáhneme výsledného času O(N).
Implementovat to můžeme tak, že si pořídíme cyklus přes všechny místnosti. Když potkáme ještě nezpracovanou místnost, tak z ní zahájíme procházení cyklu a pak si pro každou místnost na cyklu spočteme výslednou lokaci a označíme ji za zpracovanou.
31-Z4-4 Ohnivý únik (Zadání)
V úloze hledáme něco jako nejkratší cestu mezi nějakými místy. Na to se nabízí použít klasické grafové postupy, především BFS, tedy prohledávání do šířky. Na bludiště se můžeme dívat jako na graf: jednotlivá volná políčka jsou vrcholy a každé políčko je propojené hranou se všemi svými sousedy, kteří nejsou zeď. Při programování ale není nutné tento graf explicitně vytvářet, můžeme stále pracovat jen s dvojrozměrným polem, které odpovídá bludišti. Vrchol je popsán souřadnicemi svého políčka. Zda z jednoho políčka vede hrana do druhého zjistíme tak, že se podíváme, jestli jedno z nich není zdí.
Pro prohledávání bludiště do šířky budeme potřebovat frontu (detaily viz kuchařka). Při procházení našeho bludiště si do ní budeme ukládat souřadnice políček, která chceme zpracovat. Jakmile při prohledávání poprvé nalezneme políčko s východem, tak platí, že do žádného jiného políčka s východem se nelze dostat rychleji. Ve frontě se totiž nyní nacházejí jen políčka, která jsou stejně daleko nebo dále od počátku než aktuální. Časová složitost prohledávání do šířky je O(n+m), kde n je počet vrcholů a m počet hran. V tomto grafu ale platí, že počet hran m je asi jen 2n (každému vrcholu přiřadíme nejvýše jednu hranu dolů a jednu doleva), takže celková časová složitost je O(n + 2n) = O(n).
Slupky
Všimněme si, že prohledávání do šířky zpracovává vrcholy po slupkách. Slupka je tvořena všemi vrcholy, které jsou od počátečního stejně daleko. Nultá slupka je jen počáteční vrchol, první slupkou jsou jeho sousedé, druhou sousedé jeho sousedů. Obecně slupka i+1 jsou všichni sousedé slupky i vyjma vrcholů, které už patří do slupky i-1.
Pokud budeme zpracovávat vrcholy ze začátku fronty, které jsou ve slupce i, budeme přidávat na konec fronty vrcholy slupky i+1, dokud ze začátku fronty vrcholy i nedojdou. Nyní je celá fronta plná vrcholů slupky i+1, které budou při zpracování do fronty přidávat vrcholy slupky i+2 a tak dále. Ve frontě budou tedy vždy přítomny pouze dvě slupky, jedna, jejíž vrcholy zpracováváme a druhá, jejíž vrcholy do fronty přidáváme.
Celý výpočet BFS jde tedy rozdělit na jednotlivé slupky. Fronta lze nahradit dvěma seznamy: z prvního postupně odebíráme vrcholy slupky i, do druhého přidáváme vrcholy slupky i+1. Jakmile nám dojdou vrcholy v prvním seznamu, tak oba seznamy jednoduše prohodíme a pokračujeme ve výpočtu. Toto zpracování jedné slupky odpovídá pohnutí o jeden krok či jednu hranu na hledané nejkratší cestě.
A co oheň?
Zatím jsme se zabývali jen hledáním nejkratší cesty do nějakého východu a oheň jsme ignorovali. Provedeme následující: budeme hledat nejkratší cestu do nějakého východu pomocí výše popsané varianty BFS se dvěma seznamy, které odpovídají slupkám. Políčka, která hoří, budeme považovat za zeď. Po zpracování každé slupky provedeme jeden krok simulace ohně. Oheň budeme také simulovat pomocí slupkového prohledávání do šířky. Do nulté slupky ohně vložíme všechna políčka, která na počátku hoří.
V programu budeme ve smyčce postupně simulovat jeden tah osoby, poté jeden tah ohně. Jeden tah odpovídá zpracování jedné slupky daného BFS. Každý vrchol, kam se dostane prohledávání ohně, označíme v mapě jako oheň, a to už v okamžiku, kdy toto políčko přidáme do příští slupky.
Pokud bychom při BFS osoby přidali do příští slupky políčko sousedící s ohněm, tak by při simulaci ohně toto políčko pod námi začalo hořet, takže jej nelze použít. Toto můžeme opravit například tím, že při odebírání políček ze slupky při BFS osoby zkontrolujeme, zda políčko nezačalo hořet, a v takovém případě jej rovnou zahodíme.
Tím zajistíme, že nikdy nebudeme zpracovávat cestu, která projde ohněm (do zapáleného políčka nikdy nevkročíme a políčko, které začne hořet přímo pod námi, zahodíme v dalším kroku). A jak dlouho nám to trvá? Obě BFS zpracují každé políčko nejvýše jednou, takže i dohromady bude jejich časová složitost lineární vzhledem k velikosti bludiště.
31-Z4-5 Naplnění nádob (Zadání)
Máme n nádob a p příkazů k nalévání vody. Každý příkaz je určený trojicí čísel (ai,bi,ℓi), která říká, že do všech nádob s čísly ai až bi máme nalít po ℓi litrech vody.
Představíme si na chvilku, že příkaz je jenom jeden: (a,b,ℓ). Tehdy bychom mohli na a-tou nádobu pověsit cedulku s nápisem „toto je první nádoba, do které se má nalévat ℓ litrů“ a na (b+1)-ní nádobu cedulku „od této nádoby dál už ℓ litrů nenalévej“. Pak postačí projít se podél řady nádob: když potkáme první cedulku, začneme do všech nádob, kolem kterých projdeme, nalévat ℓ litrů. S naléváním skončíme, jakmile potkáme druhou cedulku.
Totéž funguje, je-li příkazů víc. Za každý příkaz (ai,bi,ℓi) vyrobíme dvě cedulky: počáteční umístíme na ai-tou nádobu, koncovou na (bi+1)-ní nádobu. Pak se zase projdeme kolem řady nádob a doléváme. Průběžně si udržujeme proměnnou D, která nám říká, kolik vody máme do nádob dolévat. Když potkáme počáteční cedulku pro i-tý příkaz, zvýšíme D o ℓi. Když potkáme koncovou cedulku, tak D o ℓi snížíme.
Postup můžeme ještě zjednodušit: na cedulky můžeme psát prostě +ℓi a -ℓi podle toho, jak máme změnit D. A pokud se sejde více cedulek na tomtéž místě, můžeme jejich hodnoty sečíst.
Nyní algoritmus popíšeme detailněji:
- Nejprve vytvoříme pole c[1… n+1], v němž si budeme pro každou nádobu pamatovat součet všech cedulek pověšených na ni. Na počátku výpočtu to budou samé nuly. (Pole indexujeme až do n+1, protože občas potřebujeme pověsit cedulku za poslední nádobu.)
- Projdeme všechny příkazy a pro každý příkaz (ai,bi,ℓi) zvýšíme c[ai] o ℓi a snížíme c[bi+1] o ℓi.
- Projdeme všechny nádoby a doléváme. Inicializujeme D na 0. Pak pro i=1,… ,n opakujeme: k D přičteme c[i] a do i-té nádoby nalijeme D litrů. Jelikož do této nádoby už nic dalšího nenalijeme, můžeme rovnou vypsat, že v ní na konci bude D litrů.
Jak rychlý tento algoritmus bude? Inicializace pole trvá čas O(n), jeho vyplnění podle příkazů O(p) a konečně projití nádob zabere O(p). Celkem tedy O(n+p). Rychleji to jistě nejde, protože tento čas je potřebný na samotné přečtení vstupu a vypsání výstupu.
Paměť spotřebujeme na uložení pole c a na konstantní počet pomocných proměnných. Vstup a výstup si nemusíme pamatovat: vstup zpracováváme jeden příkaz po druhém a už se k nim nevracíme, výstup vypisujeme průběžně. Prostorová složitost tudíž činí O(n).
31-Z4-6 Sčítání škod (Zadání)
Zadání úlohy nás navádí k tomu, abychom vytvořili nějaký graf – pokud si
potřebujete grafovou terminologii připomenout, nahlédněte do naší
grafové kuchařky. Máme
políčka, která na sobě nějak závisí. Zkusíme tedy políčka prohlásit za
vrcholy grafu a závislosti za hrany. Pokud je například v poli A4
zapsáno =A2+A1, natáhneme orientované hrany z vrcholů A2
a A1 do vrcholu A4. Je důležité, aby hrany byly orientované,
jinak bychom ztratili přehled o tom, které políčko se má vyhodnotit před
kterým.
Máme orientovaný graf, tak co teď? Chceme najít nějaké pořadí políček se vzorci (to jsou ta, do kterých vedou nějaké hrany z jiných políček). Pro jednoduchost najdeme pořadí všech políček, tedy i těch, ve kterých je zapsané pouze číslo. Vlastně nám to vůbec nebude vadit, protože jak ukážeme dále, všechna tato políčka zařadíme na začátek, takže když budeme chtít vypsat pořadí samotných políček se vzorci, přeskočíme akorát počáteční část a začneme vypisovat až od prvního políčka se vzorcem.
Uvědomíme si, že když hledáme takové pořadí, tak určitě můžeme jako první vyhodnotit políčka se samotnými čísly – vrcholy, do kterých nevede žádná hrana. Vyhodnocení políčka v naší grafové reprezentaci provedeme tak, že příslušný vrchol z grafu vymažeme, stejně jako všechny hrany, které z něj vedou. Tím se nám můžou objevit další vrcholy, do kterých už nepovede hrana, tak je pak můžeme vyhodnotit také. Je to jistě korektní krok, protože vrchol, do kterého nevede žádná hrana, nezávisí buď na žádném jiném políčku, a nebo na už vyhodnocených políčkách (a tedy smazaných z grafu).
Jak bude vypadat celý algoritmus? Nejprve projdeme všechny vrcholy grafu a ty, do kterých nevede žádná hrana, si zařadíme do fronty. Postupně vrcholy z fronty odebíráme. Vždy se podíváme na každou hranu vedoucí z odebraného vrcholu, smažeme ji, a pokud to byla jediná hrana vedoucí do následujícího vrcholu, tak jej také přidáme do fronty. Zastavíme se, když bude fronta prázdná. Buď jsme prošli celý graf a našli správné pořadí, nebo nám v grafu nějaké vrcholy zůstaly, ale do každého vede hrana. V tom případě se v grafu vyskytuje cyklus. To znamená, že nějaká políčka v tabulce na sobě závisejí navzájem a nejde z nich vybrat jedno, které bychom mohli vyhodnotit jako první. Pokud tedy existuje nějaké pořadí, ve kterém můžeme políčka vyhodnotit, náš algoritmus ho najde, a pokud neexistuje, tak to taky odhalíme.
Jaká bude časová složitost našeho algoritmu? Graf vytvoříme v lineárním čase vůči počtu políček. Pak ho jednou v lineárním čase projdeme, abychom zařadili do fronty vrcholy, které na žádných jiných nezávisí – políčka s čísly. Když pak budeme graf procházet, tak každý vrchol nejvýše jednou zařadíme do fronty a jednou ho z ní vymažeme. Než ho ale vymažeme, musíme se podívat na všechny hrany, které z něj vedou. Těch ale může být až O(n), pokud na tomto vrcholu závisí všechny ostatní. Můžeme se na to však podívat z druhé strany, tedy spočítat, kolikrát se na každý vrchol podíváme při mazání jiného vrcholu. Protože každý vrchol závisí nejvýše na dvou dalších, tak se na něj podíváme nejvýše dvakrát, než ho zařadíme do fronty. Přestože nám tedy mazání některých vrcholů může trvat dlouho, dohromady bude časová složitost algoritmu lineární, O(n).