Táto úloha je pekný príklad problému, kde je kľúčové nájsť nejakú jednoduchú charakteristiku optimálneho riešenia a potom prehľadať výrazne menší priestor možností, ktoré podľa našej charakteristiky môžu byť optimálne.

V našom prípade bude pre skúsenejšieho riešiteľa pravdepodobne náročnejšia prvá časť, kde sa budeme snažiť vymyslieť peknú charakteristiku optimálneho riešenia, ktorá nám zredukuje priestor možností, ktoré musíme vyskúšať. Efektívne prehľadanie tohto priestoru sa bude potom dať vymyslieť s použitím pomerne štandardných techník.

Nestačí orientovať hrany?

Hovoríme, že hrana je orientovaná z $u$ do $v$, ak $p(u)

p(v)$, kde $p(x)$ udáva číslo vrcholu $x$ po našom prečíslovaní. Nie je ťažké si všimnúť, že orientácia hrán v strome jednoznačne určuje počet klesajúcich ciest v prečíslovanom strome. Teda ak dostávame z viacerých prečíslovaní rovnakú orientáciu všetkých hrán, stačí vyskúšať jedno z nich.

Tuto môžeme využiť to, že na vstupe dostávame stále strom. Nech v ňom orientujeme hrany akokoľvek, ostane vždy acyklický. Teda po orientovaní hrán dostávame orientovaný acyklický graf. Vieme, že takýto graf má stále aspoň jedno topologické usporiadanie. Ku každému možnému orientovaniu hrán vieme priradiť nejaké topologické usporiadanie takto orientovaného grafu a podľa neho prečíslovať vrcholy. Z toho už vyplýva, že ku každému orientovaniu hrán máme aspoň jedno korešpondujúce prečíslovanie a stačí nám prejsť všetky možné orientovania hrán.

Všetkých prečíslovaní vrcholov je $n!$ a možných orientácií hrán je $2^{n - 1}$. Spočítať počet klesajúcich ciest, teda počet ciest po orientovaní hrán vieme v $O(n^2)$. Takto sme z triviálneho brute forcu, ktorý má zložitosť $O(n^2 \cdot n!)$, dostali lepší brute force so zložitosťou $O(n^2 \cdot 2^n)$. Ďalej sa budeme zamýšľať iba nad verziou, kde orientujeme hrany, keďže sme ukázali, že odpoveď bude rovnaká.

Vnútorné cesty

Vnútornú cestu z vrcholu $c$ do vrcholu $b$ nazveme takú orientovanú cestu v orientovanom strome, že existujú orientované hrany z $a$ do $b$ a z $c$ do $d$. Dokážeme, že vnútorné cesty v optimálnom riešení byť nemôžu.

Pozrime sa, čo sa stane, ak otočíme hrany v celom podstrome $a$ a hranu $a \rightarrow b$. Nech:

• $A$ je počet ciest, ktoré končia v $a$ (vrátane cesty dĺžky $1$, ktorá obsahuje iba $a$)

• $B_{out}$ je počet ciest dĺžky $\geq 2$, ktoré začínajú v $b$

• $B_{in}$ je počet ciest dĺžky $\geq 2$, ktoré končia v $b$ a nejdú cez hranu $a \rightarrow b$

Môžeme si všimnúť, že veľa ciest, ktoré boli orientované pred touto úpravou budú orientované aj po tejto úprave (iba sa v nich každá hrana otočí). Jediné cesty, ktoré sa mohli zmeniť musia obsahovať hranu $a \rightarrow b$. Preto sa stačí pozrieť na to, ako sa zmenil ich počet.

Pred úpravou týchto ciest bolo $A \cdot B_{out}$ : Všetky cesty končiace v $a$ vieme predĺžiť do nejakého vrcholu, do ktorého sa dá dostať cez $b$.

Po úprave ich bude $A \cdot B_{in}$ : Všetky cesty, z ktorých sa dá dostať do $b$, okrem tých, ktoré vedú cez $a \rightarrow b$ (to vyjadruje $B_{in}$), vieme predĺžiť všetkými cestami, ktoré sa končili v $a$ pred otočením, lebo po otočení sa v $a$ začínajú.

Počet orientovaných ciest sa nám teda zmení o $\delta_1 = A(B_{in} - B_{out})$. Rovnako vieme vypočítať, čo sa stane, ak otočíme hranu $c \rightarrow d$ a podstromy vrcholu $d$ neobsahujúce vrchol $c$. Počet orientovaných ciest sa v tomto prípade zmení o $\delta_2 = D(C_{out} - C_{in})$.

Teraz je dôležité si všimnúť, že každú orientovanú cestu, ktorá končí v $c$, vieme predĺžiť tak, že bude končiť v $b$ (lebo existuje orientovaná cesta z $c$ do $b$). Z toho vyplýva, že $B_{in} \geq C_{in} + 1$. Podobne vieme dokázať, že $C_{out} \geq B_{out} + 1$. Ak sčítame tieto nerovnosti, dostaneme $(B_{in} - B_{out}) + (C_{out} - C_{in}) \geq 2$.

Teda $\max (B_{in} - B_{out}, (C_{out} - C_{in}) > 0$ a keďže $A > 0$, tak aj $\max (\delta_1, \delta_2)

0$. Teda po jednej z týchto úprav vieme zvýšiť počet orientovaných ciest. Týmto sme dokázali, že takzvaná vnútorná cesta nemôže v optimálnom riešení existovať, inak by sme vedeli získať lepšie riešenie.

Toto tvrdenie nám, ako ďalej uvidíme, veľmi pomôže. Výrazne a hlavne pre algoritmické riešenie veľmi príjemne nám zredukovalo priestor možností, ktoré nám naozaj treba vyskúšať. Ďalej si ukážeme, ako presnejšie musia vyzerať riešenia, ktoré budeme skúšať.

Centrálny vrchol

Centrálny vrchol nazveme taký vrchol orientovaného stromu, pre ktorý každá neorientovaná cesta končiaca v tomto vrchole je aj orientovaná cesta. Poriadne si premyslite, alebo nakreslite, ako môže orientovaný strom s centrálnym vrcholom vyzerať. Dokážeme, že takýto vrchol v orientáciách bez vnútorných ciest (len takéto orientácie majú šancu byť optimálne) musí existovať.

Najprv si zakoreníme strom v ľubovoľnom vrchole $v$. Zlý vrchol nazveme taký vrchol $u$, pre ktorý existuje cesta $(v, \dots, u, w)$, ktorá mení orientáciu po vrchole $u$. Teda hrany sú od $v$ po $u$ orientované jedným smerom a hrana $u,w$ je orientovaná opačným smerom.

Ak vrchol $v$ nemá žiadny zlý vrchol, môžeme ho vyhlásiť za centrálny vrchol, pretože k nemu existuje orientovaná cesta z každého vrcholu v strome. Inak musí platiť, že všetky zlé vrcholy sa nachádzajú v jednom podstrome vrcholu $v$. Dokážeme to sporom s tým, že v optimálnom orientovaní nie je vnútorná cesta. Nech je zlý vrchol aspoň v dvoch podstromoch vrcholu $v$. Prípady si môžeme rozdeliť podľa toho, ako vyzerajú hrany pri vrchole $v$ na ceste medzi podstromami so zlými vrcholmi:

• Ak sú tieto hrany orientované jedna smerom ku $v$ a druhá od $v$, podľa obrázka (a) vidíme, že dostaneme vnútornú cestu, ktorá začína v $u’$ a končí v $u$.

• Ak sú tieto hrany orientované obe smerom od $v$, podľa obrázka (b) vidíme, že dostaneme vnútornú cestu z $v$ do $u$.

• Ak sú tieto hrany orientované obe smerom ku $v$, obrázok by bol zhodný s obrázkom (b), len by mal otočené hrany. Dostali by sme teda vnútornú cestu z $u$ do $v$.

Teda máme spor s tým, že v optimálnom orientovaní nie je vnútorná cesta, keďže v každom prípade, kedy sú zlé vrcholy v aspoň dvoch podstromoch, dostaneme nejakú vnútornú cestu. Stačí teda zmeniť vrchol $v$ na koreň podstromu, v ktorom je zlý vrchol a aplikovať rovnakú argumentáciu. Takto môžeme postupovať po ceste v strome, pokým nie je aktuálny vrchol $v$ centrálny.

Dokázali sme tak, že v optimálnom orientovaní hrán musí byť nejaký centrálny vrchol. Toto nám už výrazne zjednodušilo úlohu a môžeme sa začať zamýšľať nad efektívnym nájdením optimálneho riešenia v zostávajúcom priestore orientovaní, ktoré môžu byť optimálne.

Prvé polynomiálne riešenie

Ako prvé sa črtá vyskúšať všetky vrcholy ako centrálne a pre každý nejak vypočítať, koľko najviac ciest vieme dostať, ak je tento vrchol centrálny. To sa po pár optimalizáciach ukáže aj ako vzorové riešenie.

Môžeme si všimnúť, že ak zvolíme vrchol za centrálny, ostáva už len rozhodnúť, ktoré podstromy budú orientované smerom ku centrálnemu vrcholu a ktoré smerom od neho. Hrany v celom podstrome musia byť orientované rovnako, lebo z každého vrcholu musí existovať orientovaná cesta k centrálnemu, alebo naopak. Tiež si môžeme všimnúť, že menenie orientácie celých podstromov zmení iba počet orientovaných ciest, ktoré vedú z jedného podstromu centrálneho vrcholu do iného podstromu centrálneho vrcholu. Počet ostatných orientovaných ciest ostáva nezmenený (iba sa celé otočia).

Poďme teda skúmať, koľko najviac orientovaných ciest vedúcich medzi dvoma rôznymi podstromami centrálneho vrcholu vieme dostať. Zaujíma nás, koľko ciest vieme viesť k centrálnemu vrcholu z každého z podstromov centrálneho vrcholu. To je celkom jednoduché - je to počet vrcholov v tomto podstrome.

Ak orientujeme smerom ku centrálnemu podstromy so spolu $x$ vrcholmi a smerom od všetky ostatné, dostaneme $x \cdot (n - 1 - x)$ ciest, ktoré vedú cez $2$ rôzne podstromy. Z každého vrcholu v podstrome orientovanom ku centrálnemu vrcholu sa vieme dostať do každého vrcholu v podstrome orientovaného od centrálneho vrcholu.

Ak tento výraz upravíme dostaneme $x\cdot(n - x - 1) = \frac{(n-1)^2}{4} - (x - \frac{n-1}{2})^2$ Prvý člen je nezávislý na $x$, teda stačí minimalizovať druhý člen. Ten zjavne minimalizujeme, ak zvolíme $x$ čo najbližšie k $\frac{n-1}{2}$.

Štandardná dynamika

Vidíme, že potrebujeme zistiť, či je možne rozdeliť množinu veľkostí podstromov centrálneho vrcholu na $2$ časti s rovnakým súčtom. Existuje pomerne známy algoritmus založený na dynamickom programovaní, ktorý tento problém vie riešiť v čase $O(n \cdot k)$, kde $k$ je súčet prvkov v celej množine. Viac sa o ňom dočítate tuto. Pre nás je ale $k = n - 1$, teda s jeho použitím dostaneme v najhoršom prípade časovú zložitosť $O(n^2)$ pre každý skúšaný centrálny vrchol. Ak sa takto rozdeliť množinu veľkostí podstromov nedá, chceme nejaké možné čo najrovnomernejšie rozdelenie. Dynamika, ktorú používame však vždy vypočíta aj odpoveď na túto otázku, pretože počas jej behu pre každú veľkosť rozdelenia zistí, či ju je možné dosiahnuť.

Dopočítame ostatné cesty

Ostáva už len zistiť, koľko ciest je celých obsiahnutých v každom z podstromov centrálneho vrcholu. To vieme vypočítať jednoduchým dynamickým programovaním prejdením všetkých podstromov centrálneho vrcholu. Pre každý vrchol $u$ si budeme pamätať, koľko ciest z jeho podstromu v ňom môže končiť, vrátane cesty obsahujúcej iba tento samotný vrchol. To je vlastne počet vrcholov v celom jeho podstrome vrátane $u$. Túto hodnotu nazveme $u_{in}$. Budeme si tiež pamätať, koľko ciest je v celom jeho podstrome. Túto hodnotu nazveme $u_{cnt}$. Ak vieme tieto údaje pre deti vrcholu $u$, tak ich vieme vypočítať aj pre vrchol $u$:

• $u_{cnt} = \sum_{c \in children(u)} (c_{cnt} + c_{in})$ (cesty v podstrome vrcholu $c$ sa zachovajú a pribudne $c_{in}$ ciest končiacich v $u$)

• $u_{in} = \sum_{c \in children(u)} c_{in}$ (do $u$ vieme predĺžiť z každého podstromu iba tie cesty, ktoré končia v $c$)

Ak je vrchol $u$ list, tak stačí nastaviť $u_{cnt} = 0$ a $u_{in} = 1$. Týmto spôsobom vieme s použitím DFS jednoducho vypočítať počet ciest v strome, ktoré sú obsiahnuté celé v jednom podstrome aktuálneho centrálneho vrchola $v$. Maximálny počet ciest tak získame, ako $y \cdot (n - 1 - y) + v_{cnt}$, kde $y$ je $x$, ktoré nám dalo najväčší počet ciest medzi podstromami.

Časová zložitosť

Ostáva ešte zistiť, akú časovú zložitosť toto celé vlastne bude mať. Pozrime sa, koľko práce vykonáme pre nejaký pevný centrálny vrchol $v$. Najprv chceme zistiť veľkosti jeho všetkých podstromov a počas toho môžeme aj vypočítať cesty, ktoré vedú celé v jednom podstrome. To sme si ukázali, že vieme jedným DFS, ktoré bude mať v našom prípade zložitosť $O(n)$.

Potom chceme vypočítať počet ciest vedúcich cez $2$ podstromy pri optimálnom orientovaní podstromov. To dokážeme pomocou vyššie popísanej dynamiky v čase $O(n^2)$. Ukážeme, že aj keď to tak na prvý pohľad nevyzerá, aj výsledná časová zložitosť bude $O(n^2)$.

Označme počet susedov vrchola $v$ ako $deg(v)$. Potom pri zisťovaní optimálnej orientácie máme vlastne zložitosť $O(n \cdot deg(v)$. Je síce pravda, že $deg(v)$ môže byť až $n - 1$, ale použijme radšej tento predpis pri celkovom odhade časovej zložitosti. Dostaneme tak $O(\sum_{v=1}^{v=n} (n \cdot deg(v)) = O(n \cdot \sum_{v=1}^{v=n} deg(v))$. Súčet stupňov v celom strome je ale stále $2n - 2$, teda $\sum_{v=1}^{v=n} (deg(v)) = 2n - 2$ a celková časová zložitosť je $O(n \cdot (2n - 2)) = O(n^2)$. Inak povedané, prechod poľa s možnými súčtami pri dynamike prechádzame v podstate pre každú hranu raz pre jej jeden koncový vrchol a raz pre druhý koncový vrchol. Hrán v strome a aj veľkosť poľa je $O(n)$, teda časová zložitosť je $O(n^2)$.

Vzorové riešenie

Iba centroidy nie sú

triviálne

Centroid je vrchol v strome, ktorého žiaden podstrom nemá veľkosť väčšiu ako $\frac{n}{2}$. Pre vrchol, ktorý nie je centroid stačí orientovať veľký podstrom jedným smerom a ostatné druhým smerom. Teda len pre centroidy je potrebné riešiť úlohu spomenutým dynamickým programovaním. Je známe, že centroidy sú v strome stále najviac dva, teda dynamiku zbehneme konštantne veľa krát.

To samo o sebe ale nezlepší časovú zložitosť, keďže centroid môže mať až $O(n)$ detí a v tom prípade bude mať celý algoritmus kvôli dynamike časovú zložitosť $O(n^2)$. Skúsme preto zefektívniť dynamiku na súčty podmnožín.

Triky z Ameriky

Teraz popíšeme možno nie až tak známy trik, pomocou ktorého je možné vyriešiť dynamiku na súčty podmnožín v čase $O(n \cdot \sqrt n)$, kde $n$ je najväčší dosiahnuteľný súčet. Najprv je dobré si uvedomiť, že rôznych hodnôt, ktoré sa sčítajú na $n$ musí byť najviac $O(\sqrt n)$. To si vieme zdôvodniť napríklad pomocou vzorcu na výpočet súčtu aritmetickej postupnosti. Aj ak budeme používať čísla od $1$ s diferenciou $1$, dostaneme po $2 \cdot \sqrt n = O(\sqrt n)$ číslach väčší súčet ako $n$. Všetky iné množiny rôznych čísel s aspoň $2 \cdot \sqrt n$ prvkami nám dajú zjavne väčší súčet ako je tento. Teda problém môžeme mať len vtedy, ak sa nejaké malé čísla často opakujú.

Povedzme, že máme $3$ trojky. Môžeme si všimnúť, že čo sa týka dosiahnuteľných súčtov sme v tej istej situácii, ako keď máme $1$ trojku a $1$ šestku. Toto platí všeobecne. Ak máme prvok $a$ $a_{cnt}$-krát, kde $a_{cnt} \geq 3$. Ekvivalentné by bolo mať $1 + (x - 1) mod 2$-krát prvok $a$ a $\lfloor (x - 1) / 2 \rfloor$-krát prvok $2a$. Touto úpravou zjavne nezmeníme súčet všetkých prvkov.

Ak v nejakom dosiahnuteľnom súčte použijeme $a$ párny počet krát, vieme to vyskladať iba z prvkov $2a$. Prípadne použijeme oba prvky $a$ ak bolo $a_{cnt}$ párne.

Ak v nejakom dosiahnuteľnom súčte použijeme $a$ nepárny počet krát, vieme to vyskladať z prvkov $2a$ a jedného prvku $a$. Keďže prvky $a$ po úprave najviac dva, nikdy sa nám nestane, že by sme nemali dosť prvkov $2a$ na vyskladanie daného súčtu.

Prišli sme teda na spôsob ako upraviť počty tak, aby sa množina možných súčtov nezmenila a zároveň sa prvok $a$ nachádzal v množine $1$ alebo $2$-krát. Ak túto úpravu spravíme so všetkými najmenšími $\sqrt n$ prvkami, nutne budeme mať $O(\sqrt n)$ prvkov. Prvkov väčších ako $\sqrt n$ môže byť najviac $\sqrt n$ a kvôli úpravám, ktoré sme spravili máme medzi menšími prvkami ako $\sqrt n$ najviac $2 \cdot \sqrt n$ prvkov.

Dokopy máme teda $\sqrt n + 2 \cdot \sqrt n = O(\sqrt n)$ prvkov. Týmto sme dostali algoritmus, ktorý spočíta všetky možné súčty v čase $O(n \cdot \sqrt n)$. Najprv spravíme úpravy na malých prvkoch a potom použijeme predchádzajúci algoritmus.

Už iba prekoreňovať

Aj keď teraz už časová zložitosť vyzerá nádejnejšie, stále je v skutočnosti $O(n^2)$. Pri počítaní ciest, ktoré sú celé v nejakom podstrome stále pre každý vrchol prejdeme celý strom. Ak by sme sa tohto zbavili, získali by sme už naozaj lepšiu časovú zložitosť.

Takáto situácia je už skúsenejšiemu riešiteľovi pomerne známa. Stačí použiť techniku prekoreňovania. Ak spravíme najprv DFS z vrcholu $1$ na vypočítanie $u_{in}$ a $u_{cnt}$ pre všetky vrcholy, získame potrebné hodnoty pre podstromy detí (podľa zakorenenia vo vrchole $1$) každého vrcholu. Chceme teda už len vypočítať hodnoty pre “nadstrom” nášho rodiča (podľa zakorenenia vo vrchole $1$). Presne toto vieme vďaka technike prekoreňovania. Stačí použiť jedno DFS na predpočítanie hodnôt pre každý podstrom podľa zakorenenia v $1$ a pri druhom DFS si už budeme vedieť správne udržiavať hodnoty pre náš nadstrom. Ak túto techniku nepoznáte, môžete sa o nej viac dočítať v USACO guide. Pre náš konkrétny prípad sa môžete pozrieť do implementácie.

Finálna časová a pamäťová

zložitosť

Už len stačí overiť, že je časová zložitosť naozaj taká, ako chceme. Najprv spravíme DFS na vypočítanie potrebných údajov o podstromoch v $O(n)$. Potom počas druhého DFS pre necentroidy vypočítame odpoveď v $O(1)$ a pre centroidy v čase $O(n \cdot \sqrt n)$. Centroidov je ale konštantne veľa, teda finálna časová zložitosť bude $O(n \cdot \sqrt n)$. Pamäťová zložitosť je $O(n)$, pretože si pamätáme iba strom a pole s možnými súčtami.

Bonusy

Prekoreňovanie na vyriešenie tohto problému dokonca ani nebolo treba. Dá sa dokázať, že optimálny centrálny vrchol bude vždy centroid a teda stačí strom zakoreniť v ňom (resp. v obidvoch z nich, ak sú $2$). Časovú zložitosť nám to však nezhoršuje, tak sme sa kvôli lenivosti dokazovať ďalšie veci rozhodli použiť prekoreňovanie :)).

Algoritmus sa dá zrýchliť použitím C++ bitsetov. Pri dynamike si uložíme boolovské pole ako bitset b. Pri pridávaní prvku x stačí spraviť b |= (b << x). Táto neasymptotická optimalizácia vie občas výrazne zrýchliť kód v praxi. Na získanie plného počtu bodov za program to ale nebolo treba.