Zadanie

Krtko a Hodobox - posledné piliere KSP - pracujú na novom ksp. Každý má list svojich úloh, ktoré má pripraviť, aby mohla ďalšia séria prebehnúť. Avšak, internet je beznádejne zaťažený Netflixami, online vyučovaním, Zoom callmi s mačiatkami… čo značne sťažuje komunikáciu. Čo sťažuje – internet im beznádejne padol, a nevyzerá, že by chcel znovu nabehnúť. Nuž - čo už, séria aj tak musí byť, offline či online.

Na poslednom stretku pred padnutím internetu si Krtko a Hodobox rozdelili úlohy. Avšak, po pokuse začať pracovať zistili, že rozdelenie úloh je nerovnomerné. Za veľmi obmedzenej komunikácie1 si dokázali sprostredkovať, že by si mali nejakú úlohu vymeniť.

Problém je, že internet nefunguje, tak si musia poslať úlohu poštou. Listy sú ale drahé, takže si môžu vymeniť presne dve úlohy2 (Hodobox pošle jednu svoju úlohu Krtkovi a neopak).

Pre každú úlohu vedia koľko práce na ňu bude treba. Ktoré dve úlohy by si mali vymeniť?

Úloha

Každý z nich má spraviť \(N\) úloh (\(N \leq 10^5\)). Hodoboxova \(m\)-ta úloha zaberie \(h_m\) minút času. Krtkova \(m\)-tá úloha zaberie zase \(k_m\) minút času.

Ktorú úlohu by si mali vymeniť, aby strávili čo najvyrovnanejší čas prácou na úlohách?

Formát vstupu

Na prvom riadku je číslo \(N\).

Na ďalšom riadku je \(N\) čísel \(h_1\), …, \(h_N\).

Na poslednom riadku je \(N\) čísel \(k_1\), …, \(k_N\).

Všetky časy sú od \(1\) do \(10^9\) vrátane.

Formát výstupu

Ak by nemali vymeniť žiadnu úlohu, vypíšte \(-1\).

Inak vypíšte dva čísla \(1 \leq i, j \leq N\) - naznačujúce, že Krtko má pripraviť Hodoboxovu úlohu číslo \(i\), a Hodobox Krtkovu úlohu číslo \(j\).

Ak existuje viac optimálnych riešení, vypíšte také, že \(i\) je najmenšie možné. Ak je viac riešení s rovnakým \(i\) vypíšte také, že \(j\) je najmenšie možné. V prípade že jedno z optimálnych riešení zahŕňa nemenenie úlohy, vypíšte to.

Obmedzenia

Úloha má osem sád.

V prvých štyroch platí, že \(N \leq 1000\).

Vo zvyšných \(N \leq 10^5\)

Navyše, v sade \(1\), \(2\), \(5\) a \(6\) sú časy Krtkových a Hodoboxových úloh usporiadané od najmenej časovo náročnej, po najviac.

Príklad

Input:

5
1 4 2 5 3
7 10 5 8 9

Output:

1 2

Pôvodné rozdelenie úloh dáva oveľa viac (o \(24\) minút) práce Krtkovi ako Hodoboxovi. Najlepšie je, aby si Hodobox zobral Krtkovu najťažšiu úlohu, a Krtko Hodoboxovu najľahšiu. Následne bude Krtko mať len o \(6\) minút viac práce než Hodobox

Input:

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

Output:

-1

Pôvodné rozdelenie úloh je už vyrovnané. Netreba meniť.

Input:

4
2 7 2 7
3 4 4 3

Output:

2 2

Najlepšie je vymeniť Hodoboxovu úlohu zaberajúcu \(7\) minút času za Krtkovu úlohu zaberajúcu \(4\) minúty času. Existuje tu viacero riešení, ale to s najmenšími indexami je vymeniť si úlohy na druhej pozícii.


  1. poštové holuby↩︎

  2. ani jeden z nich si nepamätá zadania úloh toho druhého↩︎

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)\)

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ť.