7. Keď už je to po ceste. . . (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

V Manhattane kedysi stáli dvojičky. Kolumbus objavil Ameriku, one thing led to another a dvojičky dnes už v Manhattane nestoja. Finančníci, ktorí v dvojičkách pracovali, sa rozpŕchli po celom Manhattane.

Nieje nad vzťah založený na peniazoch, a tak ešte dodnes neustále medzi sebou kadečo vybavujú – odcestujú na nové pracovisko ich známeho, prehrabnú sa v kufríku plnom papierov, podpíšu niečo čo nikto nikdy nečítal, a vrátia sa naspäť do práce. A keď sa vydarí, po ceste sa ešte zastavia u kamaráta, vypijú kávu, zaspomínajú na strašidelné časy kedy si aj úplne obyčajní ľudia vedeli dovoliť nový, priestorný byt, a pokračujú v pracovnej ceste. Svojim nadriadeným toto drobné zdržanie vysvetlia ako zápchu v poludňajšej New Yorkskej¹ premávke, a veselo si celú cestu pripíšu do firemného času.

Ale takéto výhovorky nefungujú vždy – ak by kvôli priateľskej návšteve finančník robil dajaké obkľuky, určite by mu na to nadriadení prišli². Takúto zastávku sa teda odhodlajú urobiť len vtedy, keď nezvýšia prejdenú vzdialenosť k ich ozajstnej destinácií.

FKS³ sa rozhodol vyčísliť, koľko takýchto návštev môže denne prebiehať. Vrámci znižovania nákladov však programátorské práce outsourceli na Slovenské stredné školy…

Úloha

Všetky budovy Manhattanu perfektne zapadajú do štvorčekovej mriežky.

Zadané sú súradnice budov v Manhattane, v ktorých pracujú finančníci.

Keďže sú v Manhattane, vzdialenosť medzi budovami je samozrejme Manhattanovská – budova so súradnicami $(x_1 , y_1)$ je od budovy so súradnicami $(x_2 , y_2)$ vzdialená $|x_1 - x_2| + |y_1 - y_2|$.

Finančník cestujúc z budovy A do budovy B sa môže po ceste zastaviť pri budove C práve vtedy, keď vzďialenosť budov A a B je rovná vzdialenosti budov A a C plus vzdialenosti budov C a B.

Vyhodnotťe, koľko rôznych pocestných návštev sa môže v Manhattane odohrať. Dve návštevy považujeme za rôzne ak sa líšia v štartovnej, cieľovej, alebo navštívenej budove.

Formát vstupu

V prvom riadku je číslo $n$ – počet finančníkov v Manhattane. Každý z nasledujúch $n$ riadkov obsahuje dve celé čísla $x_i\ y_i$ – súradnice budovy, v ktorej pracuje $i$-ty finančník. Súradnice budov sú navzájom rôzne.

Pre testovacie sady pritom platí nasledovné:

Sada	1	2	3	4
$1\leq n\leq$	$200$	$2\,000$	$200\,000$	$200\,000$
$0\leq x_i, y_i\leq$	$1\,000$	$1\,000$	$1\,000$	$1\,000\,000$

Formát výstupu

Vypíšte jediné číslo – počet rôznych návštev, ktoré medzi sebou dokážu finančníci urobiť.

Príklady

Input:

Output:

Návštevu v druhej budove si môžu dovoliť finančníci cestujúci z prvej do tretej budovy, a naopak.

Input:

Output:

Teraz môžu navyše prvú budovu navštíviť finančníci zo štvrtej budovy na ceste do druhej alebo tretej (a naopak), a druhú budovu na ceste do tretej (a naopak).

Kedy ste naposledy videli v slove ‘rksk’?↩︎
pomocou GPS trackingu firemných vozidiel↩︎
Finačný Korupčný Sektor↩︎

Ako vždy, hrubá sila

Chceme vediet počet usporiadaných trojíc bodov (A,B,C) pre ktoré platí, že súčet Manhattanovských vzdialeností medzi A,B a B,C je rovný Manhattanovskej vzdialenosti medzi A a C.

Tak ich poďme všetky vyskúšať - v troch vnorených cykloch prejdeme všetky body, overíme či rovnosť sedí, a ak áno, pripočítame odpoveď.

Počet rôznych trojíc bodov, ktoré vyskúšame, je $O(n^3)$. Nemusíme si pritom pamätať nič okrem samotných bodov a zopár pomocných premenných, máme teda pamäť $O(n)$.

Toto by nám malo stačiť na prvú sadu, kde $n \leq 200$.

Poznámka o súradniciach

Doleuvedené riešenia budú záležať od veľkosti súradníc. Pre zjednodušenie zložitostí si teda môžeme uvedomiť, že ozajstné súradnice nás až tak nezaujímajú, iba ich relatívne poradie. Môžeme si teda x-ové aj y-ové súradnice na vstupe osobitne prečíslovať od $0$ po $n-1$ v $O(nlogn)$, a ďaľšia práca záležiaca na súradniciach bodov už bude $O(n)$. Keď sú súradnice menšie ako $n$, ponecháme ich tak a použijeme notáciu $O(s)$.

Postavíme Manhattan

Kedy platí požadovaná rovnosť pre body (A,B,C)? Kedy je cesta od A do B a B do C rovnako dlhá, ako priama cesta z A do C? Optimálna cesta z A do B, kde BÚNV. A je naľavo hore od C, je nejaká postupnosť krokov dĺžky jedna dole a vpravo, pričom nikdy neprekročíme súradnice bodu C. Keďže táto postupnosť krokov je ľubovoľná (nezáleží v akom poradí tieto kroky spravíme, len aby bol správny počet krokov dole a správny počet vpravo), môžeme pritom navštíviť ľubovoľný bod B ktorý je v obdĺžniku s bodmi A a C ako rohmi.

Pre každú dvojicu bodov by sme teda chceli vedieť odpovedať na otázku: Koľko bodov leží v obdĺžniku určenom týmito dvoma bodmi?

Toto je presne tá otázka, na ktorú vie efektívne odpovedať 2D prefixový súčet, o ktorom si môžete prečítať v kuchárke.

Spravíme si teda mriežku núl, na súradnice bodov pripočítame jedna, a spravíme na nej 2D prefixový súčet.

Teraz jednoducho prejdeme všetky dvojice bodov, a pre každú k odpovedi pripočítame počet bodov v obdĺžniku medzi nimi, mínus dva (keďže v obdĺžniku sa nachádzajú aj naše rohové body). Keďže každý platný bod B s rohmi A a C patrí do trojice (A,B,C) aj (C,B,A), nakoniec náš výsledok ešte prenásobíme dvomi.

Naša mriežka musí mať riadok/stĺpec pre každú možnú súradnicu. Naša mriežka teda má veľkosť $O(n^2)$,

Keďže vytvárame mriežku veľkosti $n^2$, a prechádzame všetky dvojice bodov (pre ktoré spravíme $O(1)$ operáciu v 2D prefixej mriežke), naša časová zložitosť je $O(n^2).

Pamäťová je priamočiaro $O(n^2)$.

Opačná otázka

Limitujúci faktor v našom riešení je, že musíme vyskúšať všetky dvojice bodov (a spočítať koľko bodov je v obdĺžniku medzi nimi).

Vieme túto otázku otočiť naopak, a zistiť pre každý bod, koľko dvojíc bodov tvorí obdĺžnik, v ktorom leží?

Samozrejme že to bola básnická otázka, inak by nebola vo vzoráku, všakže?¹

Poďme sa nad ňou teda zamyslieť. Obdĺžnik ktorý obsahuje nejaký bod B musí mať jeden roh nad ním (alebo zarovno), a druhý roh pod ním (alebo zarovno). Nápodobne, musí mať jeden roh naľavo od neho (alebo zarovno), a druhý roh napravo (alebo zarovno).

Ak skúsime tieto štyri podmienky zlúčiť do dvoch bodov, získame len dve možnosti: buď je jeden roh naľavo hore a druhý napravo dole, alebo je jeden roh napravo hore a druhý naľavo dole. Všetky takéto dvojice bodov sú rohmi obdĺžnika, ktorý náš bod obsahuje.

Prejdime teda všetky body, a pre každý vynásobme počet bodov naľavo hore s bodmi napravo dole, a počet bodov napravo hore s bodmi naľavo dole, a tieto dve čísla sčítajme. Úspešne sme započítali všetky obdĺžniky, ktoré obsahujú náš bod! Nanešťastie, niektoré sme započítali viackrát. Sú to práve tie, v ktorých oba body majú jednu zo súradníc rovnakú ako náš bod. Napríklad bod ktorý je priamo nad našim zvoleným, sme započítali v obdĺžnikoch s druhým rohom naľavo dole aj napravo dole, pričom v oboch prípadoch sme pripočítali body ktoré sú priamo pod ním. Musíme ich teraz raz odpočítať. Od našeho výsledku teda ešte odpočítame počet bodov priamo nad našim bodom krát počet bodov priamo pod ním, a nápodobne s bodmi priamo naľavo a napravo.

Všetky tieto otázky sú na počty bodov v obdĺžnikoch, čiže ich hravo zodpovieme 2D prefixovými súčtami v konštantnom čase.

Stále vytvárame mriežku so všetkými súradnicami, čiže $O(s^2)$.

Každý bod teraz spracujeme len raz, pričom sa popýtame na konštantne veľa obdĺžnikov v našich 2D prefixoch, a teda aj časová zložitosť je rovnaká.

Vzorák

Keď však súradnice narastú, máme už problém aj s $O(s^2)$ aj s $O(n^2)$ mriežkou. 2D prefixy nám už nestačia.

Zamyslime sa teda trochu nad informáciou ktorú potrebujeme, aby sme pripočítali k odpovedi cesty prechádzajúce cez daný bod. Potrebujeme vedieť počet bodov presne nad ním a pod ním, počet bodov presne naľavo a napravo od neho, a počet bodov vľavo/vpravo a hore/dole od neho. Ak si teda túto informáciu nevieme získať pre všetky body naraz (postavením 2D prefixov), možno si ju vieme postupne prepočítavať od jedného bodu k druhému? Tento prístup nás v tomto prípade dovedie k riešeniu.

Poďme skúsiť prechádzať bodmi zhora-dole, zľava-doprava, a udržovať si všetku potrebnú informáciu pre bod, ktorý práve spracúvame. Na začiatku, pred spracovaním prvého bodu, sú akoby všetky bod pod nami. Vytvorme si teda pole dole, ktoré na súradnici $x$ bude udržovať počet bodov pod bodom, ktorý práve spracúvame, a s x-ovou súradnicou $x$. Pred tým ako začneme spracovávať si doň zapíšeme všetky body. Nápodobne si vytvorme pole hore, ktoré bude udržiavať počet bodov nad bodom ktorý práve spracúvame, ktoré je najprv plné núl.

Postupne ako budeme prechádzať bodmi zhora-dole, si ich budeme odpočítavať z poľa dole a pripočítavať do poľa hore. Toto nám dá skoro všetku informáciu čo potrebujeme - vieme spočítať počet bodov napr. naľavo dole od práve spracúvaného bodu $(x,y)$ ako súčet poľa dole od súradnice $0$ po $x$, a napr. napravo hore ako súčet poľa hore od $x$ po maximum zo vstupu. Počet bodov priamo nad/pod našim bodom je priamo hore[x], resp. dole[x].

Jediné čo nám ostáva je vyriešiť správanie bodov s rovnakou $y$ súradnicou. Jedna možnosť je napríklad spracovávať všetky body s rovnakou výškou naraz - pridať ich hore, spočítať požadované obdĺžniky, odpočítať počet bodov priamo vľavo a vpravo (keďže spracovávame všetky v jednom prechode, udržujeme si túto informáciu), a nakoniec ich všetky jednotne odpočítať z dole.

Aby sme si polepšili s časovou zložitosťou, naše polia dole a hore budú musieť vedieť sčítavať čísla v intervale, a meniť hodnoty na jednotlivých súradniciach, v lepšom čase ako $O(n)$ resp. $O(s)$. Použijeme teda nejakú vhodnú dátovú štruktúru, ako Intervalový strom alebo Fínsky strom.

Budeme si pamätať naše body a polia zhruba také veľké, akú máme najväčšiu súradnicu – ak použijeme kompresiu, je to $n$, čiže pamäťová zložitosť je $O(n)$.

Body musíme usporiadať, prípadne spraviť kompresiu súradníc, čo nám zaberie $O(n \log n)$. Následne všetky body prejdeme, a každý konštantne veľa krát pridáme/odpočítame z intervalového stromu, a zakaždým spravíme konštantne veľa súčtov na tomto strome. Všetky tieto operácie zaberú $O(\log n)$, čiže dokopy taktiež $O(n \log n)$.

aj to je básnická otázka↩︎

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.

Sada	1	2	3	4
\(1\leq n\leq\)	\(200\)	\(2\,000\)	\(200\,000\)	\(200\,000\)
\(0\leq x_i, y_i\leq\)	\(1\,000\)	\(1\,000\)	\(1\,000\)	\(1\,000\,000\)

7. Keď už je to po ceste. . . vzorové riešenie