Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (2. soutěžní den) 59. ročníku

P-III-4 Mravenci

V této úloze máme spočítat zbytek, který dává jakési velké číslo po dělení číslem M=109 + 9. Nejprve si proto připomeneme základy počítání se zbytky.

Mějme dvě celá čísla A a B. Čísla můžeme jednoznačně zapsat ve tvaru A = a1M + a0 a B = b1M + b0, kde čísla a0, a1, b0, b1 jsou celá a 0≤a0, b0<M. Hodnoty a0 a b0 jsou zbytky, které dávají čísla A a B po dělení číslem M. Všimněte si, že A±B = (a1±b1)M + (a0±b0) a AB = (a1b1M + a1b0 + a0b1)M + a0b0. Proto platí: A±B dává po dělení číslem M stejný zbytek jako a0±b0 a AB dává po dělení číslem M stejný zbytek jako a0b0.

Uvedené pozorování nám v řešení úlohy umožní vyhnout se velkým číslům – budeme podle potřeby sčítat, odčítat a násobit a kdykoliv při tom nějaká průběžná hodnota překročí M, můžeme místo ní dále pracovat jenom se zbytkem po dělení M. Pro větší přehlednost nebudeme tuto úpravu v řešení nadále zapisovat. Když tedy například uvedeme v řešení „do c přiřaď a+b”, myslíme tím „do c přiřaď ((a+b)mod M).”

Základní dynamické programování

Budeme určovat počet různých cest vedoucích z bodu (0,0) na všechna ostatní místa mřížky. Počet cest vedoucích do místa (r,s) označíme f(r,s).

Pokud (r,s) leží vně naší mřížky, nelze se tam vůbec dostat a proto f(r,s)=0. Podobně f(r,s)=0 pro body, kde je umístěna překážka. Pro ostatní místa můžeme postupovat následovně: Když chceme jít na (r,s), můžeme tam přijít z (r-1,s) nebo z (r,s-1). Cesty vedoucí přes tato místa jsou jistě navzájem odlišné, takže příslušné počty cest stačí jednoduše sečíst. Platí tedy f(r,s) = f(r-1, s) + f(r,s-1).

Popsaným způsobem každou mapu vyřešíme s časovou složitostí O(RS), dostáváme tudíž řešení s celkovou časovou složitostí O(NRS), kde RS jsou rozměry mřížky a N počet mřížek na vstupu.

Cesty bez překážek

Někdy nebývá špatné podívat se na úlohu z opačného konce. Překážky způsobují, že některé cesty nejsou použitelné. Proto nejprve spočítáme všechny cesty vedoucí na (r,s) bez ohledu na překážky a následně odečteme nepoužitelné cesty.

Označme c(r,s) počet cest z (0,0) do (r,s), když neuvažujeme žádné překážky. Každá cesta, která urazí v jednom směru vzdálenost r a ve druhém vzdálenost s, se jistě skládá přesně z r+s kroků. Když chceme vybrat jednu konkrétní z takových cest, musíme zvolit, kterých r z uvažovaných r+s kroků povede směrem dolů. Každému možnému výběru odpovídá právě jedna cesta, a proto platí c(r,s) = r+s nad r.

Později si ukážeme, jak lze tuto hodnotu rychle spočítat. Dodefinujme ještě c(r, s) = 0, jestliže r < 0 nebo s < 0.

Inkluze a exkluze

Představte si nyní, že máme právě jednu překážku, a to na souřadnicích (r1,s1). Celkový počet cest vedoucích přes tuto překážku bude c(r1,s1)·c(R-r1, S-s1), jelikož máme c(r1,s1) způsobů, jak se dostat z (0,0) k překážce, a následně c(R-r1, S-s1) způsobů, jak pokračovat v cestě dále.

Počet všech cest, které přes tuto překážku nevedou, určíme tak, že od c(R,S) odečteme počet cest, které přes překážku vedou.

Následuje jedno důležité pozorování: Máme-li libovolný počet překážek, můžeme je uspořádat podle hodnoty ri+si. Jinými slovy, ve zbytku řešení můžeme předpokládat, že platí r1 + s1 ≤r2 + s2 ≤.... Potom každá cesta, která prochází překážkou číslo i, může předtím procházet jen přes překážky s čísly menšími než i. Proč tomu tak je? Jednoduše proto, že každým krokem se o 1 zvýší součet obou souřadnic místa, na němž právě stojíme. Každé políčko, přes které jsme dosud šli, má tedy menší součet souřadnic než to, kde právě jsme.

Vraťme se k řešení původní úlohy. Co kdyby byly překážky právě dvě: na (r1,s1) a na (r2,s2)? V souladu s uvedeným pozorováním předpokládáme, že r1 + s1 ≤r2 + s2.

Všech cest je c(R,S). Od nich odečteme cesty, které vedou přes první překážku, těch je c(r1,s1)·c(R-r1, S-s1). Následně odečteme také cesty, které vedou přes druhou překážku, těch je c(r2,s2)·c(R-r2, S-s2). Ještě ale nemáme správný výsledek. Cesty, které vedou postupně přes obě překážky, jsme totiž odečetli dvakrát. Abychom dostali správný výsledek, musíme zjistit, kolik existuje takových cest, a tento počet k aktuálnímu výsledku zase zpátky přičíst. To je ale snadné: cest, které postupně procházejí přes (r1,s1) a (r2,s2), je c(r1,s1)·c(r2-r1,s2-s1)·c(R-r2,S-s2). Díky tomu, jak jsme dodefinovali c pro záporné vstupy, tento vztah funguje i v případech, že takové cesty neexistují.

Uvedené úvahy pro jednu a dvě překážky můžeme zobecnit i pro více překážek, čímž dostaneme tzv. princip inkluze a exkluze.

Nechť p(X) je počet cest, které vedou přes každou překážku z množiny X (a možná i přes jiné překážky). Pro libovolnou množinu X dokážeme tento počet spočítat v čase úměrném |X|: stačí vynásobit počet cest z (0,0) k první překážce, počet cest od první překážky ke druhé, atd., až počet cest od poslední překážky na místo (R,S).

Abychom dostali správný výsledek úlohy, potřebujeme vzít všechny cesty. Od nich odečteme cesty vedoucí přes libovolnou jednu překážku, přičteme cesty vedoucí přes dvojice překážek, zase odečteme cesty přes trojice překážek, atd. Stručně to můžeme zapsat následovně: Hledaný počet cest je roven součtu všech hodnot (-1)|X| p(X), kde sčítáme přes všechna X⊆{1,2,..,K}.

Implementací tohoto vztahu dostáváme řešení, které dokáže libovolnou mřížku s K překážkami vyhodnotit v čase O(K·2K) – za předpokladu, že má k dispozici všechna potřebná kombinační čísla.

Vzorové řešení, první část

Označme z(i) počet způsobů, jak se lze dostat k překážce i tak, abychom nešli přes žádnou překážku s číslem menším než i.

Určitě platí z(1) = c(r1,s1) – cesta k první překážce jistě nemůže přecházet přes jiné překážky, proto každá možná cesta je dobrá.

Předpokládejme nyní, že už známe hodnoty z(1)z(k-1). Jak určit hodnotu z(k)? Všechny cesty vedoucí k překážce k můžeme rozdělit do následujících navzájem disjunktních množin:

  1. Cesty, které vedou přes překážku 1.
  2. Cesty, které nevedou přes překážku 1 a vedou přes překážku 2.
  3. Cesty, které nevedou přes překážky 1 ani 2 a vedou přes překážku 3.
  4. !!!Unknown: 'vdots'!!!
  5. Cesty, které nevedou přes žádnou z překážek 1 až k-1.

Všech cest k překážce k je celkem c(rk,sk). Všimněte si cest i-tého z výše uvedených typů (pro nějaké i<k). Kolik jich je? Máme z(i) způsobů, jak se lze dostat k i-té překážce, aniž bychom přešli přes některou z předcházejících, a c(rk-ri,sk-si) způsobů, jak se dostat odtamtud už libovolnou cestou ke k-té překážce. Proto platí:

z(k) = c(rk,sk) - ∑i<k z(i) ·c(rk-ri,sk-si).

Když už známe hodnoty z(i), analogickou úvahou bychom mohli spočítat počet cest, které neprocházejí žádnou překážkou. Při implementaci si pomůžeme jednoduchým trikem: přidáme překážku číslo K+1 na souřadnice (R,S). Potom jako z(K+1) dostaneme přesně počet hledaných cest.

Toto řešení zpracuje jednu mřížku v čase O(K2) – opět za předpokladu, že máme k dispozici všechna potřebná kombinační čísla.

(Před)počítání kombinačních čísel

Jednou možností je spočítat si všechna potřebná kombinační čísla pomocí vzorce a+1 nad b+1 = a nad b+a nad b+1 nebo jinak řečeno pomocí Pascalova trojúhelníka. Kombinační čísla se nemění, spočítáme je jednou na začátku výpočtu programu a následně je můžeme využívat během celého výpočtu.

Nejjednodušší je uložit si je do dvojrozměrného pole. Při paměťovém limitu 64 MB se nám vejde do paměti přibližně 16 milionů celých čísel, což odpovídá zhruba tabulce 4 000×4 000.

Šikovnější řešení je založeno na pozorování, že většinu kombinačních čísel nikdy nevyužijeme. Lepší tedy bude nejprve načíst celý vstup a zjistit, která kombinační čísla potřebovat budeme. Následně budeme kombinační čísla počítat pomocí výše uvedeného vztahu a vždy, když narazíme na takové, které potřebujeme, si jeho hodnotu zapamatujeme. Pomocí tohoto triku bylo možné získat alespoň 13 bodů.

Jinou možností (která navíc postačovala i na testovací vstup 14) je počítání hodnot a nad b pomocí jejich prvočíselného rozkladu: pro libovolné prvočíslo p snadno spočítáme, kolikrát dělí každé z čísel a!, b! a (a-b)!.

Dělení modulo M

Kombinační čísla můžeme počítat i přímo podle vzorce a nad b = a! !!!Unknown: 'over'!!! b!(a-b)!. Problém tohoto přístupu spočívá v dělení. Zatímco sčítat, odčítat a násobit modulo M je snadné, s dělením to není tak jasné. Dělení při operacích se zbytky obecně nemusí fungovat. Například čísla 12 a 22 dávají po dělení číslem 10 stejný zbytek, ale 12/2 = 6 a 22/2 = 11 už stejný zbytek nedávají. Pokud počítáme modulo 10, pak například číslo 7 vůbec nedokážeme vydělit dvěma – tedy neexistuje takové x, aby 2x dávalo stejný zbytek jako 7.

V naší situaci jsme na tom ale dobře, jelikož číslo M je prvočíslo. A v takovém případě umíme „dělit”? tzn. ke každému a a každému b (takovému, že 0<b<M) existuje právě jeden možný zbytek x takový, že bx ≡ a !!!Unknown: 'pmod'!!! M. Proč tomu tak je? Uvažujme hodnoty 0, b, 2b, .., (M-1)b. Žádné dvě z těchto hodnot nemohou po dělení M dávat stejný zbytek, neboť potom by M dělilo jejich rozdíl (j-i)b. To ale nemůže, jelikož oba činitelé jsou menší než M a zároveň M je prvočíslo. Speciálně tedy ke každému b existuje právě jedno x takové, že bx≡ 1 !!!Unknown: 'pmod'!!! M. Toto x budeme nazývat inverzním prvkem k b a budeme ho značit b-1.

Nyní snadno zjistíme, že platí: jestliže a/b je celé číslo, pak dává po dělení číslem M stejný zbytek jako a·b-1. Když tedy potřebujeme znát hodnotu a nad b modulo M, zjistíme ji jako ( a! ·(b!)-1 ·((a-b)!)-1 ).

Pokud si spočítáme pro každé n z rozsahu od 1 do 100 000 hodnoty n! a (n!)-1, dokážeme pak určit libovolné potřebné kombinační číslo v konstantním čase.

Inverzní prvky

Jakým způsobem najdeme inverzní prvek k danému číslu b? Můžeme použít například rozšířený Euklidův algoritmus, kde hledáme nějaké celočíselné řešení rovnice bx + My = 1. Jinou, jednodušší možností je použít malou Fermatovu větu. Ta říká, že když M je prvočíslo, potom pro libovolné b (0<b<M) platí bM-1≡ 1 !!!Unknown: 'pmod'!!! M. No a bM-1 můžeme přepsat jako b ·bM-2, odkud již vidíme, že inverzním prvkem k b je bM-2 mod M. Tuto hodnotu dokážeme spočítat šikovným umocňováním v čase O(logM).

Celé vzorové řešení

Začneme tím, že pro každé n spočítáme hodnotu n! mod M a pomocí malé Fermatovy věty k ní určíme inverzní prvek. Následně postupně zpracováváme mřížky ze vstupu s využitím postupu založeného na počítání čísel z(i). Toto řešení má časovou složitost O( (R+S)logM + NK2 ).

4.cc

P-III-5 Hurikán

Je zřejmé, že kiribatské ostrovy a aktuálně stojící mosty mezi nimi tvoří neorientovaný graf. Když spadne některý z mostů, z grafu zmizí příslušná hrana.

Mezi vrcholy, které tvoří jednu komponentu souvislosti grafu, existuje spojení po mostech. Potřebujeme zabezpečit dostatek převozníků na dopravu mezi různými komponentami. Má-li graf S komponent, nejmenší postačující počet převozníků je S-1 (budou například jezdit mezi první komponentou a všemi ostatními). Proto nám stačí zjistit pro každý den, z kolika komponent souvislosti se skládá graf.

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

Počet komponent grafu lze určit prohledáváním do hloubky nebo do šířky. Začneme v prvním vrcholu a postupně obarvujeme všechny vrcholy, do nichž se dá z něho dostat. Pokud zůstaly nějaké neobarvené vrcholy, některý z nich si vybereme a začneme z něho znovu prohledávat další komponentu. Tento postup opakujeme, dokud neobarvíme celý graf. Počet komponent je určen tím, kolikrát jsme museli začít prohledávat.

Na popsaném principu je založeno jednoduché řešení úlohy: postupně pro každý den odstraníme z grafu hranu odpovídající tomu mostu, který právě spadl, a prohledáváním zjistíme aktuální počet komponent souvislosti. To znamená, že potřebujeme (K+1)-krát prohledat celý graf. Časová složitost tohoto řešení je proto O(K·(M + N)).

Výpočet odzadu

Podívejme se nyní na úlohu od konce. Začneme s grafem, v němž chybí všech K mostů s porušenou statikou. Budeme postupovat od posledního dne k prvnímu a postupně přidávat mosty do grafu. Zatím je toto řešení stejně dobré jako to předcházející, jenom dostáváme výsledky v opačném pořadí.

Přidáním hrany do grafu se mohou dvě komponenty spojit do jedné (pokud tato hrana vedla mezi vrcholy z dvou různých komponent), nebo se rozdělení na komponenty vůbec nezmění (pokud hrana vedla mezi dvěma vrcholy téže komponenty). Pro získání rychlejšího řešení budeme proto potřebovat datovou strukturu, která nám umožní efektivně zjišťovat, zda jsou dva vrcholy ve stejné komponentě, a také spojovat dvojice komponent.

Union-Find

Na chvíli teď zapomeneme, že se jedná o graf, a budeme řešit obecnější úlohu. Komponentu nazveme množinou, její vrcholy budou prvky této množiny. Množinu prvků si budeme reprezentovat stromem. Zavěsíme ho za kořen, který označíme jako reprezentanta množiny. Z ostatních prvků množiny vede vždy jedna hrana směrem nahoru, do nadřízeného prvku. Nadřízený prvek je blíže ke kořeni nebo je to dokonce kořen stromu.

Když vyjdeme z libovolného prvku množiny a budeme procházet v hierarchii stále výše (vždy do nadřízeného prvku), musíme skončit v reprezentantovi množiny. To znamená, že dva prvky patří do stejné množiny právě tehdy, když uvedeným postupem z obou dojdeme do téhož reprezentanta.

Dvě množiny sloučíme do jedné tak, že reprezentanta jedné z nich zavěsíme pod reprezentanta druhé množiny (nastavíme mu ho jako nadřízeného).

Spojováním množin mohou vznikat dlouhé řetězce prvků. V takovém případě bude mít hledání reprezentantů až lineární časovou složitost vzhledem k velikosti množiny. Ukážeme si dvě úpravy, které nám přinesou zrychlení.

Při slučování dvou množin zavěsíme vždy strom s menší hloubkou pod hlubší strom. To zajistí, že vznikající stromy budou mít hloubku řádově logaritmickou vzhledem k počtu prvků. Další možností je zvolit si vždy náhodně, který strom zavěsíme pod který. Potom budou také v průměrném případě vznikat stromy s malou hloubkou.

Druhým trikem je komprese cesty. Po nalezení reprezentanta ho nastavíme všem prvkům, jimiž jsme cestou nahoru prošli, jako jejich přímého nadřízeného.

Pomocí pokročilejších matematických metod lze dokázat, že průměrná časová složitost hledání reprezentanta s využitím obou uvedených zrychlení bude O(α(n)), kde n je velikost množiny a α je inverzní Ackermannova funkce. Pro prakticky využitelná čísla nabývá její hodnota nejvýše 4, proto ji můžeme považovat za konstantu. Celková časová složitost tohoto algoritmu je proto O(N + Mα(N)), případně O(N + M + K α(N)), když nejprve všechny stabilní mosty zpracujeme jedním prohledáváním.

V programu uvedeném na konci tohoto řešení používáme místo spojování podle hloubek stromů spojování náhodné – snáze se implementuje a očekávaná časová složitost je stejná.

Existuje i jiný způsob, jak lze napsat řešení, které získá plný počet bodů. Stejně jako v předchozím řešení budeme mosty zpracovávat od konce a zjišťovat počet komponent souvislosti grafu. To budeme dělat jednoduše tak, že si ke každému vrcholu budeme pamatovat číslo jeho komponenty a ke každé komponentě seznam jejích vrcholů. Vždy, když přidáváme hranu, ověříme, zda jsou oba její konce ve stejné komponentě. Pokud ano, nic se neděje, pokud ne, „přebarvíme” celou menší komponentu – tzn. každému jejímu vrcholu změníme přiřazené číslo na číslo větší komponenty.

Všimněte si, že vždy, když nějaký vrchol přebarvíme, dostane se tím do komponenty alespoň dvojnásobné velikosti, než v jaké byl dosud. Proto každý vrchol přebarvíme nejvýše log2 N krát, takže toto řešení má časovou složitost O(M+NlogN).

5.cc