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

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

Přinášíme vám řešení čtvrté série tohoto ročníku KSP. Čtení vzorových řešení je skvělý způsob, jak se naučit nové způsoby řešení úloh, a tak neváhejte a začtěte se do nich.

Připomínáme, že seriál můžete za menší bodové ohodnocení stále odevzdávat a to až do konce ročníku, takže jeho vzorové řešení vám vydáme až po skončení celého ročníku. Také odevzdávání úlohy 33-4-X1 Koření a recepty jsme prodloužili až do konce 5. série, zatím vám namísto řešení přinášíme nápovědu.

Řešení úloh

Teoretická úloha33-4-1 Ohňostroj (Zadání)

Odpalovací zařízení mají definované pořadí, říkejme mu třeba „zleva doprava“. Nejprve zařídíme, aby kdykoliv někdo zmáčkne tlačítko na kterémkoliv zařízení, dozvědělo se o tom nejlevější zařízení. To zařídíme vysláním signálu od tlačítka doleva. V každém tiku se každé zařízení podívá na svého pravého souseda. Pokud už je soused ve stavu „zmáčknuto“, samo také přejde do stavu „zmáčknuto“. Signál po nejvýše N tikách doputuje k nejlevějšímu zařízení.

Dvě místa současně

Teď vyřešíme, jak zasynchronizovat nějaká dvě zařízení ℓ a p, kde ℓ je nalevo od p. Tedy jak způsobit, aby nějaká událost v zařízení ℓ způsobila jinou událost současně v zařízeních ℓ a p. Provedeme to takto: Vyšleme z ℓ směrem k p dva signály, říkejme jim třeba A a B, přičemž A se bude šířit plnou rychlostí a B rychlostí poloviční (posune se o jeden krok za dva tiky). Jakmile A dorazí do p, „odrazí se“ a bude pokračovat jako A′ stejnou rychlostí zpět k ℓ. Všimněte si, že A′ se vrátí do ℓ přesně v okamžiku, kdy B dorazí do p.

Program (C++)

Simulátor odpalovacích zařízení (C++)

Všechna místa současně

Když už umíme synchronizovat dvojice zařízení, můžeme použít metodu Rozděl a panuj a vyřešit problém pro celou posloupnost. Uvažujme interval zařízení ⟨ℓ,p), na počátku je ℓ nejlevější zařízení a p těsně za nejpravějším (takové zařízení doopravdy neexistuje, ale poslední si na něj může hrát). Nalezneme zařízení s v polovině intervalu a to zasynchronizujeme s ℓ. Tím se nám interval rozpadne na poloviny ⟨ℓ,s) a ⟨s,p). V obou polovinách pak současně spustíme tentýž algoritmus.

Pokud bude počet zařízení N=2k, po k iteracích se dobereme k jednoprvkovým intervalům (ke všem současně), a tehdy už může každé zařízení rovnou odpálit.

Zbývá dořešit hledání středu. K tomu můžeme použít opět šíření signálů různými rychlostmi: z levého okraje intervalu vyšleme doprava signál C plnou rychlostí a signál D rychlostí třetinovou. Signál C se od pravého okraje odrazí jako C′ a na cestě zpět se potká se signálem D přesně v polovině intervalu (pokud si vrcholy očíslujeme 0, …, N-1 a N bude sudé, potkají se ve vrcholu N/2).

Každá iterace tohoto algoritmu potřebuje lineární počet tiků vzhledem k délce intervalů, které se zrovna zpracovávají. Celková časová složitost tedy bude O(N+N/2+N/4+… +1) = O(N).

Kdyby N nebylo mocninou dvojky, museli bychom se vyrovnat s nerovnoměrným dělením intervalů. To ale není nijak těžké: při hledání středu v intervalu liché délky se zastavíme na (N-1)/2, a dokonce poznáme, že se nám to stalo, podle toho, že se signály nepotkají přesně na hranici periody signálu D. Pak můžeme prostřední vrchol intervalu vynechat a zpracovat zbylé stejně velké části identicky. Nakonec nám zbudou jednoprvkové intervaly a mezi některými z nich osamocené vrcholy. Stačí tedy, aby zařízení místo odpálení ohňostroje nastavila nějakou značku „připravit se“ a v následujícím tiku odpálí každé zařízení, které buďto tuto značku má, nebo ji vidí u svého souseda. Program si tím ovšem komplikovat nebudeme.

Program (C++)

Úlohu připravili: Jirka Kalvoda, Martin „Medvěd“ Mareš

P.S.: Medvěd děkuje svému mladšímu já za inspiraci v podobě úlohy P-II-2 z 56. ročníku MO kategorie P.

Praktická opendata úloha33-4-2 Firewall (Zadání)

V této úloze bylo úkolem zpracovávat tři události – blokaci nebo povolení nějakého rozsahu IP adres a dotaz na to, jestli je daná IP adresa povolená. Nejdříve si ukážeme dvě pomalejší řešení, která jsou ale zajímavá nápadem, a nakonec předvedeme řešení pomocí líných stromů, které je již dostatečně rychlé na vyřešení všech vstupů.

Nejprve si však povíme, jak s IP adresami efektivně pracovat. Už v zadání jsme zmínili, že IPv4 adresy jsou vlastně 32bitová čísla a jejich běžná reprezentace v programu je buď čtveřice bajtů, nebo přímo jedno čtyřbajtové číslo (třeba uint32_t v Céčku). Pokud načítáme IPv4 adresu jako čtveřici čísel oddělených tečkami, tak si je na 32bitové číslo můžeme převést třeba pomocí funkce ip níže (každý bajt jen posuneme na správné číslo a uděláme bitový or).

Stejně tak si můžeme z počtu bitů v CIDR formátu (číslo K za lomítkem) vyrobit masku, která bude mít prvních K bitů jedničky a zbytek nuly. Můžeme to udělat třeba jako ve funkci mask níže.

typedef unsigned char byte;
uint32_t ip(byte a, byte b, byte c, byte d) {
  return (a << 24) | (b << 16) | (c << 8) | d;
}
uint32_t mask(int K) {
  if (K > 0)
    return (0xFFFFFFFF << (32-K)) & 0xFFFFFFFF;
  else
    return 0;
}

K čemu nám takové reprezentace jsou? Můžeme s nimi rychle provádět bitové operace. Například test, jestli adresa patří do nějaké sítě, provedeme tak, že uděláme bitový and adresy a masky sítě. Pokud se výsledné číslo shoduje s prefixem sítě, adresa do ní skutečně patří:

if ((adresa & maska) == prefix) { je v síti... }

A nakonec, pokud chceme otestovat, jestli je K-tý bit adresy jednička, můžeme to udělat třeba takto (indexujeme od jedničky):

if (adresa & (1 << (32-K))) { K-tý bit je 1... }

Teď již máme nějaký základní arzenál pro rychlé operace s IPv4 adresami, pojďme se podívat na řešení. Abychom si zjednodušili popis, tak odteď budeme používat výraz operace pro blokaci nebo povolení.

Přímočaré řešení

Protože se operace navzájem přepisují, tak nás pro každý dotaz zajímá jen ta poslední operace, která dotazovanou IP adresu ovlivnila. Můžeme si tedy všechny operace ukládat do seznamu a pro každý dotaz celý seznam projít. Pro každou operaci otestujeme, jestli dotazovaná adresa patří do podsítě, na které byla operace provedena – pokud ano, tak si zapamatujeme typ operace a pokračujeme dál. Nakonec jen vypíšeme poslední zapamatovanou operaci.

Lze lehce nahlédnout, že toto řešení vždy vrátí správnou odpověď, ale bude muset pro každý dotaz projít všechny doposud provedené operace. Pokud si jako N označíme počet řádků na vstupu a budeme předpokládat, že polovina z nich jsou operace a druhá polovina dotazy, tak můžeme odhadnout, že zpracování jednoho dotazu bude trvat řádově O(N) a celkově se tak dostaneme na čas O(N2).

Zlepšit to sice můžeme procházením seznamu odzadu a zastavením se u první operace ovlivňující dotazovanou adresu (předchozí operace nás již nezajímají), ale není těžké vymyslet vstup, na kterém i tak musíme pro podstatnou část dotazů projít skoro všechny doposud provedené operace (takové vstupy jsme v úloze skutečně vyráběli). Tudy správná cesta nevede.

Pole všech adres

V prvním řešení bylo provedení operace okamžité, ale dotaz nám trval až O(N), pojďme dotazy zrychlit… třeba až na O(1). Možných IPv4 adres je 232 (neboli něco přes 4 miliardy). Když si budeme pro každou adresu držet v poli jednobajtové true nebo false udávající, jestli je adresa aktuálně povolená nebo blokovaná, tak nám na to stačí přesně 4 GiB paměti, což dnes většinou není problém. A i jeden bajt je plýtvání, ve skutečnosti nám stačí jen jeden bit informace a spotřebovanou paměť tak můžeme snížit na 512 MiB (ale je potřeba umět přistupovat k jednotlivým bitům, typicky pomocí nějakých bitových triků s andy a ory, záleží na jazyku).

Na začátku si celé pole vynulujeme, abychom reprezentovali, že všechny adresy jsou blokované. Pro operaci blokace pak přepíšeme správnou část pole nulami, pro operaci povolení jedničkami. Dotaz je pak jen vytažení správného prvku pole – jednička značí povolenou adresu, nula blokovanou.

U tohoto řešení je asi na první pohled jasné, že bude také vracet správné výsledky, ale s rychlostí na tom nebude nejlépe. Pokud si jako U označíme velikost univerza (v tomto případě 4 miliardy adres), tak jedna operace může trvat až čas O(U), celkově jsme tak skončili na časové složitosti O(NU). To na vyřešení všech vstupů této úlohy nestačilo (a například pro IPv6 adresy by taková složitost byla úplně nepoužitelná).

Líné stromy

Problémem předchozího řešení bylo to, že jsme zbytečně trávili čas s „tapetováním“ velkých částí paměti nulami nebo jedničkami. Přitom by nám pro některé části stačilo vědět „od X do Y jsou adresy zakázané“. Na takové věci se bude hodit reprezentovat IP adresy pomocí stromů.

IPv4 adresa rozepsaná na bity reprezentuje průchod binárním stromem o hloubce 32 – nechť třeba nulový bit znamená doleva a jedničkový doprava. Podsíť s prefixem délky K v takovém stromě je vlastně podstrom začínající vrcholem v hloubce K, ke kterému jsme došli pomocí prefixu této sítě.

Operace si ve stromě budeme reprezentovat jako vrcholy říkající „všechno pode mnou je blokováno/povoleno“. Musíme ale vyřešit, jak při dotazu na nějakou IP adresu poznat poslední operaci, která se této IP adresy týkala. To se dá udělat více přístupy, ale my si ukážeme řešení pomocí líného stromu.

Idea je vlastně triviální: vrcholy stromu si budeme vyrábět až ve chvíli, kdy budou potřeba, a nikdy si nedovolíme mít ve vrcholu operaci, která by byla přepsaná nějakou novější operací pod ní. Při dotazu pak díky tomu bude platit, že první operace, kterou při procházení stromu potkáme, je platná a můžeme ji rovnou vrátit jako odpověď.

V momentě, kdy budeme přidávat novou operaci, vydáme se stromem k vrcholu představujícímu podsíť této operace. Pokud cestou potkáme neexistující vrchol, tak ho založíme. Pokud potkáme vrchol s jinou operací, musíme tento jiný vrchol „rozhrnout“. Jednoduše zrušíme operaci v současném vrcholu, ale předtím zkopírujeme tuto operaci do obou jeho synů (které případně založíme, pokud ještě neexistují). Pak můžeme pokračovat v původním průchodu (který pravděpodobně do jednoho ze synů sestoupí a bude se tak opakovat podobná situace, dokud nedojdeme až k vrcholu, kde se chceme zastavit – je to něco jako když sněžný pluh rozhrnuje sníh na obě strany :)).

Jak rychlé takové řešení je? Každá operace i dotaz projde stromem jen jednou, hloubka stromu pro univerzum o velikosti U je log U, takže celkový čas je O(N log U). To již stačilo k vyřešení všech vstupů v řádu jednotek sekund. Na implementaci se můžete podívat v přiloženém programu.

Poznámka: Tento strom je nazývaný líný proto, že operace na intervalech ukládáme vždy co nejblíže ke kořeni a tím si ušetřujeme práci. Poctivě je propíšeme do nižších vrstev až ve chvíli, kdy je to nutné.

Program (C)

Úlohu připravili: Michal Kodad, Martin Koreček, Jirka Sejkora, Jirka Setnička

Teoretická úloha33-4-3 Mraveniště na kopci (Zadání)

Nejprve si uvědomíme, že jednotliví mravenci jsou nezávislí (a taky určitě i silní, ale to je pro naši úlohu nepodstatné). Tedy když vyšleme nějakého mravence z mraveniště, tak pravděpodobnost toho, že skončí v nějakém vrcholu, nijak nezávisí na tom, kam došli předcházející mravenci (a ani kolik jich bylo).

Představme si, že známe pravděpodobnost p, se kterou mravenec dorazí do cíle. Pokud bychom vyslali jen tohoto jednoho mravence, bude střední hodnota počtu mravenců dorazivších do cíle právě p.

Dále využijeme linearity střední hodnoty: Vyšleme-li K/p mravenců, dorazí jich do cíle ve střední hodnotě přesně požadovaných (K/p) ·p = K. Protože vyslaných mravenců musí být celočíselně, vyšleme jich ⌈K/p ⌉ (nejbližší celé číslo ≥ K/p).

Nyní se podívejme, jak spočítat onu pravděpodobnost p.

Využijeme dynamického programování. Pro každý vrchol grafu si spočítáme, jaká je pravděpodobnost toho, že jím mravenec projde. Mraveništěm projde určitě, tedy s pravděpodobností 1. Pro ostatní vrcholy sečteme pravděpodobnosti podle toho, odkud mravenec přijde. Předpokládejme, že z vrcholu V vede do aktuálního vrcholu hrana. Pravděpodobnost toho, že mravenec přijde po hraně z vrcholu V je pV / sV, kde pV je pravděpodobnost průchodu mravence vrcholem V a sV je počet hran, které z V vedou. Když tedy známe pravděpodobnosti pro všechny předky, zvládneme spočítat i pravděpodobnost aktuálního vrcholu.

Jak ale zařídit, abychom počítali vrcholy tak, že vždy budeme mít spočítány všechny předky? V případě, že cestičky jsou stromem, stačí udělat průchod do šířky či do hloubky z mraveniště. V obecném případě budeme hledat možné rozložení nadmořských výšek tak, aby všechny hrany vedly z kopce. Tedy můžeme najít topologické uspořádání grafu, o němž se můžete dočíst v kuchařce Grafy. Jelikož graf neobsahuje cyklus, tak musí alespoň jedno existovat. V tomto pořadí pak už můžeme bez problémů spočítat pravděpodobnosti.

Pro naši úlohu ale stačí použít i jednodušší postup než hledání topologického uspořádání. Uděláme průchod do hloubky z cílového vrcholu, který bude procházet po hranách v opačném směru než mravenci. U každého vrcholu nejprve provedeme rekurzi do všech předků (v případě, že jsme je ještě nenavštívili) a pak spočteme pravděpodobnost pro aktuální vrchol. Každého předka jsme tedy buď spočítali již někdy dříve, nebo jsme ho spočetli teď rekurzí. Budeme mít tedy dostatek dat pro výpočet pravděpodobnosti aktuálního vrcholu.

Úlohu připravili: Jirka Kalvoda, Jirka Setnička

Praktická opendata úloha33-4-4 Prohledávání KSP webu (Zadání)

Úloha byla implementačně založená – nemuseli jste nic světoborného vymýšlet, ale spíše si osahat komunikaci s webem. Zdrojový kód a popsané řešení se vztahuje k řešení psanému v jazyce Python. Jiné jazyky můžou mít řešení této úlohy trochu lehčí či těžší nebo mít jiné záludnosti.

Řešení se bude skládat ze dvou částí. První část stáhne všechny stránky z webu, předpřipraví je do nějakého formátu, který bude příjemný na odpovídání dotazů, a uloží výstup do souboru. Druhá část programu bude už jen číst tento soubor a odpovídat na dotazy.

První krok je zjištění všech URL, ze kterých chceme stahovat. Při krátkém průzkumu našeho webu zjistíme, že URL má tento tvar: Začátek bude /z/ulohy nebo /h/ulohy (pro dvě různé kategorie), následovaný číslem ročníku a nakonec určením, jestli chceme zadání, řešení či komentáře spolu s číslem série. Nějaké nástroje dokonce umí stáhnout úplně vše z daného kořenové URL, ale to využít nepotřebujeme.

Dále dané stránky musíme stáhnout. Na toto využijeme knihovnu requests (standardní Pythoní knihovna je pro jednoduché použití spíše nevhodná a lehce se můžete něčím střelit do nohy, requests je lepší).

Nyní na každé stránce stačí najít div s identifikátorem content. Pro obecné parsování HTML bychom doporučili nějaký parser, například knihovnu BeautifulSoup, ale protože teď potřebujeme jen vyseknout div se správným identifikátorem ze stránek, které mají všechny stejnou strukturu, je jednodušší to v tomto případě udělat regexem (neboli regulárním výrazem). Dejte si však pozor, že obecné parsování HTML jen pomocí regexu napsat nejde (regulární jazyky jsou v Chomského hierarchii jazyků slabší, než bezkontextové jazyky, do kterých lze řadit HTML) a nedoporučujeme se o to ani pokoušet.

Víme, že chceme zahodit vše, co je před tagem div s identifikátorem content a poté zahodit vše od momentu, kde začíná div s identifikátorem sidebar-wrapper.

Nyní chceme odstranit HTML entity. Ty odstraníme tímto regexem &.*?; (otazník za hvězdičkou říká, že chceme hledat nehladově – najít nejkratší úsek splňující kritérium). Uvědomme si, že znaky &<> a další jsou speciální znaky HTML, takže pokud je chceme mít v textu, tak je musíme mít napsané HTML entitou. Nakonec dalším regexem <.*?> smažeme všechny tagy. Pozor, v Pythonu standardně tečka nebere znak nového řádku (newline), proto musíme tuto funkci explicitně zapnout nepovinným parametrem flags.

Poté již stačí procházet jednotlivá slova regexem \w+ a házet si je třeba do slovníku.

První část našeho programu se spouští s parametrem -ini, protože tento krok děláme většinou jednou a pak již program pracuje „offline“.

Druhá část programu je již jednoduchá – načtu si předpřipravený soubor třeba do slovníku a odpovídám na dotazy. Celkový počet slov je vcelku malý – kolem 60 tisíc slov, takže se moc nevyplatí vymýšlet něco speciálního (třeba slova binárně vyhledávat).

Program (Python 3)

Úlohu připravili: Michal Kodad, Martin „Medvěd“ Mareš, Jirka Sejkora, Jirka Setnička

Teoretická úloha33-4-X1 Koření a recepty (Zadání)

Toky a řezy

Zopakujeme si část algoritmů a teorie okolo toků a řezů. Budeme se řídit podle kapitoly o tocích v Průvodci labyrintem algoritmů.

Mějme nějakou síť s vrcholy V, orientovanými hranami E, nezápornými kapacitami hran c(e), a konečně zdrojem z a stokem neboli spotřebičem s.

Pro množiny vrcholů A,B označíme množinu hran vedoucích z A do B jako E(A,B) = { (a, b)∈E | a∈A, b∈B}.

Řez v síti budeme říkat každé množině hran R⊆ E, jejichž odebrání přeruší všechny cesty ze zdroje do stoku. (Pokud v síti žádná taková cesta nebyla, i prázdná množina je řez.)

Pokud vrcholy beze zbytku rozdělíme na množiny A a B tak, aby zdroj ležel v A a stok v B, hrany z A do B budou tvořit řez. Každá cesta ze zdroje do stoku totiž někde musí přejít z A do B, takže obsahuje aspoň jednu hranu z E(A,B). Takovým řezům říkáme elementární řezy.

Navíc platí, že podmnožinou každého řezu je nějaký elementární řez. To dokážeme snadno: Mějme nějaký řez F. Označme A množinu všech vrcholů dosažitelných ze zdroje v grafu G-F. Zřejmě z∈A a snot∈A, jinak by totiž řez nepřeřízl všechny cesty ze z do s. Přitom všechny hrany elementárního řezu E(A,B) musí ležet v F (jinak by množinu A šlo rozšířit).

Řezům můžeme také přiřazovat kapacity. Pro libovolnou podmnožinu hran F⊆ E (tedy i pro řez) položíme c(F) := ∑e∈F c(e). Speciálně se nám to bude hodit pro elementární řezy, tak zavedeme zkratku c(A,B) := c(E(A,B)).

Základní úlohou týkající se řezů je nalezení minimálního řezu, tedy řezu o nejmenší možné kapacitě. Všimněte si, že alespoň jeden z minimálních řezů je elementární. To proto, že každý minimální řez obsahuje jako podmnožinu nějaký elementární řez, jehož kapacita nemůže být větší (hrany mají nezápornou kapacitu).

Nyní mějme nějaký tok f. Definujme průtok přes libovolný elementární řez E(A,B) tak, že tok po hranách z A do B započítáme kladně a tok v protisměru záporně:

fΔ(A,B) := (∑e∈E(A,B) f(e)) - (∑e∈E(B,A) f(e)).

Pak platí (důkazy najdete v Průvodci):

Koření a recepty

Vztahu mezi toky a řezy teď využijeme k řešení úlohy. Nejprve vytvoříme vhodnou síť, složenou ze čtyř vrstev: zdroj, vrstva koření (každý druh koření zde bude mít svůj vrchol), vrstva receptů (vrcholy pro jednotlivé recepty), stok. Přitom:

Než nastavíme kapacity, uvědomíme si následující vlastnost grafu: Nechť vybereme nějaká koření a nějaké recepty. Sestrojíme množinu hran R tak, že do ní dáme hrany vybraných koření a nevybraných receptů. Nahlédneme, že vybraná koření jsou dostatečná k uvaření vybraných receptů právě tehdy, když R je řez. To proto, že kdykoliv by vybraný recept závisel na nevybraném koření, vedla by nějaká nepřeříznutá cesta ze zdroje do stoku (totiž ze zdroje hranou koření, pak hranou závislosti a hranou receptu do stoku). Naopak jakákoliv nepřeříznutá cesta odpovídá porušené závislosti. Tady se hodí všimnout si, že kvůli orientaci hran jsou všechny cesty tvořené třemi hranami.

Nyní nastavíme kapacity takto:

Minimální řez určitě nebude mít nekonečnou kapacitu (protože všechny hrany koření tvoří řez o konečné kapacitě), takže bude používat jenom hrany koření a receptů. Minimální řezy tedy odpovídají výběru koření a receptů podle požadavků úlohy. Jejich kapacita minimalizuje výraz

(cena použitých koření ) + (cena nepoužitých receptů ).

Jelikož součet cen všech receptů je konstanta, je to ekvivalentní s minimalizací

(cena použitých koření ) - (cena použitých receptů ).

A jelikož min(-x,-y) = -max(x,y), je to ekvivalentní s maximalizací

(cena použitých receptů ) - (cena použitých koření ),

což je přesně cílem úlohy.

Zbývá dořešit, jak minimální řez nalezneme. Nejdřív najdeme maximální tok. Jelikož Fordův-Fulkersonův algoritmus je pro obecné kapacity velmi pomalý, použijeme Dinicův algoritmus. Na nalezený tok pak spustíme Fordův-Fulkersonův algoritmus. Ten se nutně zastaví po prvním průchodu – maximální tok už nejde zlepšit. I tak nám řekne něco užitečlného: množina vrcholů, do kterých se dostal, určuje jeden z minimálních řezů.

Nakonec rozebereme složitost. Označme K počet druhů koření, R počet receptů a Z počet závislostí. Náš graf má n=K+R+2 vrcholů a m=K+R+Z hran. Dinicův algoritmus běží v čase O(n2m). Jeden průchod F-F algoritmu stojí O(m), což je asymptoticky méně. Časová složitost celého algoritmu je tedy O(n2m) = O((K+R)2(K+R+Z)). Pokud samostatně ošetříme koření a recepty, které se neúčastní žádné závislosti, bude platit K+R ∈O(Z), takže odhad složitosti můžeme zjednodušit na O((K+R)2·Z). Paměti nám stačí lineárně s velikostí grafu, tedy O(K+R+Z).

Úlohu připravili: Martin „Medvěd“ Mareš, Tom Sláma

Seriálová úloha33-4-S Raytracing (Zadání)

Odkazy na referenční implementace úkolů ze všech dílů seriálu naleznete v řešení posledního dílu seriálu.