Pustíme sa rovno do riešenia tretej sady. Prvé dve nechávame ako úlohu čitateľovi.

Musíme sledovať veľa vecí

Zadanie má celkom veľa obmedzení a je ťažké sledovať, či všetky z nich naraz platia. My sa budeme snažiť zjednodušiť si úlohu.

Prvá vec čo si môžme zjednodušiť je, že plebejci sa v úlohe pohybujú v čase a priestore zároveň. My sa snažíme zabrániť tomu, aby v rovnakú noc boli na rovnakom mieste dva tímy. Môžme si preto celý časo-priestor interpretovať ako graf. Pre každú dvojicu $(i, j)$, kde $i$ je číslo mesta a $j$ je číslo dňa, budeme mať vrchol. Ak sme v zadaní mali hranu medzi mestami $u$ a $v$, tak v našom grafe budeme mať dve orientované hrany: z $(u, i)$ do $(v, i+1)$ a z $(v, i)$ do $(u, i+1)$. Takto zabezpečíme, že sa tím posunul z mesta $u$ do mesta $v$, alebo naopak, a trvalo mu to jeden deň.

Okrem toho pridáme hrany z (u, i) do (u, i+1). Takéto hrany znamenajú, že tím sa za deň nepohol.

Takto by vyzeral graf pre prvý ukážkový vstup zo zadania. Červenou sú označené začiatočné pozície plebejcov, zelenou koncové.

Nateraz budeme riešiť len vstupy, kde pohyb plebejcov môže trvať maximálne jeden deň, teda kde $k=1$. V tejto podúlohe nepotrebujeme riešiť podmienku, aby dva tímy neboli v noci na rovnakom mieste. Totiž na začiatku sú v rôznych mestách a ak sa nám po prvom dni podarí dostať nejaký tým na každé z koncových miest, znamená to, že ani po prvom dni nie sú dva tímy na rovnakom mieste.

Jediné čo musíme zistiť je, či vieme tímom priradiť cielové mestá tak, aby sa každý tým na svoje cielové miesto dostal za jeden deň. Inými slovami, tímu môžme priradiť také cielové mesto, že z jeho začiatočného mesta do neho vedie hrana.

Skúseným čitateľom môže napadnúť, že ide o známy problém párovana. My si však beztak ukážeme ako sa problém rieši.

Párujeme štarty a cieľe

Ukážeme si iteratívny postup, ktorý nájde maximálne párenie.

Predstavme si, že už sme niektorým začiatočným mestám priradili koncové mestá. To znamená, že sme vybrali niektoré hrany po ktorých tímy prejdu. Takéto mestá budeme volať spárované, a hrany ktoré spájajú jeden pár budeme volať hrany párenia.

Ak sú už všetky začiatočné mestá spárované s koncovými, nemusíme nič robiť. Inak skúsime pre jedeno ďalšie štartovacie mesto pár.

Budeme hľadať takzvané alternujúce cesty. Takáto cesta začína v nejakom nespárovanom štartovaciom meste $x_0$, a pokračuje do nejakého cieľového mesta $y_0$. Ak $y_0$ nie je spárované, skončíme. Inak z neho prejdeme po hrane párenia do jeho spárovaného štartovacieho mesta $x_1$. Z neho opäť proces opakujeme. Zastavíme sa ak už sme prehľadali celý graf, alebo sme skončili v cieľovom meste $y_q$, ktoré zatiaľ nie je spárované.

V druhom prípade vieme spraviť nasledovný trik. Všetky hrany po ktorých sme prešli odstránime z párenia a popárujeme $x_0$ s $y_0$, $x_1$ s $y_2$, $\dots$, $x_q$ s $y_q$. Všetky štartovacie mestá, ktoré mali predtým pár ho budú mať aj teraz. Nemusí to ale nutne byť ten istý pár. Navyše sme ešte priradili koncové mesto aj mestu $x_0$. Takto sme o 1 zvýšili počet miest ktoré sú spárované.

Na obrázku môžeme vidieť ukážku tohoto procesu. Červené hrany sú v párení na začiatku, modrou je znázornená alternujúca cesta a zelenou su znázornené nové hrany párenia po konci procesu.

Dá sa ukázať, že ak alternujúcu cestu nevieme nájsť, našli sme maximálny počet miest, ktoré môžu byť spárovane. Ak sme teda ešte nenašli pár pre všetky štartovacie mestá a už nevieme nájsť alternujúcu cestu, znamená to, že sa plebejci nevedia hýbať tak, aby po jednom dni bol v každom cieľovom meste tím. Dôkaz a dôkladnejší popis celého algoritmu môžete nájsť v kuchárke.

Máme teda algoritmus, ktorý rieši tretiu podúlohu. Začneme s prázdnym párením, teda pre žiaden štartovací vrchol nemáme priradený koncový, a postupne pomocou alternujúcich ciest vždy o jedna zväčšíme počet spárovaných vrcholov. Ak sa nam podarí spárovať všetky štartovacie vrcholy, vieme, že plebejci sa vedia za jeden deň dostať do cieľových miest, teda odpoveď je ANO. Na základe hrán ktoré sú aktuálne v párení, vieme zrekonštruovať pohyb jednotlivých tímov. Ak sa nám naopak nepodarí spárovať všetkých, vieme, že do niektorého cieľového mesta nepríde žiaden tím a teda odpoveď je NIE.

Keď hľadáme alternujúcu cestu, musíme ju postupne hľadať z každého zatiaľ nespárovaného vrchola. Počas toho však stačí spracovať každý vrchol len raz. Aj keď sa zmení vrchol v ktorom sme alternujúcu cestu začali, ak sa dostaneme v dvoch prípadoch do toho istého vrchola, z ktorého už nevieme alternujúcu cestu dokončiť v prvom prípade, nebudeme ju vedieť dokončiť ani v druhom prípade. Preto nájsť jednu alternujúcu cestu nám zaberie $O(n+m)$ času. Počet hrán párovania zvýšime vždy o jedna a ak je odpoveď ANO bude hrán v párovaní $p$, preto celková zložitosť nášho programu je $O(p(n+m))$.

Implementačný trik

Proces hľadania alternujúcej cesty je trochu komplikovaný. V prvom rade musíme prehľadávanie spúšťať z každého nespárovaného vrchola. Okrem toho sa musíme inak správať pokiaľ do vrchola vedie hrana z párenia a pokiaľ do neho hrana nevedie. My si celú logiku trošku zjednodušíme. Nezlepší nám to časovú zložitosť, ale pomôže nám to neskôr vyriešiť aj zvyšné sady.

Prvá vec čo spravíme je že pridáme jedno spoločné štartovasie mesto $S$. Toto mesto prepojíme so všetkými štartovacími mestami v dni $0$. Pred prvým dňom tímy akoby prejdu z tohoto štartovacieho mesta na svoje cieľové pozície.

Podobne to spravíme aj s koncovými mestami, spravíme si jedno spoločné koncové mesTo $T$¹, kam sa všetky tímy akoby odoberú keď sa dostanú do svojich cieľových destinácií.

Prvý vstup zadania by po takomto prerobení vyzeral nasledovne:

Náš cieľ je teraz vhodne určiť čo spravíme keď nájdeme alternujúcu cestu. Snažíme sa o to, aby hľadanie alternujúcej cesty znamenalo len nájdenie ľubovoľnej cesty zo $S$ do $T$.

Nachvíľu sa zamyslite, ako by sme to docielili.

Na začiatku ešte žiadne vrcholy nie sú spárované. Preto naozaj keď nájdeme nejakú cestu zo $S$ do $T$, bude to alternujúca cesta, zlepší párovanie z 0 na 1. Teraz však musíme opatrne rozhodnúť, čo v grafe zmeníme, aby aj v druhej iterácii bolo hľadanie alternujúcej cesty takéto jednoduché.

Každú hranu, ktorou sme v našej alternujúcej ceste prešli, z grafu odstránime. Namiesto toho do grafu pridáme hranu, ktorá ide opačným smerom. Tie hrany ktoré pôjdu opačným smerom, teda z vrcholov prvého dňa do vrcholov nultého budeme volať spätné. Uvedomme si, že spätné hrany sú práve hrany párenia.

Pozrime sa teraz, čo sa stane, ak sa dostaneme do nejakého koncového vrchola, ktorý už je spárovaný. Hrana, ktorá z neho viedla do $T$ už je otočená naopak. Všetky normálne hrany vedú do neho, keďže je to vrchol prvého dňa. Jediná hrana, po ktorej môžeme ísť ďalej je práve spätná hrana, ktorá z neho vedie. To presne zodpovedá tomu, že zo spárovanych koncových vrcholoch musíme chodiť po hranách párenia. Ak nájdeme nejakú alternujúcu cestu, ktorá využíva spätné hrany, tieto spätné hrany opäť otočíme, teda už budú viesť správnym smerom. To tiež zodpovedá tomu, že hrany už nie sú v párení a že ich môžeme zase neskôr do párenia pridať.

Pridávať a odstraňovať hrany za behu môže byť náročné a potrebovali by sme nejaké špeciálne dátové štruktúry. Namiesto toho môžeme mať vytvorené všetky normálne aj spätné hrany a len si pamätať pre každú či je zrovna aktívna. Ak nájdeme alternujúcu cestu, označíme hrany na nej za neaktívne a ich zodpovedajúce opačné hrany označíme za aktívne.

Ak sa nám v takomto grafe podarí nájsť $p$ alternujúcich ciest, znamená to, že každé začiatočné aj koncové mesto musí byť v párovaní a teda že odpoveď je ANO. Opäť budeme vedieť zrekonštruovať odpoveď podľa toho, ktoré hrany sú aktívne.

Toto riešenie má stále rovnakú časovú zložitosť, ale je trošku elegantnejšie.

Riešime viac dní

Hneď by nám malo napadnúť, že tento postup sa viac menej dá použiť aj ak majú plebejci na presun viac ako jeden deň. Len si dorobíme ďalšiu vrstvu a robíme to isté.

Pre tretí vstup by sme si vytvorili takýto graf.

Namiesto alternujúcich cestách budeme odteraz hovoriť o zlepšovacích. Zlepšovacia cesta začína vo vrchole $S$, končí vo vrchole $T$ a prechádza len po aktívnych hranách. Po nájdení zlepšujúcej cesty opäť otočíme všetky prejdené hrany. Môžme si všimnúť, že po tom ako nájdeme $i$-tu zlepšujúcu cestu a otočíme jej hrany, budú spätné hrany tvoriť $i$ spatných ciest. Každá z nich bude popisovať pohyb jedného z $i$ tímov.

Tento postup má však jeden problém. Ak sa nám podarí nájsť $p$ zlepšovacích ciest, tak síce bude nakonci každý tím v rôznom koncovom meste, ale môže sa stať, že počas cesty, sa v jednom meste stretnú dva tímy na noc.

Ukážku tohoto problému môžme vidieť na obrázku. Je to druhý vstup zo zadania, ktorý nemá riešenie, avšak náš proces nájde dve zlepšujúce cesty. Červenou a modrou sú zvýraznené hrany dvoch zlepšujúcich ciest, ktoré sme našli. Žiadna z nich nevyužila spätnú hranu.

Len to opravíme

Namiesto toho aby sme menili náš algoritmus, ktorý hľadá zlepšujúce cesty, zmeníme náš graf, tak aby nájdené zlepšujúce cesty viedli k platnému riešeniu.

Pre každé mesto a každý deň namiesto jedného vrcholu vytvoríme dva, spojené hranou. Tieto hrany budeme volať kontrolné. Keď kontrolnú hranu využije nejaká zlepšujúca cesta, podobne ako ostatné hrany, otočíme ju naopak. To môže symbolizovať, že tu nejaký tím prečká noc. Ak teraz hľadáme ďalšie zlepšujúce cesty, môžu po tejto kontrolnej hrane prejsť len spätným smerom, v tom prípade sa ale vrátia aj po spätnej hrane ktorá do tohoto mesta viedla. Zlepšujúca cesta tak zmení, že v danom meste v noci žiaden tím nebude a teda je opäť voľné.

Takto by vyzeral graf pre druhý vstup. Všimnime si, že v grafe teraz existuje len jedna zlepšujúca cesta.

Postup hľadania zlepšujúcich ciest naozaj zostáva stále rovnaký, jediné čo sa mení je to, ako zlepšujúce cesty interpretujeme.

Ak sa nám v takomto grafe podarí nájsť $p$ zlepšujúcich ciest, našli sme pre každý tím cestu, po ktorej sa má vydať aby dorazili všetky tímy do koncových miest a neboli počas toho žiadne dva cez noc na rovnakom mieste. Opäť ich budeme vedieť zrekonštruovať podľa toho ako sú hrany orientované.

Náš graf bude mať $O(nk)$ vrcholov a $O(mk)$ hrán. Celá zložitosť bude $O(p(n+m)k)$.

Toto je koniec vzoráku, ak sa však chcete dozvedieť niečo viac, môžete čítať dalej.

Načo sme to celé robili?

Pre skúseného čitateľa to môže byť sklamanie, pretože úloha sa dá riešiť oveľa rýchlejšie. Algoritmus, ktorý sme použili na hľadanie zlepšujúcich ciest sa volá Ford-Fulkersonov algoritmus a používa sa na hľadanie tokov v grafe. Toky sú tošku komplikovanejšia verzia toho čo sme robili. Zadanie tokového problému je nasledovné:

Máme orientovaný graf, kde jeden vrchol $S$ je neobmedzený zdroj a vrchol $T$ je neobmedzený požierač. Každá hrana má priradenú maximálnu kapacitu. Našou úlohou je priradiť hodnoty hranám tak, aby 1. Hodnota každej hrany bola najviac taká, ako jej kapacita 2. Pre každý vrchol okrem $S$ a $T$, súčet na hranách, ktoré do neho prichádzajú, je rovnaký ako súčet na hranách, ktoré z neho odchádzajú. - Zo $S$ môže odchádzať viac ako do neho vchádza a do $T$ môže vchádzať viac ako z neho vychádza 3. Rozdiel medzi súčtom hodnôt, ktoré zo $S$ vychádzaju oproti tým čo do neho vchádzajú, bol čo najväčší.

Na tento problém sa vieme pozerať akoby hrany boli vodovodné trubky a z vrcholu $S$ vytekalo čo najvačšie množstvo vody, tak aby to kapacita trubiek zvládla. Preto sa problém volá tok.

Naša úloha je vlastne verzia tokového problému, kde každá hrana má kapacitu $1$. Je veľa algoritmov, ktoré tento problém riešia oveľa rýchlejšie, ako sme ho vyriešili my. Pri riešení tokových problémov je teda dôležité vedieť správne navrhnúť graf, na ktorom budeme algoritmus spúšťať. Presne preto sme v poslednom odseku neupravovali náš algoritmus na hľadanie zlepšujúcich ciest, ale radšej trošku zmenili graf.

Na takto navrhnutom grafe môžeme spustiť ľubovoľný algoritmus na hľadanie toku, na plný počet stačil ten najjednoduchší. Ak však chcete, môžte si pozrieť nejake zložitejšie napríklad tu.

Medzi jednotlivými úrovňami vedú hrany vždy tak isto.