Diferente intre titluri:
Diferente intre continut:
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.
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.
Un heap este un arbore binar echilibrat, cu proprietatea ca fiecare nod, are asociata o cheie, cheie care este mica decat cheile asociate nodurilor din subarborele sau. Evident raspunsul la operatiile de tip $3$ se vor gasi in radacina arborelui.
O implementare usoara este aceea de a reprezenta heapul ca pe un vector. Astfel radacina se va afla pe pozitia $1$ iar pentru un nod $i$, fii lui se vor afla pe pozitiile $2*i$ respectiv $2*i+1$.
Cand vrem sa inseram un element nou in vector, il adaugam la capatul sirului, si apoi il interschimbam cu parintele sau pana cand se respecta proprietatea de heap.
De asemenea pentru fiecare element vom tine minte pozitia pe care se afla acesta in vector. Astfel ca atunci cand o sa vrem sa stergem un element din heap, il interschibam cu ultimul element din vector si scadem dimensiunea acestuia cu $1$. Totusi acest lucru ne poate strica proprietatea de heap. Astfel avem $2$ cazuri:
*Elementul nostru este mai mic decat parintele sau, caz in care aplicam acelasi algoritm pe care il aplicam si atunci cand vrem sa adaugam un nod in heap, adica il interschibam cu parintele sau pana cand se respecta proprietatea de heap.
*Elementul nostru este mai mare decat fii sai, caz in care vom continua sa il interschimbam cu cel mai mic fiu al sau pana cand se va respecta proprietatea de heap.
Puteti citi "aici":http://infoarena.ro/heapuri mai multe detalii.
h3. Probleme suplimentare
* "Djikstra":http://infoarena.ro/problema/dijkstra
* "Catun":http://infoarena.ro/problema/catun
*Paul*:
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
