h2. Date de iesire
In fisierul $algsort.out$ veti tipari cele $N$ numere din fisierul de intrare, sortate in ordine crescatoare.
In fisierul $algsort.out$ veti tipari restul impartirii sumei <tex>S=\sum_{i=1}^N {i \cdot v[i]}</tex> la numarul $123457$, unde $v[]$ este vectorul celor $N$ numere sortate in ordine crescatoare (si indexate incepand cu pozitia $1$). Pentru detalii despre calculul acestei sume, consultati sectiunea $Observatii$.
h2. Restrictii
* $1 ≤ N ≤ 500 000$
* Toate cele $N$ numere vor fi cuprinse intre $0$ si $2^31^-1$ inclusiv.
* Toate cele $N$ numere se vor fi cuprinse intre $0$ si $2^31^-1$ inclusiv.
h2. Exemplu
table(example).
|_. algsort.in |_. algsort.out |
| 6
4 1 7 5 1 3 | 1 1 3 4 5 7 |
| 5
4 7 5 1 3 | 74 |
h2. Observatii
Limitele de timp si memorie folosite va ofera posibilitatea de a studia comparativ diverse implementari ale diversilor algoritmi de sortare intalniti.
h3. Explicatie
In analiza comportamentului surselor evaluate trebuie sa tineti cont de faptul ca cea mai mare parte a timpului de executie va fi ocupata de citirea si scrierea datelor in fisier (pentru testele maxime, intre $400$ si $600 ms$ vor fi ocupate de operatiile de intrare/iesire). *Nu* este necesara folosirea functiilor specializate de citire a blocurilor de caractere (parsarea citirii) pentru a obtine punctajul maxim, insa recomandam folosirea stream-urilor C++, care se comporta mai bine in mediul de evaluare decat functiile de citire din libraria standard C.
Dupa sortare, vectorul v devine:
h3. Structura testelor
|_. i | 1 | 2 | 3 | 4 | 5 |
|_. v[i] | 1 | 3 | 4 | 5 | 7 |
Datorita largii varietati de algoritmi de sortare si comportarii lor diferite in functie de anumite particularitati structurale ale datelor de intrare, pentru evaluarea problemei se folosesc $5$ grupe de cate $4$ teste. Toate testele aflate in aceeasi grupa vor avea aceeasi valoare pentru $N$ si acelasi domeniu de valori pentru cele N numere: <tex>0 \le v[i] \le \lfloor N \cdot \gamma \rfloor</tex>, unde <tex>\gamma = \frac{2^{31}-1}{500000}</tex>. Valorile lui $N$ pentru cele 5 grupe de teste sunt $10$, $1.000$, $100.000$, $350.000$ respectiv $500.000$. Testele din cadrul fiecarei grupe se vor diferentia astfel:
Astfel, <tex>S=1 \cdot 1 + 2 \cdot 3 + 3 \cdot 4 + 4 \cdot 5 + 5 \cdot 7=74</tex>, iar restul impartirii acestui numar la $123457$ este tot $74$.
* primul test va contine numere generate aleator
* al doilea test va contine numere "aproape sortate" (numarul de inversiuni din lista de numere este mic)
* al treilea test va contine numerele sortate in ordine descrescatoare
* al patrulea test va contine numerele in ordine aleatoare, insa vor exista putine perechi de numere distincte (foarte multe dintre numere vor aparea de mai multe ori in fisierul de intrare)
h2. Observatii
h2. Solutie
Problema sortarii eficiente a datelor impune, in conditiile de fata, cateva particularitati de evaluare pe care le vom descrie in continuare si care au fost pe care le vom descrie in continuare:
Structura problemei cere implementarea unui 'algoritm de sortare pe baza de comparatii':http://en.wikipedia.org/wiki/Comparison_sort. Exista, de asemenea, algoritmi de sortare care nu compara explicit elementele si care au performante mai bune pentru anumite cazuri particulare ale structurii datelor de intrare; acestia nu se preteaza insa cerintelor impuse in cazul de fata.
h3. Citirea datelor
Orice algoritm de sortare bazat pe comparatii trebuie sa efectueze, pentru a putea distinge corect toate cele <tex>N!</tex> permutari posibile ale sirului de valori, <tex>\Omega \left( N \cdot \log N \right)</tex> comparatii (o justificare a acestui rezultat se afla 'aici':http://www.cs.utexas.edu/~vlr/s07.357/notes/lb-apr5.pdf). Din aceasta perspectiva, algoritmi precum 'Merge Sort':http://en.wikipedia.org/wiki/Merge_sort, 'Heapsort':http://en.wikipedia.org/wiki/Heapsort sau 'Introsort':http://en.wikipedia.org/wiki/Introsort sunt optimi, executand <tex>\Theta \left( N \cdot \log N \right)</tex> operatii in cazul cel mai defavorabil. Dintre acestia, Merge Sort foloseste <tex>\mathit{O}\left( N \right)</tex> memorie suplimentara in implementarea clasica.
Limita de timp impusa este de $500 ms$, din care, pentru testele maxime, intre $150$ si $300 ms$ vor fi ocupate de citirea datelor. *Nu* este necesara folosirea functiilor specializate de citire a blocurilor de caractere (parsarea citirii) pentru a obtine punctajul maxim, insa recomandam folosirea stream-urilor C++, care se comporta mai bine in mediul de evaluare decat functiile standard.
Un alt algoritm de sortare foarte popular este 'Quicksort':http://en.wikipedia.org/wiki/Quicksort. Desi complexitatea sa pentru cazul cel mai defavorabil este <tex>\mathit{O}\left( N^2 \right)</tex>, in practica se comporta foarte bine si cunoaste multe imbunatatiri (detalii in prezentarea profesorului Robert Sedgewick 'aici':http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf si a profesorului Jon Bentley 'aici':blog/three-beautiful-quicksorts).
h3. Scrierea rezultatelor
In libraria standard a limbajului C este implementata o varianta naiva de Quicksort (poate fi apelata prin $qsort(...)$ - o sursa demonstrativa gasiti 'aici':job_detail/239877?action=view-source), iar STL-ul ofera programatorilor C++ atat functia $sort$, o implementare a algoritmului Introsort (o sursa demonstrativa 'aici':job_detail/239875?action=view-source), cat si functiile $make_heap$ si $sort_heap$, pentru a putea implementa usor Heapsort (sursa demonstrativa 'aici':job_detail/239880?action=view-source). De asemenea, o varianta scurta de implementare a algoritmului Merge Sort (inspirata din acest 'articol':multe-smenuri-de-programare-in-cc-si-nu-numai) puteti gasi 'aici':job_detail/239878?action=view-source.
Fisierul de iesire nu va contine toate numerele afisate in ordine crescatoare deoarece dimensiunea lui ar creste foarte mult si, odata cu aceasta, si timpul de executie al programului. Astfel, cea mai mare parte a timpului alocat ar fi ocupata de scrierea informatiilor in fisier, si nu de algoritm in sine. Din acest motiv, dupa ce vectorul de numere (il vom nota cu $v$) va fi sortat, va trebui calculata si tiparita suma $S$ conform cerintei. Valoarea acestei sume poate fi foarte mare, iesind din tipurile standard de date, iar pentru calculul ei ne vom folosi de faptul ca nu avem nevoie decat de restul impartirii ei la numarul $123457$:
Alti algoritmi neoptimi, ce ruleaza in cazul mediu in complexitate <tex>\mathit{O}\left( N^2 \right)</tex>, dar elementari si foarte usor de inteles sunt: "Bubblesort":http://en.wikipedia.org/wiki/Bubble_sort, "Selection Sort":http://en.wikipedia.org/wiki/Selection_sort si "Insertion Sort":http://en.wikipedia.org/wiki/Insertion_sort.
==code(c) |
S <- 0
pentru i <- 1, N
S <- (S + i*v[i]) mod 123457
sfarsit pentru
==
Pentru mai multe detalii si un studiu comparativ al algoritmilor de sortare vizitati 'pagina Wikipedia dedicata acestui subiect':http://en.wikipedia.org/wiki/Sorting_algorithm.
Singurul detaliu la care trebuie sa mai avem grija este faptul ca rezultatul inmultirii $i*v[i]$ poate depasi tipul de date in care se incadreaza factorii ei (intreg cu semn pe 32 de biti). De aceea, fie va trebui sa facem o conversie explicita catre un tip intreg pe 64 de biti ($long long$ sau $int64$), fie ne vom folosi de particularitatile de limbaj sau de compilator, declarand unul dintre factorii produsului ca intreg pe 64 de biti.
h2. Aplicatii
h3. Structura testelor
Sortarea datelor apare ca subproblema sau etapa intermediara intr-o larga varietate de probleme si algoritmi, fiind considerata astfel una dintre temele principale de studiu in informatica teoretica. Diverse strategii greedy cu aplicatii in planificarea activitatilor, determinarea 'arborilor partiali de cost minim':problema/apm ({'algoritmul lui Kruskal':http://en.wikipedia.org/wiki/Kruskal's_algorithm}) sau constructia 'codurilor Huffman':http://en.wikipedia.org/wiki/Huffman_coding, implica o prima etapa de sortare a datelor. De asemenea, in geometria computationala intalnim sortarea punctelor dupa unghiul polar pentru determinarea 'infasuratorii convexe':problema/infasuratoare sau metoda 'dreptei de baleiere':http://en.wikipedia.org/wiki/Sweep_line, care presupune sortarea punctelor-eveniment dupa anumite criterii.
Datorita largii varietati de algoritmi de sortare si comportarii lor diferite in functie de anumite particularitati structurale ale datelor de intrare, pentru evaluarea problemei se folosesc $5$ grupe de cate $4$ teste. Toate testele aflate in aceeasi grupa vor avea aceeasi valoare pentru $N$ si acelasi domeniu de valori pentru cele N numere: <tex>0 \le v[i] \le \lfloor N \cdot \gamma \rfloor</tex>, unde <tex>\gamma = \frac{2^{31}-1}{500000}</tex>. Testele din cadrul fiecarei grupe se vor diferentia astfel:
Alte probleme in care este folosita (intr-o forma sau alta) sortarea datelor:
* primul test va contine numere generate aleator
* al doilea test va contine numere "aproape sortate" (numarul de inversiuni din lista de numere este mic)
* al treilea test va contine numerele sortate in ordine descrescatoare
* al patrulea test va contine numerele in ordine aleatoare, insa vor exista putine perechi de numere distincte (foarte multe dintre numere vor aparea de mai multe ori in fisierul de intrare)
* 'Loto':problema/loto
* 'Reactivi':problema/reactivi
* "Akbardin’s Roads":http://acm.timus.ru/problem.aspx?space=1&num=1178
* 'Granita':problema/granita
* 'Lungimi de interval':problema/linterv
* 'Sport':problema/sport
* "Rooks":http://acm.sgu.ru/problem.php?contest=0&problem=269
* 'Cai':problema/cai
* "Inversions":http://acm.sgu.ru/problem.php?contest=0&problem=180
* 'Cutii':problema/cutii
* 'Invsort':problema/invsort
* 'Mexc':problema/mexc
* 'Demolish':problema/demolish
* "Wolves and Sheep":http://acm.sgu.ru/problem.php?contest=0&problem=349
* "Antenna":http://www.hsin.hr/ceoi2006/tasks/day1/antenna.pdf, _CEOI 2006_
* "Sails":http://hsin.hr/ioi2007/tasks/day1/sails.pdf, _IOI 2007_
== include(page="template/taskfooter" task_id="algsort") ==
== include(page="template/taskfooter" task_id="algsort") ==
