6. Žeby závod? vzorové riešenie

4 5 10
2 1 3
4 2 4
7 1 3
9 0 2

9
5
3
3
6
10

Tip na úvod

Aby sme nemuseli špeciálne riešiť začiatok a koniec parkoviska, tak si vieme pridať 2 nabíjacie stanice na začiatok a koniec, ktoré zaberajú celú šírku parkoviska.

Bruteforce

Vytoríme si celé parkovisko ako 2D pole boolovských hodnôt, na začiatku núl, a pre každú nabíjačku zmeníme hodnoty v poli, na všetkých políčkach kam zasahuje z nuly na jednotku.

Na zistenie odpovede prejdeme každý riadok a počítame akú najväčšiu medzeru sme videli.

Časová zložitosť takéhoto riešenia je \(O(w(n+l))\), pretože musíme vytvoriť a prejsť pole veľkosti \(w\times l\), a pridať \(n\) nabíjacích staníc s maximálnou dĺžkou \(w\).

Pamäťová zložitosť je \(O(wl)\), pretože si musíme pamätať celé pole parkoviska.

Lepší bruteforce

Namiesto vytvárania celého parkoviska si vieme vždy jednoducho zistiť \(x\)-ové súradnice všetkých nabíjacích staníc, ktoré zasahujú do riadka ktorý aktuálne spracovávame.

To vieme spraviť tak, že si pre každý riadok prejdeme všetky nabíjačky, a zistíme, či cez ne kolobežka na tomto riadku prejde, potom tieto nabíjačky prejdeme v zoradenom poradí podľa \(x\), a nájdeme medzi ktorými dvomi je najväčšia medzera.

Časová zložitosť je \(O(nw \log n)\), pre každý riadok prejdeme všetky nabíjačky, a tie cez ktoré kolobežka na danom riadku prejde, zoradíme podľa \(x\). Všimnime si, že riešenie vieme spraviť aj tak, že si nabíjačky zoradíme podľa \(x\) na začiatku, a tak vieme dostať zložitosť \(O(nw + n \log n)\), respektíve \(O(nw + l)\), ak použijeme counting sort. \(^1\)

Pamäťová zložitosť je \(O(n)\), pretože si musíme pamätať všetky nabíjačky, respektíve \(O(n+l)\), ak chceme použiť counting sort.

Zaujímavá myšlienka

Pozrime sa, ako vyzerá \(i\)-ty riadok v porovnaní s \((i+1)\)-vým. Vidíme, že väčšinou vyzerajú celkom podobne a vačšina nabíjačiek zostáva na rovnakých miestach.

Vieme si všimnúť, že ak prechádzame všetky riadky postupne, tak sa nabíjačky dokopy zmenia iba \(2n\)-krát. Každá nabíjačka sa raz pridá medzi tie aktívne, teda tie, cez ktoré prejde kolobežka na aktuálnom riadku, a raz sa z nich odoberie. Tieto zmeny pre \(i\)-tu kolobežku nastanú na súradnichiach \(y_{0,i}\) a \(y_{1,i}\).

Otázkou zostáva, ako tieto zmeny rýchlo vykonávať, a následne rýchlo zisťovať veľkosť najväčšej medzery medzi aktívnymi nabíjačkami.

Optimálne riešenie

Použijeme metódu zametania roviny priamkou. \(^2\)

Najskôr si vytvoríme zoznam zmien - udalostí. Zmena nastáva na riadku, kde končí alebo začína nejaká nabíjačka. Tieto zmeny si utriedime primárne podľa riadku a sekundárne podľa toho, či sa jedná o začiatok alebo koniec nabíjačky.

Následne zametáme rovinu, teda prechádzame riadky, a držíme si množinu všetkých aktuálne aktívnych nabíjačiek, teda tých cez ktoré prejde kolobežka na aktuálnom riadku - \(A\).

Postupujeme následovne: - Na novom riadku prejdeme všetky zmeny, kde sa nám pridá nejaká nabíjačka, a pridáme ich do množiny \(A\). - Zistíme, aká je najväčšia medzera medzi 2 aktuálne aktívnymi nabíjačkami. - Vymažeme všetky nabíjačky, ktoré v tomto riadku končia z množiny \(A\).

Na uchovávanie si množiny \(A\) vieme použiť napríklad std::set v jazyku C++.

Poslednou otázkou zostáva, ako rýchlo sa dá zistiť aká je najväčšia medzera medzi 2 aktívnymi nabíjačkami. To urobíme tak, že si spravíme multimnožinu, teda množinu, ktorá podporuje opakovanie sa prvkov, všetkych veľkostí medzier medzi aktívnymi susediacimi nabíjačkami - \(S\). Na to vieme použiť napríklad std::multiset v C++.

Ako robiť zmeny v \(S\): - Pri pridaní nabíjačky medzi aktívne sa s medzerami stane to, že sa nejaká medzera, veľkosti \(a\), rozdelí na 2 menšie, veľkosti \(b,c\). Na to, aby sme vedeli ako vyzerala pôvodná medzera, a ako vyzerajú tie nové potrebujeme vedieť, kde sa nachádza najbližšia nabíjačka na ľavo a na pravo od tej, ktorú sme aktuálne pridali. To vieme spraviť pomocou metód prev/next od práve pridanej nabíjačky v množine \(A\).
Potom užiba stačí z \(S\) odstrániť \(a\) a pridať \(b,c\). Je treba dávať si pozor, aby sme pri odstraňovaní nevymazali všetky výskyty medzier veľkosti \(a\) z multimnožiny, ale iba jeden.

• Zistíme, aká je najväčšia medzera medzi 2 aktuálne aktívnymi nabíjačkami ako maximum multisetu, teda jeho posledný prvok, pretože multiset je Binárny Vyhľadávací Strom. \(^3\)
• Pri odobraní nabíjačky sa stane opačná situácia, a dve medzery sa spoja do jednej. Vieme postupovať analogicky ako pri pridávaní, a len vymazať \(b,c\) z \(S\) a pridať \(a\).

Časová zložitosť je \(O((n+w) \log n )\), máme \(n\) udalostí, ktoré musíme zoradiť \(O(n \log n)\), pri každej udalosti hľadáme/vyberáme/pridávame do množiny \(O(n \log n)\), a pre každý riadok musíme zistiť aktuálnu veľkosť najväčsej medzery z množiny \(S\) - \(O(w \log n)\), všimnime si, že taktiež vieme mať zložitosť \(O(n \log n + w)\), ak si po každej zmene uchováme aktuálnu najväčšiu dĺžku medzery, namiesto toho, aby sme ju pre každý riadok hľadali v \(S\).

Pamäťová zložitosť je \(O(n)\), pretože máme \(O(n)\) udalostí, a množiny veľkosti \(O(n)\).

Riešenie pre iné jazyky

Ak nemáme usporiadanú množinu v štandardnej knižnici, ako to je v C++, tak máme dve možnosti ako si ju implementovať.

• Spravíme si vyvažovaný binárny vyhľadávací strom, na ktorom imlementujeme operácie nasledovný a predchádzajúci prvok \(^4\)
• Implementujeme množinu pomocou dynamického intervalového stromu nad množinou možných hodnôt - v našom prípade čísla od \(0\) do \(l\). Zisťovanie nasledovného a predchádzajúceho prvku vieme urobiť pomocou chodenia po intervalovom strome.\(^5\)

Všimnime si že oboma spôsobmi vieme tak isto implementovať aj multimnožinu.