Zoznam úloh

8. Ešte treba kúpiť internet

Zadanie

V Absurdistane to s internetom nie je med lízať. Bežný internet je tam v takej kvalite, že kým načítaš stránku so správami, sú už neaktuálne. Aby to vláda zlepšila, rozhodla sa podporiť výstavbu optických liniek. Keďže s peniazmi hospodári zodpovedne, dotačný úrad má jedno posvätné pravidlo: podporiť sa smie iba linka medzi dvoma miestami, ktoré ešte spojené nie sú. Vďaka tomu medzi každými dvoma miestami v krajine vedie po optike práve jedna možná trasa – ani o linku viac, aby náhodou nevznikla nejaká podozrivo užitočná rezerva.

Ty zhodou okolností pracuješ v internetovej firme, ktorá musí pravidelne prenášať obrovské kvantá dát medzi svojimi dátovými centrami po celej krajine. Bežná sieť je pomalá, a preto chceš používať iba optiku. Lenže vzhľadom na veľký dopyt a preťaženú sieť nie je ľahké dostať sa k používaniu týchto liniek. Každú optickú linku prevádzkuje iný súkromný operátor a ponúka dve možnosti:

  • Prenájom. Zaplatíš $R$ peňazí a linku môžeš neobmedzene používať počas jednej jednotky času.
  • Odkúpenie. Zaplatíš $B$ peňazí a linku môžeš používať, kedykoľvek potrebuješ.

V diári máš rozpísané, kedy medzi ktorými dátovými centrami musia tiecť dáta. Každá požiadavka znie rovnako: „od času $l$ po čas $r$ (vrátane) musí byť možné preniesť dáta z miesta $a$ do miesta $b$.“ To znamená, že po všetkých linkách na trase z $a$ do $b$ musíš v každom okamihu z tohto intervalu smieť preniesť dáta, teda tie linky musíš mať vtedy buď prenajaté, alebo odkúpené.

Požiadavky ignorovať nemôžeš, pretože zákazníci sa na teba spoliehajú a peniazmi plytvať nechceš, lebo potom nezostane na odmeny pre teba (a tvojich kolegov). Zisti, koľko najmenej peňazí musíš dokopy zaplatiť za prenájom/odkúpenie kapacity na optických linkách.

Úloha

Máme strom s $n$ vrcholmi (miesta) a $n-1$ hranami (optické linky). Pri $i$-tej linke vieme buď zaplatiť $B_i$ a používať ju po celý čas, alebo za každú jednotku času, počas ktorej ju chceme používať, zaplatiť $R_i$.

Ďalej máme $m$ požiadaviek. $i$-ta požiadavka hovorí, že v každom okamihu času od $l_i$ po $r_i$ vrátane musia byť použiteľné všetky linky na (jedinej) trase medzi vrcholmi $a_i$ a $b_i$.

Nájdi najmenšiu možnú celkovú cenu, ktorou sa dajú splniť všetky požiadavky.

Formát vstupu

V prvom riadku vstupu sú dve celé čísla $n$ a $m$ ($2 \leq n$, $1 \leq m$) – počet miest a počet požiadaviek.

Nasleduje $n-1$ riadkov popisujúcich linky. V $i$-tom z nich sú štyri celé čísla $u_i$, $v_i$, $B_i$, $R_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq B_i, R_i \leq 10^9$) – linka spája miesta $u_i$ a $v_i$, jej odkúpenie stojí $B_i$ peňazí a prenájom na jednu jednotku času stojí $R_i$ peňazí. Linky tvoria strom, teda medzi ľubovoľnými dvoma miestami vedie práve jedna trasa.

Nasleduje $m$ riadkov popisujúcich požiadavky. V $i$-tom z nich sú štyri celé čísla $a_i$, $b_i$, $l_i$, $r_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$, $1 \leq l_i \leq r_i$).

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4 5 6 7 8
$n, m \leq$ $10$ $300$ $2\,000$ $2\,000$ $4\cdot10^4$ $4\cdot10^4$ $4\cdot10^4$ $4\cdot10^4$
$1 \leq l_i \leq r_i \leq$ $10$ $300$ $1\,000$ $10^9$ $10^9$ $10^9$ $10^9$ $10^9$
sieť sa nerozvetvuje nie nie nie nie áno áno nie nie

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo – najmenší počet peňazí, ktorý musíš dokopy zaplatiť.

Upozornenie: Výsledok sa nemusí zmestiť do 32-bitovej premennej.

Príklady

Vstup

3 1
1 2 7 2
2 3 9 4
1 2 3 5

Výstup

6

Požiadavka potrebuje iba linku medzi miestami $1$ a $2$, a to počas troch jednotiek času. Prenájom vyjde na $3 \cdot 2 = 6$ peňazí, čo je menej ako odkúpenie za $7$. Linku medzi $2$ a $3$ nepotrebujeme, takže za ňu nezaplatíme nič.

Vstup

4 3
1 2 12 2
2 3 6 3
2 4 100 1
1 3 1 5
3 4 4 6
1 4 2 3

Výstup

21

Linku $1-2$ potrebujeme v časoch $1$ až $5$ (prvá požiadavka) a $2$ až $3$ (tretia požiadavka), dokopy teda päť jednotiek času, čo nás pri prenájme vyjde na $5 \cdot 2 = 10$ peňazí. Linku $2-3$ potrebujeme šesť jednotiek času, prenájom by stál $18$, takže ju radšej odkúpime za $6$. Linku $2-4$ potrebujeme v časoch $2$ až $6$, čiže tiež päť jednotiek času, a prenajmeme ju za $5$ peňazí. Dokopy $10 + 6 + 5 = 21$.

Všimni si, že tretia požiadavka nás v skutočnosti nestála nič navyše – obe linky na jej trase sme aj tak už museli mať.

Dostali sme strom s $n$ miestami a $n-1$ optickými linkami. Každú linku vieme buď raz odkúpiť za $B$ peňazí, alebo prenajať za $R$ peňazí za každú jednotku času, počas ktorej ju používame. Ďalej máme $m$ požiadaviek tvaru „od času $l$ po čas $r$ musí byť použiteľná celá trasa medzi miestami $a$ a $b$“. Chceme minúť čo najmenej.

Kľúčovým pozorovaním je, že o tom, či kúpime alebo prenajmeme každú linku, sa môžeme rozhodnúť nezávisle. Tým pádom celková cena je proste súčet cez všetky linky:

$$\text{cena} = \sum_{\text{linka } e} \min\left(B_e,\; R_e \cdot T_e\right)$$

kde $T_e$ je počet jednotiek času, v ktorých linku $e$ potrebuje aspoň jedna požiadavka. Pre každú linku sa teda nezávisle rozhodneme pre lacnejšiu z dvoch možností: buď ju raz odkúpime za $B_e$, alebo ju prenajímame za $R_e \cdot T_e$.

Zostáva zistiť $T_e$. Linka $e$ je potrebná v tých časoch, ktoré pokrýva aspoň jedna požiadavka vedúca cez $e$. $T_e$ je teda veľkosť zjednotenia intervalov $[l_i, r_i]$ tých požiadaviek, ktorých trasa prechádza cez $e$.

Celá úloha sa tým rozpadá na dve nezávislé otázky:

  • ktoré požiadavky vedú cez danú linku a
  • ako rýchlo vieme spočítať veľkosť zjednotenia ich intervalov.

Jednotlivé sady odmeňujú postupné odpovede na tieto otázky.

Riešenie hrubou silou

Strom si zakoreníme (napr. v mieste $1$). Linky potom budeme indexovať pomocou spodnejšieho z vrcholov, ktoré spájajú - teda ak hrana spája vrcholy $v$ $a$ u, kde $v$ je otcom $u$, linka bude mať index $u$.

Pre každú požiadavku prejdeme trasu $a \to b$: hlbší z koncov vždy posunieme k jeho otcovi, až kým sa oba nestretnú v ich najnižšom spoločnom predkovi. Každej linke na trase pripíšeme interval $[l, r]$.

Označme $t_{\max}$ najväčší možný čas (horná hranica $r$). Keď sú časy malé (sady 1–3, $r \leq t_{\max} \leq 1000$), vieme pre každú linku držať pole cez čas a priamo si odškrtávať obsadené jednotky času; $T_e$ je potom počet odškrtnutých. Aby sme každý interval neoznačovali po jednotkách, použijeme diferenčné pole: pri intervale $[l,r]$ pripočítame $+1$ na pozíciu $l$ a $-1$ na pozíciu $r+1$. Nakoniec pole každej linky raz prejdeme, spravíme prefixové súčty a spočítame pozície s kladnou hodnotou — to je $T_e$. Rozdávanie $\pm 1$ stojí $O(n \cdot m)$ (každá z $m$ požiadaviek prejde až $n$ liniek) a záverečné prechody polí $O(n \cdot t_{\max})$, dokopy $O(n \cdot m + n \cdot t_{\max})$.

Veľké časy: zlievanie intervalov

Keď je rozsah času veľký ($t_{\max} \leq 10^9$, sada 4), políčka v poli cez čas si dovoliť nemôžeme. Namiesto odškrtávania si pre každú linku len nazbierame zoznam intervalov tých požiadaviek, čo cez ňu vedú. Na konci intervaly každej linky utriedime podľa začiatku a zametaním zlejeme prekrývajúce sa a nadväzujúce kusy do blokov. Potom súčet dĺžok blokov je $T_e$.

Zametanie robíme jednoducho. Prechádzame utriedené intervaly podľa začiatku a pamätáme si, ktorý najbližší čas nie je pokrytý. Ak interval, ktorým prechádzame, začína až po najbližšom nepokrytom čase, tak si vyhodnotíme celý predchádzajúci zjednotený blok. Inak iba predĺžime predchádzajúci zjednotený blok.

Prechod každej trasy je $O(n)$ (keďže môže prechádzať až cez $n$ vrcholov), takže na prejdenie všetkých trás použijeme spolu $O(n \cdot m)$, plus $O(m \log m)$ na triedenie. Pri $n, m \leq 2000$ (sada 4) to bez problémov stačí a riešenie zvláda ľubovoľne veľké časy. Na veľkej sieti (sady 5–8) však $O(n \cdot m)$ nestačí – na reťazi dĺžky $4\cdot10^4$ je jediná trasa dlhá až $O(n)$ a dokopy to je priveľa.

Veľká sieť

Na plný počet musíme obe čiastkové úlohy vedieť vyriešiť rýchlo.

Dĺžka zjednotenia.

Potrebujeme štruktúru, ktorá udržiava meniacu sa množinu intervalov a vie vrátiť dĺžku ich zjednotenia. Na to vieme použiť intervaláč. Časy najprv skomprimujeme (rôznych hraníc $l$ a $r+1$ je iba $O(m)$) a nad elementárnymi (skomprimovanými) intervalmi medzi nimi postavíme intervalový strom. V každom vrchole držíme, koľkokrát je jeho rozsah celý pokrytý (cely_pokryty), a akú dĺžku v jeho rozsahu pokrýva aspoň jeden interval (pokryty_rozsah).

Dĺžku pokrytú aspoň jedným intervalom udržiavame bez posúvania lazy nadol. Pri update-e zostúpime do uzlov, ktoré upravovaný rozsah pokrýva celé, a v nich zmeníme cely_pokryty o $\pm1$. Pri vracaní z rekurzie (teda už sme v oboch deťoch updatli cely_pokryty) prepočítame pokryty_rozsah uzla z jeho detí: ak má tento uzol cely_pokryty $> 0$, je pokrytá celá jeho dĺžka; inak je pokryty_rozsah súčet hodnôt detí (v liste nula).

Pridanie či odobranie intervalu je range update na intervale o $\pm 1$ v $O(\log m)$; dĺžku zjednotenia prečítame v koreni v $O(1)$.

Ktoré požiadavky vedú cez linku.

Linku $(v, \text{otec})$ používa požiadavka práve vtedy, keď v podstrome vrchola $v$ leží práve jeden z jej dvoch koncov. Chceme teda zistiť, koľko liniek a v akých časových intervaloch bude prechádzať cez vrchol $v$ do jeho otca. Toto zistíme z intervaláča, ktorý sme si vyššie vysvetlili. Pre daný vrchol si však tento intervaláč potrebujeme vytvoriť, a robíme nasledovne: Keď spracovávame nejaký podstrom, tak najprv rekurzívne spracujeme jeho deti (skonštruujeme si ich intervaláč). Potom množiny „aktívnych“ požiadaviek pre jednotlivé linky zlievame technikou small-to-large: Z dieťaťa s najväčším podstromom si zoberieme celý intervaláč. Pre ostatné deti si zoberieme zoznam ich “aktívnych” požiadaviek a pridáme ich do tohto intervaláča alebo ich z neho uberieme, ak tam už sú (ak tam už sú, vieme, že táto cesta už vyššie do stromu nepôjde).

Prečo je to efektívne? Predstavme si ľubovoľnú požiadavku. Keď ju pridávame do intervaláča, podstrom, do ktorého ju dvíhame, má aspoň dvakrát toľko vrcholov ako ten, z ktorého prišla. (Inak by totiž bola vo väčšom z nich — a ten sme si ako ťažké dieťa zobrali „zadarmo”, takže by sme ju nepresúvali.) Počet vrcholov v jej podstrome sa takto môže zdvojnásobiť najviac $\log_2 n$-krát, čiže každú požiadavku presunieme najviac $\log_2 n$-krát. Spolu je to $O(m \log n)$ prepnutí, každé za $O(\log m)$ v intervaláči — celková časová zložitosť je teda $O((n+m) \log n \log m)$.

Vďaka tejto technike intervaláč pri spracovaní vrcholu $v$ obsahuje presne tie požiadavky, čo majú v jeho podstrome jediný koniec – čiže tie, ktoré používajú linku k otcovi. Prečítame dĺžku zjednotenia z koreňa a pripočítame $\min(B_v, R_v \cdot T_v)$.

Dynamický intervalač namiesto kompresie.

Zjednotenie sa dá počítať aj bez kompresie súradníc — dynamickým intervaláčom nad celým časom $[0, 2^{30})$, ktorý alokuje vrcholy až keď treba. Je to elegantné, ale každá operácia prejde $30$ úrovní namiesto $\log m \approx 17$ pri kompresii, takže je asi 2-krát pomalší. Hĺbku by sa dalo zraziť ešte nižšie kompresiou ciest (skracovaním jednodetných reťazí v intervaláči), lenže kvôli horším konštantám (strom je roztrúsený po pamäti, takže cache nefunguje efektívne) je to v praxi výrazne pomalšie ako súradnicová kompresia.

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty