Pátá série třicátého čtvrtého ročníku KSP

Řešení úloh


Praktická opendata úloha34-5-1 Lehátka (Zadání) (Komentáře)


Není zřejmé, jak optimální vzdálenost najít „přímo“, ale pro danou minimální vzdálenost mezi hrochy snadno ověříme, zda ji umíme dodržet. Můžeme postupovat následujícím způsobem.

Binárně vyhledáme optimální vzdálenost hrochů. Víme, že tato hodnota bude určitě někde mezi nulou a vzdáleností krajních lehátek. Vyzkoušíme, zda umíme dodržet vzdálenost uprostřed mezi těmito hodnotami. Pokud ano, můžeme zkoušet vyšší hodnoty. Pokud ne, musíme zkusit nižší. Postupně půlíme interval zkoušených hodnot, dokud nenajdeme samotné optimum.

Jak přesně ověříme, že danou vzdálenost umíme dodržet? Můžeme opět použít binární vyhledávání. Určitě si nepohoršíme, když prvnímu hrochovi věnujeme první lehátko. Binárním vyhledáváním zjistíme, jaké nejbližší lehátko je v požadované vzdálenosti nebo dál. Tím jsme našli lehátko pro druhého hrocha a postupujeme podobně dál, dokud nezjistíme, že máme místo pro všechny hrochy, nebo nám došla lehátka, a požadovaná vzdálenost je tak příliš vysoká.

Pokud jako V označíme vzdálenost mezi krajními lehátky, celkový čas běhu našeho algoritmu bude O(H log V log L), protože binárně vyhledáváme v intervalu délky V a pro každou zkoušenou vzdálenost přiřadíme (až) H hrochům binárním vyhledáváním lehátka z L možností.


Praktická opendata úloha34-5-2 Veletrh (Zadání) (Komentáře)


Označíme N počet vrcholů grafu (místností), M počet hran mezi nimi, U počet událostí a Tmax čas konce poslední události. Hledáme trasu (nějaký plán toho, kdy se chceme přesunout kam a jak dlouho tam počkat) s co nejvyšším ziskem – tak budeme říkat počtu minut událostí, kterých jsme během plánu zúčastnili.

Prohledávání časoprostoru

Nejprve nadefinujeme δt,v, což je zisk z t-té minuty strávené ve vrcholu v. Tedy 1, pokud tam zrovna probíhá událost, jinak 0.

Nyní budeme počítat čísla Zt,v: maximální možný zisk trasy, která na konci t-té minuty (0≤ t≤ Tmax) skončí ve vrcholu v. Přitom Zt,v = -∞, pokud žádná taková trasa neexistuje.

Nejprve prozkoumáme případ t=0, tedy první minutu veletrhu. Tu můžeme trávit pouze ve vrcholu 0, protože z jiného nestihneme přijít. Takže Zt,0 = δt,0 a Zt,v = -∞ pro všechna v≠ 0.

Nyní uvažujme t>0. Optimální trasa může končit buďto minutou čekání ve vrcholu v, anebo přesunem z nějakého vrcholu u. Pokud končí čekáním, máme z trasy zisk Zt-1,v + δt,v. Pokud trasa končí přesunem po hraně délky u,v, zisk je roven Zt-ℓu,v,u (což je -∞, pokud t < ℓu,v). Zkombinováním obou možností dostaneme:

Zt,v = max(Zt-1,v, maxu Zt-ℓu,v,u).

Jak dlouho nám bude trvat spočítat všechna Zt,v? Pro každý čas t procházíme všechny vrcholy v, pro každý vrchol v zkoumáme všechny do něj vedoucí hrany. Celkem tedy pro každé t projdeme každou hranu právě jednou. Výpočet všech Zt,v tedy trvá O(Tmax·(N+M)).

Pak už stačí vyzkoušet všechny vrcholy, kde jsme mohli být v poslední minutě veletrhu, a najít ten s maximálním ziskem. To nám časovou složitost nezkazí.

Nakonec musíme vymyslet, jak optimální trasu vypsat. Při výpočtu Zt,v si budeme pamatovat, pro jaký konec trasy se nabylo maxima – tedy zda jsme čekali ve v, nebo přišli z nějakého u. Pomocí toho pak můžeme optimální trasu rekonstruovat od konce k začátku. To opět složitost nepokazí.

Naše první řešení tedy pracuje v čase O(Tmax·(N+M)). Pojďme ho překonat – zejména se chceme zbavit závislosti na rozsahu časů.

Předvýpočet vzdáleností

Zbavíme se omezení, že hrany vedou jenom mezi některými vrcholy. Pro každou dvojici vrcholů spočítáme jejich vzdálenost, tedy délku nejkratší cesty. Na to se hodí například Floydův-Warshallův algoritmus pracující v čase O(N3). Najdete ho v kuchařce o dynamickém programování.

Od této chvíle můžeme předpokládat, že se lze odkudkoliv kamkoliv dostat přímo. Jen musíme při zavěrečném vypisování trasy umět přesuny rozložit na jednotlivé hrany – to je ale snadné, pokud si ve F.-W. algoritmu budeme pamatovat předchůdce vrcholu na nejkratší cestě.

Lemma o trpělivosti

Nyní ukážeme, že pokud nějakou událost navštívíme, nemusíme z ní nikdy netrpělivě odcházet před koncem. Přesněji řečeno, alespoň jedna z optimálních tras zůstane na každé navštívené události až do konce.

Důkaz provedeme tak, že vezmeme nějakou optimální trasu a postupně ji budeme upravovat, než bude „trpělivá“. Dokud není, vybereme nějakou událost ui, na které nezůstane do konce. Trasu upravíme, aby na této události vydrželo o minutu déle. Tím pádem přijde o minutu později na následující událost ui+1. Celkově se tedy zisk nezměnil. Jen pozor na případ, kdy jsme na ui+1 trávili jen její poslední minutu – tehdy ui+1 z trasy odstraníme a z ui jdeme rovnou na ui+2. Tam nepřijdeme později než v původní trase.

Opakováním tohoto postupu zařídíme, aby trasa na každé události čekala až do konce.

Rychlejší řešení

Naše rychlejší řešení nebude zkoumat všechny polohy v časoprostoru (dvojice vrchol a čas), nýbrž jenom konce událostí. Opět nás bude zajímat maximální zisk, jakého umíme dosáhnout trasou, která končí daným koncem události.

Události procházíme v pořadí časů začátků. Mějme událost u ve vrcholu v probíhající v časovém intervalu < t1, t2 >. Probereme všechny konce událostí, ze kterých dokažeme přijít na u.

To uděláme tak, že projdeme všechny vrcholy v'. Nechť u' je událost ve v' s časovým intervalem < t1', t2' >. Pokud z jejího konce odcházíme do v, přijdeme tam v čase t2' + 1 + d, kde d je předpočítaná vzdálenost z v' do v. Z události u tedy stihneme posledních p = t2' + d - t2 minut. Pokud vyjde p≤ 0, nemá tedy smysl z u' na u chodit.

Stačilo by tedy projít všechny vrcholy v' a události u' v nich. Všechny u' jsme už dříve zpracovali, takže známe maximální zisky tras končících v nich. Stačí k nim připočítat zisk z části události u, kterou stihneme, a vybrat maximum přes všechny u'. Jen nesmíme zapomenout, že předchozí událost může být také ve v, takže do maxima ještě započitáme zisk z předchozí události ve v plus zisk z celé u.

Tento algoritmus by běžel v čase O(N3 + U2) – nejdříve by v čase O(N3) předpočítal vzdálenosti. Pak by v O(U log U) setřídil události. A nakonec by pro každou událost zkoumal až U předchůdců.

Ještě rychlejší řešení

Zkoumání tolika předchůdců si můžeme ušetřit. Kdykoliv zpracujeme událost, poznamenáme si ke všem vrcholům, kdy se do nich umíme dostat z konce aktuální události. Každý vrchol si tedy bude pamatovat možné časy příchodů z minulých událostí. Když pak zpracováváme další událost, podíváme se na časy příchodu do jejího vrcholu a odebíráme od začátku seznamu ty příchody, které jsou dostatečně brzké. Všimneme si, že žádný z nich se nevyplatí použít pro pozdější událost ve stejném vrcholu.

Za každou událost vytvoříme příchody do všech vrcholů. Celkem tedy vznikne O(UN) příchodů. Vytvořit i odebrat jeden příchod stojí konstantní čas. Kromě toho trávíme každou událostí už jenom konstantní čas.

Celkem tedy výpočtem strávíme čas O(N3 + U log U + UN). Do toho se jistě vejde i závěrečné vypsání optimální trasy. Toto řešení je lepší než předchozí, kdykoliv se v každém vrcholu koná aspoň jedna událost.


Teoretická úloha34-5-3 Jednoznačné cestování (Zadání) (Komentáře)


Nejprve zkusme přiřadit hranám ceny tak, aby žádné dvě cesty neměly stejnou cenu. Cesta v našem případě bude posloupnost po sobě jdoucích hran, která nenavštíví žádný vrchol vícekrát. Zatím nebudeme hledět na to, aby nejlevnější cesta byla skutečně i tou nejkratší. Všimneme si, že různé cesty mají různou množinu hran, přes kterou prochází. Tedy určitě když každá množina hran bude mít unikátní celkovou cenu, tak máme vyhráno. Nyní si můžeme pomoct binárním zápisem čísel. Když i-té hraně přiřadíme cenu 2i, tak součet libovolných cen bude v binárním zápise obsahovat jedničky na pozicích příslušných hran. Tedy když dostaneme do ruky nějakou celkovou cenu, zvládneme poznat, za které hrany platíme pouhým pohledem na binární zápis ceny.

Jak ale zařídit, aby nejlevnější cesta byla skutečně nejkratší? Když ke každé ceně hrany přičteme nějaké opravdu velké číslo, tak se rozdíly v cenách hran mohou stát zanedbatelné. Projít k hran bude stát pouze k-krát moc a nějaké drobné, zatímco projít k+1 hran bude stát k+1 krát moc a už nebude záležet na tom, jaké drobné jsou k tomu navíc. V původních cenách může celá cesta stát nejvýše:

20 + 21 + 22 + ...+ 2m-1 = 2m - 1.

Validní řešení získáme, když k cenám přičteme 2m. Cena i-té hrany tedy bude 2m + 2i. Snadno nahlédneme, že stále dvě různé cesty mají různou celkovou cenu.

Největší použitá cena je 2m+2m-1 ∈Θ(2m) a časová složitost algoritmu je evidentně lineární.

Předchozí řešení můžeme vylepšit drobnou optimalizací – ceny nebudeme přiřazovat hranám ale vrcholům. Ovšem my vybíráme poplatky pouze na hranách, jak si zaúčtovat průchody za vrcholy? Můžeme polovinu zaúčtovat při vstupu a polovinu při odchodu z vrcholu. Všimneme si, že až na první a poslední vrchol vybereme za každou cestu správně. Ovšem nám stačí, aby byly ceny unikátní jenom mezi každou dvojicí vrcholů, takže to vlastně znamená, že z každé ceny odečteme jenom konstantu. Tím se jednoznačnost neporuší. Drobný problém je, že touto úpravou budeme chtít účtovat neceločíselné ceny, což zadání zakazuje. Ovšem když ceny vynásobíme dvěma, tedy za každou hranu zaúčtujeme součet okolních vrcholů, tak se také nic nepokazí. Na hranu spojující vrcholy s indexy x a y budeme účtovat (2n+2x) + (2n+2y) = 2x+2y+2n+1

Největší použitá cena je nejvýše 2n+1+2n+2n-1 ∈Θ(2n) a časová složitost algoritmu je stále lineární. Všimneme si, že kdyby graf obsahoval multihrany (dvě různé hrany mezi stejnou dvojicí vrcholů), tak už toto řešení nefunguje, kdežto řešení před optimalizací stále ano. Můžete si rozmyslet, jak řešení opravit, aby fungovalo i pro multihrany.

V předchozích úvahách jsme se snažili zajistit, aby každá cesta mezi dvojicí vrcholů měla unikátní cenu. Ovšem zadání po nás chce pouze to, aby nejlevnější cesta byla unikátní. Pojďme využít této vlastnosti na nalezení algoritmu, který generuje hranám menší ceny, byť bude běžet pomaleji.

Využijeme předchozí myšlenku o přičtení velkého čísla ke každé hraně. Budeme se tedy starat jen o nejlevnější cesty mezi dvojicemi vrcholů, protože nejlevnější cesta musí být po přičtení nutně nejkratší.

Začneme s grafem, který neobsahuje žádné vrcholy. Postupně do něj budeme přidávat hrany s nějakou cenou tak, aby nejlevnější z nejkratších cest mezi každou dvojicí vrcholů v aktuálním grafu byla stále unikátní.

Po přidání hrany jsou pro každou dvojici vrcholů dva kandidáti na nejlevnější cestu mezi nimi – původní nejlevnější cesta a nějaká cesta využívající aktuálně přidanou hranu. O původní nejkratší víme, že je jednoznačná.

Dále si ukážeme, že nejlevnější cesta využívající přidanou hranu je také jednoznačná. Nikdy se nevyplatí stejnou hranu při jedné z možností projít jedním směrem a při jiné v opačném směru, protože takovéto cesty budou nutně delší než kdybychom došli na jeden konec hrany a pak bez použití přidané hrany pokračovali do cíle. Když ovšem existuje kratší trasa, trasy přes přidanou hranu nemusíme řešit. Ze startu na začátek hrany je nejlevnější cesta unikátní, z konce hrany do cíle taky, takže celá nejlevnější trasa využívající novou hranu musí být také unikátní. Zajímá nás tedy jenom, jak nastavit cenu přidávané hrany tak, aby nejlevnější cesty přes hranu a bez hrany nebyly stejně drahé. Pokud jsou pro danou dvojici cesty jinak dlouhé či jedna z možností vůbec neexistuje, nemůže nastat žádný problém.

Dvojic vrcholů ovšem máme jen
n(n-1)
2
, takže existuje nejvýše
n(n-1)
2
cen nové hrany takových, že jejich použitím nebudou všechny nejlevnější cesty jednoznačné. Proto zvládneme vybrat číslo mezi 0 a n2 takové, že se nic nerozbije. Cena cest může být nejvýše (n-1) ·n2 < n3. Tedy když každé hraně přiřadíme cenu mezi n3 a n3 + n2, nemusíme řešit, jestli se jedná o nejkratší cestu.

Jak ovšem najít, kterou cenu hrany můžeme použít? Pro každou hranu bohužel budeme muset procházet všechny dvojice vrcholů. Můžeme si v průběhu celého algoritmu udržovat tabulku n×n, kde budeme mít pro každou dvojici vrcholů minimální cenu cesty mezi nimi v aktuálním grafu, případně informaci, že žádná cesta zatím neexistuje. Když budeme přidávat hranu, projdeme všechny dvojice vrcholů. Za pomoci tabulky spočteme minimální cenu cesty mezi nimi používající přidanou hranu, kdyby její cena byla n3. Stačí se podívat na informace o cestách ze startu a cíle do krajních vrcholů hrany. Pokud je o k levnější než původní cesta, víme, že problém nastane jen tehdy, když cena za průchod přidanou hranou bude n3+k. Pro každou z možných cen hrany si můžeme udržovat, jestli je nebo není problematická. Když spočtená cena leží v přípustném intervalu, poznačíme si jen, že tuto cenu nemůžeme použít. Pak jen sekvenčním průchodem najdeme nejlevnější nezakázanou cenu a s takovouto cenou hranu přidáme. Všechny dvojice vrcholů pak ještě jednou projdeme a případně upravíme minimální cenu cesty mezi nimi, pokud to přes nově přidanou hranu vychází lépe.

Na ceny hran se používají čísla v O(n3). Časová složitost algoritmu je O(n2m). Paměťová složitost je O(n2).


Teoretická úloha34-5-4 Dělení ve velkém (Zadání) (Komentáře)


Pokud si rozmyslíme, co dělá zdrojový program v zadání, tak chceme umět pro pole velikosti N spočítat součet celočíselných dělení přes všechny dvojice v poli. A to rychleji než kvadraticky vzhledem k velikosti pole.

V řešení využijeme toho, že hodnoty v poli nejsou větší než nějaké rozumně malé C. Můžeme tedy snadno zjistit pro každou hodnotu od 0 do C, kolikrát se mezi prvky vyskytuje. Dále také prvky setřídíme, což vzhledem k malým hodnotám můžeme udělat pomocí přihrádkového třídění.

Nyní pro každou hodnotu a mezi 0 a C chceme zjistit, jakým celkovým součtem přispějí všechny podíly, které mají a ve jmenovateli. Všimněme si, že obecně nemůže být příliš mnoho různých výsledků, kterých jednotlivé podíly mohou nabývat. Konkrétně to mohou být hodnoty 0 až C / a: jedná se o nejvýše 1 +
C
a
různých hodnot. Pro každou z nich jsme schopni říct, kolikrát přispěje do celkového výsledku. To je kolikrát se hodnota a vyskytuje krát kolik hodnot může být v čitateli, abychom získali odpovídající výsledek.

Jediné, co zatím neumíme spočítat, je počet čitatelů, které při jmenovateli a dají nějaký konkrétní výsledek, označme jej b. To jsou všechna čísla x z původního pole, pro která platí:

ab ≤ x < a(b + 1)

Stačí tedy umět zjistit počet hodnot v poli menších než nějaká konkrétní hodnota. Jakmile toto umíme, tak počet hodnot v intervalu, je počet hodnot menších než a(b + 1), od čehož odečteme počet hodnot menších než ab.

Zjistit počet hodnot menších než nějaké k ale umíme snadno. Stačí v uspořádané posloupnosti binárně vyhledávat k. Tím najdeme první výskyt k v posloupnosti, případně nejnižší vyšší číslo než k. To, na jakém indexu v seřazeném poli se tato hodnota nachází, je pak rovno počtu prvků v posloupnosti menších než k.

Jakmile sečteme počty čitatelů krát počty jmenovatelů přes všechny hodnoty jmenovatelů a přes všechny možné výsledky, dostaneme celkový výsledek.

Zatím ale vůbec není jasné, že jsme si polepšili. Mohlo by se zdát, že hodnot jmenovatelů je lineárně vzhledem k hodnotám a stejně tak možných výsledků a tedy že binární vyhledávání provádíme celkem kvadraticky-krát. Ukažme, že situace se dá zanalyzovat tak, že skutečná složitost algoritmu vyjde lépe.

Počítejme, kolikrát celkem zavoláme binární vyhledávání. To je:

C
a=0
1 +
C
a
= ∑
C
a=0
1 + ∑
C
a=0
C
a
= C + 1 + C ∑
C
a=0
1
a

Zbývající suma je harmonická řada. O té ale víme, že její součet lze shora omezit logaritmem z počtu prvků, které sčítáme.

Celkově tak dostaneme, že binární vyhledávání zavoláme O(C log C) krát. Jelikož binární vyhledávání je časově nejnáročnější operace, kterou v každém kroku provádíme, celková časová složitost je O(C log C log N), jelikož binární vyhledávání trvá O(log N), což pro malé hodnoty vychází lépe než kvadratický algoritmus ze zadání.

Paměťová složitost je O(C + N). Poznamenejme, že to by šlo zlepšit na O(N), pokud bychom si ukládali počty pouze u hodnot, které se v poli vyskytují a pro ostatní bychom krok přeskakovali.

Úlohu připravil: Ondra Sladký

Teoretická úloha34-5-S Manimujeme – vlastní animace a pluginy (Zadání) (Komentáře)


K letošnímu seriálu nevydáváme řešení v klasické podobně, nicméně můžete se podívat na programy a animace od řešitelů: http://ksp.mff.cuni.cz/viz/34-5-S/komentare