\begin{yl}{5}{Vale kuju 2}{kuju2}{2 sek / 3 sek}{80 punkti}
\emph{Idee: Phil Labuschagne ja Ahto Truu, teostus ja lahenduse selgitus: Ahto Truu}

\begin{quote}
Antud $A_1 < A_2 < \ldots < A_N$ ja $B_1 \le B_2 \le \ldots \le B_M$, kus $M, N \le 25\,000$.
Leida iga $i$ jaoks vähim $j$, mille korral $B_i \le A_j$, kasutades võimalikult vähe päringuid kujul ``kas $B_i \le A_j$?''
\end{quote}

Esimene võimalus selle ülesande lahendamiseks on püstitusest lähtuv naiivne algoritm: proovime iga punni järjest aukudesse $1, 2, \ldots$, kuni leiame esimese, mis pole liiga väike. Nii on tehtud failides \verb'sol1_naive.py' ja \verb'sol1_naive.cpp' toodud lahendustes, mis vaatavad iga $i$ väärtuse jaoks läbi keskmiselt pooled (ja halvimal juhul isegi kõik) $j$ väärtused ning kulutavad selleks kokku $O(M \cdot N)$ operatsiooni. See on piisav, et lahendada esimene alamülesanne, aga edasi võivad $M$ ja $N$ olla nii suured, et see lahendus ei mahu ajalimiidi piiridesse. 2.~ja 3.~alamülesande $1\,000 \cdot 25\,000 = 25\,000 \cdot 1\,000 = 25\,000\,000$ operatsiooni oleks ajalimiidi piires tehtavad, kui andmed oleks lahenduse enda mälus, aga hindamisprogrammiga suhtlemine on märksa aeglasem.

Üks võimalus parema lahenduse saamiseks on kasutada ära, et augud on kasvavalt sorteeritud, ja leida iga $i$ jaoks sobiv $j$ väärtus kahendotsinguga. Kahendotsing kulutab $N$-elemendilises jadas õige väärtuse leidmiseks $O(\log(N))$ võrdlemist ja seega kulub kokku $O(M \cdot \log(N))$ operatsiooni. Failides \verb'sol2_bin.py' ja \verb'sol2_bin.cpp' toodud lahendused seda teevadki ja teenivad punktid nii 1.~kui ka 2.~alamülesande eest.

Teine võimalus on kasutada ära, et punnid on sorteeritud, ja teha iga augu jaoks kahendotsing punnide hulgas. Selle juhu teeb natuke keerulisemaks asjaolu, et punnide diameetrid ei tarvitse unikaalsed olla ja siis peab olema hoolikas, et leida iga augu jaoks kõik punnid, mis sinna auku käivad. Failides \verb'sol3_bin.py' ja \verb'sol3_bin.cpp' toodud lahendused lähenevad sellele nii, et leiavad iga augu jaoks esimese punni, mis sinna \emph{ei mahu} ja teevad siis järelduse, et kõik väiksemad punnid peavad mahtuma. Eelmise juhuga sarnaselt kulutavad need lahendused $O(\log(M) \cdot N)$ operatsiooni ja teenivad punktid nii 1.~kui ka 3.~alamülesande eest.

Kolmas võimalus on kasutada ära, et mõlemad jadad on sorteeritud. See tähendab, et kui me oleme juba leidnud, et punn $i$ peab minema auku $j$, siis teame, et $i+1$ jaoks sobiv $j$ väärtus ei saa olla väiksem. Kuigi failides \verb'sol4_merge.py' ja \verb'sol4_merge.cpp' toodud lahendustes on kaks kordust üksteise sees, tasub tähele panna, et sisemine \verb'while'-kordus alustab iga kord sealt, kus eelmine \verb'while'-kordus lõpetas. Kui \verb'for'-kordus käib läbi $M$ erinevat $i$ väärtust, käivad kõik \verb'while'-korduse käivitused \emph{kokku} läbi $N$ erinevat $j$ väärtust ja seega kulutab selline kahe jada paralleelse läbimise algoritm $O(M + N)$ operatsiooni. Sellega teenivad need lahendused punktid nii 1.~kui ka 4.~alamülesande eest, aga 2.~ja 3.~alamülesandes nad maksimumpunkte ei saa, sest kui $M$ on palju väiksem kui $N$, siis on $M \cdot \log(N)$ väiksem kui $M + N$, ja sarnaselt ka siis, kui $N$ on palju väiksem kui $M$.

Üks võimalus maksimumskoori teenimiseks oleks kirjutada kolm eelkirjeldatud lahendust ja need kõik esitada. Siis saaks igas alamülesandes vähemalt üks lahendus täispunktid ja kolme lahenduse peale kogunekski ülesande eest kokku maksimumskoor.

Teine võimalus täispunktide saamiseks on kaks kahendotsingut kombineerida: kui teeme aukude hulgas esimese kahendotsingu mitte kõige väiksema ega kõige suurema, vaid keskmise punni jaoks, jagab leitud $i$-$j$ paar kaheks nii punnid kui augud; seejärel saame eraldi leida vastavused väiksemate punnide ja väiksemate aukude ning suuremate punnide ja suuremate aukude vahel, nagu on tehtud failides \verb'solx_binbin.py' ja \verb'solx_binbin.cpp' toodud lahendustes. Kui eeldame, et keskmisele punnile $i = M/2$ vastav auk $j$ jagab ühe kahendotsinguga ka aukude hulga umbes pooleks ($j \approx N/2$), saame selle algoritmi tööaja $T(M, N)$ hindamiseks rekurrentse võrrandi $T(M, N) \approx \log_2(N) + 2 \cdot T(M/2, N/2)$. Selle võrrandi lahendamine oleks päris keeruline, aga eksperimendid näitavad, et kui $M$ ja $N$ on ligikaudu võrdsed, kulutab see lahendus ainult mõned päringud rohkem kui kahe kahe jada paralleelne läbimine, ja kui $M$ ja $N$ on oluliselt erinevad, siis umbes poole vähem päringuid kui ühekordne kahendotsing.

\end{yl}
