3. Slimačie spojenie vzorové riešenie

5
1 4 2 5 3
7 10 5 8 9

1 2

6
2 4 10 17 99 123
1 7 17 17 101 112 

-1

4
2 7 2 7
3 4 4 3

2 2

Skúšame všetky možnosti

Základné riešenie na všetky úlohy je skúsiť všetky možnosti. Ako to funguje tu?

Máme \(n^2\) dvojíc ktoré by si Krtko s Hodoboxom mohli vymeniť. Stačí pre každú spočítať aký je rozdiel medzi výslednými súčtami časov.

Spočítať súčty síce trvá \(O(n)\), môžeme si však pomôcť nasledovným trikom:

Predstavme si, že Krtko si zoberie Hodoboxovu úlohu číslo \(i\), a Hodobox si zoberie Krtkovu úlohu číslo \(j\). Potom rozdiel medzi ich časmi bude

\[ |k_1 + \dots k_{j-1} + k_{j+1} + \dots + k_n + h_i - (h_1 + \dots h_{i-1} + h_{i+1} + \dots + h_n + k_j)| = |\sum_{l_1}^{n} k_l + h_i - k_j - \left( \sum_{l=1}^n h_i - h_i + k_j \right)| \]

Takže nám stačí spočítať sumu všetkých originálne Krtkových úloch, \(K\), všetkých originálne Hodoboxových úloh \(H\) raz na začiatku. Následne, rozdiel po vymenení \(h_i\) a \(k_j\), dostanú rozdiel \(|K - H + 2h_i - 2k_j|\).

Takto vieme v konštatnom čase spočítať rozdiely pre všetky možné dvojice vymenení, a teda v časovej zložitosti \(O(n^2)\) vyriešiť úlohu. Toto riešenie mohlo získať \(4\) body.

S ktorou úlohou je najlepšie meniť \(k_i\)?

Pre jednoduchosť predpokladajme, že náročnosti sú zoradené podľa minutáže, teda \(h_1 \leq h_2 \leq \dots \leq h_n\) a \(k_1 \leq k_2 \leq\dots\leq k_n\).

Na ceste ku vzorovému riešeniu si pomôžme nasledovnou modifikáciou úlohy.

Predstavme si, že Krtko sa rozhodol, že sa mu úloha \(k_i\) nepáči a teda ju bude musieť pripraviť Hodobox. Ktorú úlohu by mu mal poslať Hodobox, aby bol rozdiel časov pripravovania čo najmenší?

Predstavme si najskôr, že Hodoboxove úlohy sú utriedené od najkratšej po najdlhšiu.

Tiež si predstavme, že \(k_i\) je najdlhšie trvajúca Krtkova úloha.

Bez ujmy na všeobecnosti, rátajme s tým, že Krtko má na začiatku viac práce ako Hodobox, a chce si vymeniť úlohu \(k_n\).

Krtko by mohol (trochu neintuitívne) začať skúšať od Hodoboxovej najviac času konzumujúcej úlohy, a postupne porovnávať \(|K - H + 2h_i - 2k_n|\), ako v riešení s hrubou silou.

Avšak, všimnime si, že keď sa stane, že výsledný rozdiel časov klesne, teda \(|K - H + 2h_i - 2k_n| < |K - H + 2h_{i-1} - 2k_n|\), potom sme už “prestrelili” a Hodobox bude mať oveľa viac práce ako Krtko, a zameniť za kratšiu úlohu čas môže len zhoršiť.

Takže v prípade, že nám rozdiel klesne, Krtko vie, s ktorou úlohou má meniť. Povedzme, že je to úloha číslo \(i\).

Pozorný čitateľ si teraz myslí - počkať, veď toto je stále lineárne, v ničom to nepomohlo!

Avšak, teraz nastane trik: predstavme si že Krtko sa zrazu rozhodne, že si úlohu \(k_n\) chce nechať, a miesto toho chce dať Hodoboxovi \(k_{n-1}\), druhú najdlhšiu úlohu.

Všimnime si, že meniť \(k_{n-1}\) s úlohou dlhšie trvajúcou než \(h_i\) sa nemôže oplatiť. Takže jediné, čo sa môže zlepšiť rozdiel oproti \(|K - H + 2h_i - 2k_{n-1}|\) je skúšať výmenu s kratšími Hodoboxovými úlohami.

Znova, ak raz nastane že výmena s kratšou úlohou by zhoršila balans, už sa ďalej skúšať neoplatí, a teda sme našli s ktorou úlohou má Krtko meniť \(k_{n-1}\).

Čitateľ, sledujúci časovú zložitosť, si môže všimnúť, že sme neporovnali oba z \(k_n\), \(k_{n-1}\) s každou Hodoboxovou úlohou - dokopy sme ich porovnali s najviac \(n+1\) úlohami.

Čo tak ďalej pokračovať s \(k_{n-2}, \dots, k_2, k_1\)? Ak vždy začneme porovnávať len s predchádzajúceho maxima, tak určite dokopy nájdeme optimálne riešenie pre každé \(k_j\), a zároveň prejdeme Hodoboxove pole presne raz.

Ako získame odpoveď na originálnu otázku? Ak pre každé \(k_j\) máme \(h_{i(j)}\) - úlohy ktoré je najlepšie vymeniť, za predpokladu, že Krtko dá Hodoboxovi úlohu číslo \(j\), tak najlepší rozdiel časov, ktorý vedia výmenou dosiahnuť je minimum z \(|K - H + 2h_{i(j)} - k_j|\). Toto vieme tiež spočítať v lineárnom, a teda dokopy v \(O(n)\) čase dostať výsledok.

Myšlienka tejto úlohy sa volá dvaja bežci.

Implementačné detaily

Naše riešenie trochu odmávalo pár detailov v ktorých sa môže dobré riešenie stratiť. Poďme sa teda pozrieť na ne.

Po prvé, postupnosť časov na vstupe nemusí byť utriedená. To sa dá vyriešiť utriedením v programe, čo nám síce zväčší časovú zložitosť na \(O(n\log n)\) (to ale v tejto úlohe nie je problém).

Čo ak súčet pôvodných Krtkových časov je viac ako Hodoboxových? Jedno z riešení je ich jednoducho vymeniť - tvárime sa že Krtkove úlohy sú Hodoboxove a naopak. Ich polia v programe rovno vymeníme, a pokračujeme ako predtým.

Posledný problém je, že potrebujeme vypisovať ktoré úlohy by si mali vymeniť. Toto môžme vyriešiť tak, že miesto polí s \(k_i\) a \(h_i\), máme polia párov \((k_i, i)\), resp. \((h_i, i)\), a keď sa nám stane, že dve rôzne výmeny by mali rovnaký rozdiel, porovnáme indexy.

Celkovo tak dostávame riešenie ktoré beží v čase \(O(n\log n)\) (pre nezotriedené postupnosti úloh), s pamäťovou zložisťou \(O(n)\)