Zamyslime sa najskôr nad statickou verziou tejto úlohy: ak máme daných $n$ úsekov cesty $[ x_i,y_i]$, ako vyzerá ich prienik? Kedy je neprázdny?

Aby nejaký bod $x$ patril do prieniku všetkých intervalov, museli už všetky začať, teda musí platiť $x\geq\max_i x_i$. Tiež musí platiť, že žiaden interval ešte nesmel skončiť, teda $x\leq\min_j y_j$.

Z toho vidíme, že môžu nastať dva prípady: ak $\max_i x_i > \min_j y_j$, prienik je prázdny – niektorý interval skončí skôr ako niektorý iný začne. V opačnom prípade je prienik neprázdny a je ním zjavne práve uzavretý interval $[\max_i x_i, \min_j y_j]$.

Dĺžka intervalu ako funkcia

Ak si v našej úlohe zvolíme nejaký konkrétny okamih $t\geq 0$, vieme si vypočítať, ako v danom okamihu vyzerajú slepé intervaly: $i$-ty z nich bude $[\ell_i + tv_i, r_i + tv_i]$.

Nás zaujíma, akú najdlhšiu dĺžku (a pre aké $t$) bude mať tento interval. Uvažujme preto nasledujúcu funkciu: $f(t) = \min_j (r_j + tv_j) - \max_i (\ell_i + tv_i)$. Zjavne platí, že ak $f(t) < 0$, tak je v čase $t$ prienik prázdny, a inak $f(t)$ udáva jeho dĺžku. Našu úlohu teda vieme preformulovať tak, že hľadáme, pre ktoré $t\geq 0$ nadobúda funkcia $f$ svoje maximum.

Príklad funkcie f

Na prvom grafe nižšie vidíme, ako sa tri rôzne slepé intervaly pohybujú v čase. Na $x$-ovej osi je čas, na $y$-ovej vzdialenosť na ceste. Znázornené intervaly zodpovedajú poslednému príkladu v zadaní, až na to, že $\ell_2$ je o čosi väčšie, aby to lepšie vyzeralo.

Čiarkované čiary predstavujú začiatky jednotlivých intervalov. Nás vždy zaujíma posledný začiatok (hodnota $\max_i (\ell_i + tv_i)$), čiže najvyššie sa nachádzajúca čiarkovaná čiara.

Analogicky nás v každom čase zaujíma prvý koniec intervalu, čiže najnižšie sa nachádzajúca plná čiara. Ak sa tá nachádza nad všetkými čiarkovanými, intervaly majú v danom čase neprázdny prienik.

Na druhom grafe sme vyfarbili oblasť, ktorá zodpovedá neprázdnemu prieniku intervalov, a hrubou čiarou sme vyznačili optimálne riešenie našej úlohy.

Dôležitá vlastnosť funkcie f

V čase $t=0$ vidíme, že najvyššia čiarkovaná čiara zodpovedá intervalu 1, zatiaľ čo najnižšia plná čiara intervalu 0. No a keďže interval 0 sa hýbe rýchlosťou 30 a interval 1 len rýchlosťou 10, keď teraz pôjdeme v čase ďalej, bude dĺžka prieniku plynule rásť (rýchlosťou $30-10 = 20$ za jednotku času).

V čase $t=50/29$ sa spodnou plnou čiarou stane čiara zodpovedajúca intervalu 2. Ten sa hýbe len rýchlosťou 1. Od tohto okamihu ďalej teda bude čiarkovaná čiara plnú. Dĺžka prieniku sa teda bude meniť o $1-10 = -9$ za jednotku času.

V čase $t=9/2$ nastane ďalšia zmena: hornou čiarkovanou čiarou sa stane čiara zodpovedajúca intervalu 0. Od tejto chvíle sa dĺžka prieniku mení rýchlosťou $1-30 = -29$ za jednotku času, a čoskoro už prienik prestane existovať.

Na tomto príklade si môžeme všimnúť všeobecné pravidlo, ktoré bude vždy platiť: rýchlosť, ktorou rastie dĺžka prieniku, sa môže s rastúcim časom . Totiž vždy, keď nastane zmena najvrchnejšej čiarkovanej čiary, tá nová rastie rýchlejšie, a vždy, keď nastane zmena najspodnejšej plnej čiary, tá nová rastie od tej predchádzajúcej pomalšie.

Keďže na začiatku môže byť rýchlosť rastu kladná, znamená to, že samotná (presnejšie, hodnota funkcie $f$, ktorá nás zaujíma) vo všeobecnosti .

My teraz potrebujeme nájsť maximum takejto funkcie. Spravíme to binárnym vyhľadávaním.

Binárne vyhľadávanie

V ľubovoľnom čase $t$ si vieme v čase $O(n)$ nájsť aj najspodnejšiu plnú čiaru, aj najvrchnejšiu čiarkovanú, a u oboch sa pozrieť na to, ako rýchlo rastú. Rozdiel týchto dvoch hodnôt nám povie, či v danom bode funkcia $f$ ešte rastie, je práve konštantná, alebo už klesá.

Začneme tým, že sa pozrieme na čas $t=0$. Ak už v tomto okamihu $f$ nerastie, je $f(0)$ odpoveďou, ktorú hľadáme a môžeme skončiť.

Označme teraz $m$ najväčšie číslo na vstupe (či už ide o súradnicu alebo rýchlosť). Pripomíname, že pre testovacie dáta platilo $m\leq 10^6$. Potom tvrdíme, že po čase $m$ už nenastane žiadna zmena: od tohto času ďalej musí byť aj čiarkovaná aj plná čiara stále tá istá. Totiž ak iná bola od nej rýchlejšie/pomalšie rastúca, tak na začiatku mala táto pred ňou najviac $m$, a keďže sú všetky čísla celé, tá druhá čiara tento náskok dobiehala aspoň rýchlosťou 1 za jednotku času.

(Algebraicky, priesečník priamok $a+bt$ a $c+dt$, kde $c\not= d$, je v bode $t=(a-c)/(d-b)$, no a v základnom tvare má tento zlomok má čitateľ $\leq m$ a menovateľ $\geq 1$.)

Máme teraz dve pozorovania: v čase $t_{lo}=0$ funkcia $f$ ešte rastie, zatiaľ čo v čase $t_{hi}=m$ už určite nerastie. Od tohto okamihu ďalej môžeme použiť spomínané binárne vyhľadávanie: dokola opakujeme, že sa pozrieme do stredu intervalu, vyhodnotíme, či tam $f$ ešte rastie alebo už nerastie, a podľa toho posunieme buď $t_{lo}$ alebo $t_{hi}$.

Trocha technických detailov na záver

Pri praktickej implementácii si treba dať pozor na zaokrúhľovacie chyby. Hodnotu optimálneho $t$, a teda aj hodnotu $f(t)$, zistíme len približne. Zadanie síce sľubuje, že testovač je tolerantný, ale aj tak ostáva jeden okrajový prípad, na ktorý si treba dať pozor: ak je optimálna odpoveď presne $f(t)=0$, ale správne $t$ netrafíme presne, dostaneme ako $f(t)$ hodnotu, ktorá je tesne pod nulou. Ak vtedy prehlásime, že riešenie neexistuje, dáme nesprávnu odpoveď.

V jednom autorskom riešení sme pre istotu celý záver riešenia spravili exaktne: po dostatočnom počte iterácií binárneho vyhľadávania máme nájdené nejaké $t$. Okrem tohto $t$ si exaktne (ako zlomok dvoch veľkých čísel) dopočítame najbližšie menšie aj najbližšie väčšie $t$, v ktorom sa mení niektorá hraničná čiara, a v oboch časoch exaktne vyhodnotíme funkciu $f$. Takto máme istotu, že sme určite našli optimálne riešenie.

Na úspešné vyriešenie úlohy však stačilo aj použitie reálnych (floating-point) čísel a vhodné zaokrúhľovanie. Správny čas $t$, aj správna odpoveď je totiž vždy zlomok, ktorého menovateľ je najviac $m$. V našom prípade to teda znamená, že ak je maximum $f$ naozaj záporné, tak je vždy menšie alebo rovné $-10^{-6}$. A teda ak nám vychádza odpoveď výrazne bližšia nule, môžeme si byť rozumne istí, že správnou odpoveďou je samotná nula.