Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-12-04 13:24:03.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:sdo.in, sdo.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.6 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Statistici de ordine

A i-a statistică de ordine 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.

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

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.

Restricţii

  • 1 ≤ K ≤ N ≤ 3 000 000
  • Toate cele N elemente ale mulţimii A sunt din intervalul [1, 109]

Exemplu

sdo.insdo.out
8 3
1 10 4 13 7 6 11 14
6

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.

O primă soluţie, care numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de O(N^2), şi ar trebui să obţină 10 puncte.

O altă soluţie care selectează cele mai mici K elemente, având complexitatea O(N*K) obţine în jur de 20 puncte.

Altă soluţie care sortează elementele în ordine crescătoare şi are complexitatea O(Nlog_{2}N) ar trebui să obţină 50 puncte.

O altă soluţie, cu complexitatea O(Nlog_{2}K), care foloseşte un heap pentru a menţine cele mai mici K elemente ar trebui să obţină 60 puncte.

O soluţie care sortează elementele în timp aproape liniar, folosind radix sort ar trebui să obţină în jur de 70 de puncte.

În final, soluţia 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 găsindu-se în headerul algorithm. O sursă demonstrativă se găseşte aici. Complexitatea acestui algoritm este în medie O(N), însă teoretic în cel mai defavorabil caz poate atinge O(N^2) 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. De asemenea, şi soluţia care alege un pivot fixat obţine 100 de puncte. Există şi un algoritm teoretic ce garantează O(N) pe cel mai defavorabil caz, care se poate găsi în Cormen la capitolul "Statistici de Ordine".

Marius Ideal ar fi ca O(N2) 10, O(N*K) 20, O(N logN) 40, O(N logK) 50, O(N+KlogK) 60, O(N) cu radix sort 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(N2), 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). Marius Am rectificat punctajele în 10 şi 20 pentru O(N2) şi O(N*K). Nu e mare diferenţa între O(N) cu radix sort şi O(N) cu statistici, pentru că radix sort consumă şi memorie şi timp. Nu sunt bulăneli, pentru că obţii rezultatul corect întotdeauna. :P

Mishu Mie mi-a mers mai repede soluţia în O(NlogK) decât cea în O(N + KlogK), proabil din cauza priority_queue-ului, care din ce am văzut este destul de încet. De aceea propun modificarea puţin a punctajelor, O(N2) 10 O(N*K) 20 O(NlogN) 50 O(NlogK) 60 O(N) cu radix sort 70, O(N) 100 :) Marius Era de aşteptat să fie greu de departajat. Poate cu seturi ar fi mers mai repede. Dar dacă tot ai implementat-o să o menţionezi pe undeva, măcar ca idee. :)

Aplicaţii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?