== include(page="template/taskheader" task_id="sdo") ==
'A $i$-a statistică de ordine':http://en.wikipedia.org/wiki/Order_statistic a unei mulţimi este al $i$-lea cel mai mic element al mulţimi. Fiind date o mulţime de numere naturale $M$, de $n$ elemente şi un număr natural $k$, să se determine a $k$-a statistică de ordine a mulţimii.
A $i$-a 'statistică de ordine':http://en.wikipedia.org/wiki/Order_statistic a unei mulţimi este al $i$-lea cel mai mic element al mulţimi. Fiind date o mulţime de numere naturale $A$, de $N$ elemente şi un număr natural $K$, să se determine a $K$-a statistică de ordine a mulţimii.
h2. Date de intrare
Fişierul de intrare $sdo.in$ conţine pe prima linie $n$ şi $k$, iar pe a doua linie $n$ numere naturale, reprezentând elementele mulţimii $M$.
Fişierul de intrare $sdo.in$ conţine pe prima linie $N$ şi $K$, iar pe a doua linie $N$ numere naturale, reprezentând elementele mulţimii $A$.
h2. Date de ieşire
În fişierul de ieşire $sdo.out$ se va afla un singur număr natural, reprezentând a $k$-a statistică de ordine a mulţimii.
În fişierul de ieşire $sdo.out$ se va afla un singur număr natural, reprezentând a $K$-a statistică de ordine a mulţimii.
h2. Restricţii
* $1 ≤ k ≤ n ≤ 3 000 000$.
* Toate cele $n$ elemente ale mulţimii $M$ sunt din intervalul $[1, 10^9^]$.
* $1 ≤ K ≤ N ≤ 3 000 000$
* Toate cele $N$ elemente ale mulţimii $A$ sunt din intervalul $[1, 10^9^]$
h2. Exemplu
h3. Explicaţie
În exemplu, se observă că elementele aranjate în ordine crescătoare sunt: $1 4 **6** 7 10 11 13 14$, prin urmare al $3$-lea cel mai mic element este $6$.
În exemplu, se observă că elementele aranjate în ordine crescătoare sunt: $1 4 **6** 7 10 11 13 14$, prin urmare al 3-lea cel mai mic element este 6.
h2. Indicaţii de rezolvare
O primă 'soluţie':job_detail/370055?action=view-source, care numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de <tex>O(N^2)</tex>, şi ar trebui să obţină $20$ puncte.
'Soluţia':job_detail/370055?action=view-source ce numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de <tex> O(n^2) </tex>, ar trebui să obţină $10$ puncte.
*Marius* Mai e o soluţie în O(N*K), care rulează selection sort de K ori. Dacă ai K mic atunci ia multe puncte. Poate bagi o sursă.
Dacă modificăm algoritmul de 'sortare prin selecţie':http://en.wikipedia.org/wiki/Selection_sort pentru a selecta cele mai mici $k$ elemente, obţinem complexitatea <tex> O(nk) </tex>. Această 'soluţie':job_detail/371158?action=view-source obţine în jur de $20$ puncte.
Altă 'soluţie':job_detail/369661?action=view-source care sortează elementele în ordine crescătoare şi are complexitatea <tex>O(Nlog_{2}N)</tex> ar trebui să obţină $50$ puncte.
Una din îmbunătăţiri constă în 'sortarea':problema/algsort elementelor în complexitate <tex> O(n log_{2}n) </tex> şi selectarea valorii căutate în $O(1)$. 'Soluţia':job_detail/369661?action=view-source ar trebui să obţină $50-60$ puncte.
*Marius* Un radix sort cât să ia? Grupezi câte 2^16. Are O(N + K).
O altă 'soluţie':job_detail/369662?action=view-source, cu complexitatea <tex> O(n log_{2}k) </tex>, foloseşte un 'heap':problema/heapuri pentru a menţine cele mai mici $k$ valori. Aceasta ar trebui să obţină $60$ puncte, fiind o îmbunătăţire faţă de soluţia anterioară. În continuare, dacă construim un heap în complexitate <tex> O(n) </tex> iar pe acesta realizăm o 'parcurgere în lăţime':problema/bfs ajungem la 'soluţia':job_detail/371237?action=view-source ce obţine acelaşi punctaj de complexitate <tex> O(n+klog_{2}k) </tex>. Deşi complexitatea este teoretic mai bună, ea se comportă mai slab decât cea menţionată anterior, datorită folosirii unei structuri de date ce încetineşte uşor, $priority_queue$.
O altă 'soluţie':job_detail/369662?action=view-source, cu complexitatea <tex>O(Nlog_{2}K)</tex>, care foloseşte un heap pentru a menţine cele mai mici $K$ elemente ar trebui să obţină $70$ puncte.
O 'soluţie':job_detail/371166?action=view-source care foloseşte proprietatea că valorile sunt numere întregi, sortează elementele în timp liniar cu algoritmul 'radix sort':http://en.wikipedia.org/wiki/Radix_sort. Această sursă ar trebui să obţină în jur de $70$ de puncte. Motivele acestui punctaj constau în dimensiunea mare a datelor de intrare şi memoria suplimentară folosită.
*Marus* Se poate mai bine de O(N logK). Poţi crea un min-heap în O(N) din care extragi K elemente. Deci O(N + KlogK) cât să ia?
*Mishu* Nu am înţeles exact cum zici. Dacă îmi creez un min-heap cu N elemente si extrag primele K nu iese O(NlogN + KlogN)?
'Soluţia':/job_detail/372622?action=view-source cea mai eficientă foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a $k$-a statistică de ordine. Practic, acest algoritm este asemănător algoritmului 'Quicksort':http://en.wikipedia.org/wiki/Quicksort, cu deosebirea că se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. Însă, această soluţie obţine $90$ de puncte. În 'sursa':job_detail/372623?action=view-source de $100$ de puncte se va folosi un pivot ales aleator, în locul unui pivot fixat. Complexitatea acestui algoritm este în medie <tex> O(n) </tex>, însă, teoretic, în cel mai defavorabil caz poate atinge <tex> O(n^2) </tex> pentru că am putea fi extrem de nenorocoşi să partiţionăm în jurul celui mai mare element rămas. Dar, deoarece algoritmul este aleator, nu există date de intrare particulare care să provoace comportamentul celui mai defavorabil caz. Iată motivul pentru care algoritmul ce selectează pivotul random este mai eficient decât cel care selectează un pivot fixat. Acest algoritm este implementat şi în STL: funcţia 'nth_element':http://cplusplus.com/reference/algorithm/nth_element/ găsindu-se în headerul 'algorithm':http://cplusplus.com/reference/algorithm/. O sursă demonstrativă se găseşte 'aici':job_detail/369659?action=view-source. Există şi un algoritm teoretic ce garantează <tex> O(n) </tex> pe cel mai defavorabil caz, şi se poate găsi în cartea '„Introducere în algoritmi”':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm la capitolul '„10. Statistici de Ordine”':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap10.htm.
În final, 'soluţia':job_detail/369692?action=view-source care ar trebui să obţină $100$ de puncte foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a $K$-a statistică de ordine. Practic, acest algoritm este foarte asemănător quicksort-ului, doar că în loc să se sorteze tot şirul se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. Acest algoritm este implementat şi în STL, funcţia 'nth_element':http://cplusplus.com/reference/algorithm/nth_element/ găsindu-se în headerul 'algorithm':http://cplusplus.com/reference/algorithm/. O sursă demonstrativă se găseşte 'aici':job_detail/369659?action=view-source. Complexitatea acestui algoritm este în medie <tex>O(N)</tex>, însă teoretic în cel mai defavorabil caz poate atinge <tex>O(N^2)</tex> pentru că am putea fi extrem de nenorocoşi să partiţionăm în jurul celui mai mare element rămas. Dar deoarece algoritmul este aleator, nu există date de intrare particulare care să provoace comportamentul celui mai defavorabil caz.
h2. Aplicaţii
*Marius* Ideal ar fi ca O(N^2^) 20, O(N*K) 30, O(N logN) 40, O(N logK) 50, O(N+KlogK) 60, O(N+K), 70, O(N) 100. Am vorbit cu Paul şi am ajuns la concluzia că implementat de mână ca în Cormen avem worst case O(N^2), însă cu STL worst case e O(N logN) deoarece... aici mă mai gândesc, dar tind să cred că se bazează pe introsortul lui QuickSort. Algoritm O(N) de selecţie este cel cu împărţire în bucăţi de câte 5 elemente, însă, în practică, se comportă mai prost decât cel care alege un pivot aleator. Eu zic să bagi o sursă care nu alege un pivot aleator (ci pe primul) pentru comparaţie cu cea care alege pivotul aleator şi să zici decât că există acest algoritm teoretic cu cu ordinul de execuţie O(N) (şi nu O(N) în medie). Nu mă gândeam că ies atâtea surse. :)
*Mishu* Nu este cam mare diferenţa între O(N + K) si O(N). În plus, atât soluţia în O(N^2^), cât şi cea în O(N*K) sunt cam bulăneli, cred că este cam mică diferenţa (10 puncte) între O(N*K) si O(NlogN).
h3. Aplicaţii
* 'Toys':problema/toys
* 'Geometrie':problema/geom
