== 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
h3. Explicaţie
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$.
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}
h2. Indicatii de rezolvare
== include(page="template/taskfooter" task_id="heapuri") ==
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.
h3. Indicatii de rezolvare
h2. Aplicatii
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.
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:
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.
* '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
*catre Paul si buru*: nu va speriati o sa pun in seara asta si testele si sursa, scuze ca am trecut peste deadline. My bad.
*Paul*:
1. Fii atent la brutul in N^2 care cauta minimul doar atunci cand stergi elementul minim si restul cazurilor le trateaza O(1).
2. Nu uita ca se poate face si in sqrt (tii pentru fiecare bucata de sqrt(N+M) minimul) si adaugi bucati pe parcurs.
3. Explica ca lumea cum se face un heap.
4. Baga probleme suplimentare / aplicatii. Explica in ce alte situatii e bun un heap (ex. Dijkstra, Prim).
*Cosmin*:
De ce e multime si nu colectie de elemente. Nu imi place ca adaugi o restrictie care nu e necesara la heapuri prin faptul ca zici ca elementele apartin unei multimi.
== include(page="template/taskfooter" task_id="heapuri") ==
