== include(page="template/taskheader" task_id="heapuri") ==
Se da o multime de numere cu $N$ elemente. Se cere sa se efectueze $M$ operatii asupra acestei multimi astfel. Operatiile sunt de $3$ tipuri:
Fie o multime de numere naturale initial vida. Se cere sa se efectueze $N$ operatii asupra acestei multimi, unde operatiile sunt de tipul celor de mai jos:
* Operatia de tipul 1: inserareaza elementul $x$ in multime
* Operatia de tipul 2: stergerea elementului $x$ din multime
* Operatia de tipul 3: care este elementul minim din multime
* operatia de tipul {$1$}: se insereaza elementul $x$ in multime
* operatia de tipul {$2$}: se sterge elementul intrat al $x$-lea in multime, in ordine cronologica
* operatia de tipul {$3$}: se afiseaza elementul minim din multime
h2. Date de intrare
Fisierul de intrare $heapuri.in$ va contine pe prima linie numarele $N$ si $M$. Pe a doua linie se vor afla $N$ numere, reprezentand multimea initiala. Pe liniile $3$ .. $M+2$ se vor afla operatiile descrise astfel: un numar $cod$ reprezentand tipul operatiei, iar in caz ca acesta este $1$ sau $2$ se mai da si un numar $x$ avand semnificatia din enunt.
Fisierul de intrare $heapuri.in$ va contine pe prima linie numarul $N$. Pe urmatoarele $N$ linii se va afla descrierea operatiilor care trebuie efectuate. Primul numar de pe fiecare linie, $cod$, reprezinta tipul operatiei. Daca $cod$ este $1$ sau $2$, atunci linia corespunzatoare va mai contine si numarul $x$, avand semnificatia din enunt.
h2. Date de ieşire
Fisierul de iesire $heapuri.out$ va contine pe cate o linie raspunsul pentru fiecare operatie de tipul $3$ din fisierul de intrare.
Fisierul de iesire $heapuri.out$ va contine, pe cate o linie, raspunsul pentru fiecare operatie de tipul $3$ din fisierul de intrare, in ordinea data.
h2. Restricţii
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100 000$
* $1 ≤ N ≤ 200 000$
* Elementele multimii nu vor depasi $1 000 000 000$
* Se garanteaza ca nu se va cere niciodata sa se afle minimul daca multimea este vida
* Se garanteaza ca nu vor exista $2$ operatii de tipul $2$ care sa stearga acelasi element din multime
* Pentru o operatie de tipul $2$ se va sterge un element care e deja intrat in multime
h2. Exemplu
table(example). |_. heapuri.in |_. heapuri.out |
| 5 6
4 9 7 12
| 9
1 4
1 7
1 9
3
1 2
2 4
2 1
3
2 2
2 4
3
| 4
| 4
2
7
|
|
h2. Explicatie
Dupa primele $3$ operatii vom avea in multime elementele $4$, $7$ si $9$. Astfel raspunsul la operatia de tip $3$ este $4$. In continuare vom adauga elementul $2$ si vom sterge primul element inserat, adica $4$, ramanand cu elementele $2$, $7$ si $9$. Vom sterge apoi al $4$-lea element intrat, adica $2$, in multime aflandu-se la sfarsit numai $7$ si $9$, minimul fiind $7$.
h3. Explicaţie
h2. Indicatii de rezolvare
La prima operatie de tipul $3$ multimea arata astfel: {4, 9, 7, 12}
La a doua operatie de tipul $3$ multimea arata astfel: {2, 9, 7 12}
la a treia operatie de tipul $3$ multimea arata astfel: {9, 7, 12}
Problema se poate rezolva prin metoda $brute-force$, tinand numerele intr-un vector si efectuand fiecare operatie fara nici un rafinament. Aceasta solutie are complexitate $O(1)$ pe o operatie de tipul $1$ si $O(N)$ pe celelalte. O astfel de abordare nu ar trebui sa ia mai mult de $30$ de puncte.
Rezolvarea optima foloseste o structura de date cunoscuta sub numele de _heap_, care suporta efectuarea operatiilor de tipul $1$ si $2$ in complexitate timp $O(log{~2~}N)$ si a operatiilor de tipul $3$ in timp constant.
Un heap este un arbore binar, cu proprietatea ca fiecare nod are asociata o cheie, cheie care este mai mica decat cheile asociate nodurilor din subarborele sau. Astfel, raspunsul la o operatie de tip $3$ se va gasi in radacina arborelui. Pentru a intelege modul in care functioneaza aceasta structura de date va recomandam sa cititi 'acest articol':heapuri, ce contine si cateva desene demonstrative. Un alt articol care prezinta acest subiect sa gaseste {'aici':http://en.wikipedia.org/wiki/Heap_(data_structure)}.
Pentru a putea implementa mai usor aceasta structura, se recomanda reprezentarea heap-ului ca un vector. Astfel radacina se va afla pe pozitia $1$, iar pentru un nod $i$, parintele sau se va afla pe pozitia $i/2$, in timp ce fii lui se vor afla pe pozitiile $2*i$ si, respectiv, $2*i+1$. De asemenea, va fi necesar sa pastram un vector cu pozitia fiecarui nod in heap, pentru a-l putea localiza rapid in cazul unei operatii de stergere. O implementare ce obtine $100$ de puncte se gaseste 'aici':job_detail/235474?action=view-source.
== include(page="template/taskfooter" task_id="heapuri") ==
h2. Aplicatii
h3. Indicatii de rezolvare
Heap-urile sunt niste structuri de date foarte utile, deoarece operatiile descrise mai sus sunt intalnite intr-o multime de situatii. Doua aplicatii clasice ce folosesc aceasta structura de date sunt 'algoritmul lui Dijkstra':problema/dijkstra si algoritmul lui Prim pentru determinarea 'arborelui partial de cost minim':problema/apm. Alte probleme ce pot fi rezolvate folosind heap-uri sunt:
Problema se poate rezolva brut-force tinand numerele intrun vector, si efectuand pur si simplu fiecare operatie. Aceasta solutie are complexitate $O(1)$ pe o operatie de tipul $1$ si $O(N)$ pe celelalte si nu ar trebui sa ia $~30$ de puncte.
* 'Base3':problema/base3
* 'Catun':problema/catun
* 'Lupul urias si rau':problema/lupu
* 'Timbre':problema/timbre
* 'Barbar':problema/barbar
* "Sarov zones":http://acm.sgu.ru/problem.php?contest=0&problem=171
* 'Mine':problema/mine
Rezolvarea optima se face folosind un heap, care suporta aceste efectuarea operatiilor de tipul $1$ si $2$ in $O(log N)$ si a operatiilor de tipul $3$ in $O(1)$.
Pentru detalii despre cum se implementeaza un heap si ce este acesta puteti citi "aici":http://infoarena.ro/heapuri.
== include(page="template/taskfooter" task_id="heapuri") ==
