== include(page="template/taskheader" task_id="huffman") ==

Codurile Huffman reprezintă o tehnică foarte eficientă pentru compactarea datelor, spaţiul economisit fiind adesea cuprins între $20%$ şi $90%$. Algoritmul greedy pentru realizarea acestei codificări înregistrează frecvenţele de apariţie ale fiecărui simbol dintr-un fişier text, după care utilizează o modalitate optimă pentru reprezentarea fiecărui simbol sub forma unui şir binar.

'Codurile Huffman':http://en.wikipedia.org/wiki/Huffman_coding reprezintă o tehnică foarte eficientă de compactare a datelor, spaţiul economisit fiind cuprins adesea între $20%$ şi $90%$. Algoritmul greedy pentru realizarea acestei codificări înregistrează frecvenţele de apariţie ale fiecărui simbol dintr-un fişier, după care utilizează o modalitate optimă pentru reprezentarea fiecărui simbol sub forma unui şir binar.

Astfel, se dă un alfabet $A = {a{~1~},a{~2~},...,a{~n~}}$ format din $n$ caractere. Numim cod binar un şir de cifre de $0$ şi $1$ de o lungime finită. Fie $B$ un şir de lungime $n$ de coduri binare cu proprietatea că niciun cod $b{~i~}$ nu este prefixul unui alt cod $b{~j~}$ $(i ≠ j)$.

Astfel, se dă o mulţime $A = {a{~1~},a{~2~},...,a{~n~}}$ formată din $n$ simboluri. Numim cod binar un şir de cifre de $0$ şi $1$ de o lungime finită. Fie $B$ un şir de lungime $n$ de coduri binare cu proprietatea că niciun cod $b{~i~}$ nu este prefixul unui alt cod $b{~j~}$ $(i ≠ j)$.

h2. Cerinţă

Ştiindu-se că într-un text $T$ caracterul $a{~i~}$ apare de $v{~i~}$ ori, să se determine un şir $B$ astfel încât înlocuind în textul $T$ fiecare caracter $a{~i~}$ cu codul $b{~i~}$ să se obţină un text $T'$ de lungime minimă $lg$.

Ştiindu-se că într-un text $T$ simbolul $a{~i~}$ apare de $v{~i~}$ ori, să se determine un şir $B$ astfel încât înlocuind în textul $T$ fiecare simbol $a{~i~}$ cu codul $b{~i~}$ să se obţină un text $T'$ de lungime minimă $lg$.

h2. Date de intrare

h2. Restricţii
* $1 ≤ n ≤ 1 000 000$.

* $1 ≤ v{~i~} ≤ 100 000 000, 1 ≤ i ≤ n$.

* $1 ≤ v{~i~} ≤ 100 000 000$.

* $1 ≤ lg ≤ 10^18^$.

* $b{~i~} ≤ 10^18^, 1 ≤ i ≤ n$.

* $b{~i~} ≤ 10^18^, 1 ≤ i ≤ N$.

* Soluţia nu este unică; poate fi afişată orice soluţie ce duce la o lungime $lg$ minimă.
h2. Exemplu

h3. Explicaţie

!problema/huffman/Huffman_tree_2.svg 50%!

!problema/huffman?Huffman_tree_2.png 50%!

Caracterelor le-au fost atribuite codurile astfel:

| 9 | 2 | 01 | 18 |
| 10 | 2 | 10 | 20 |

Lungimea totală a textului $T'$ este $86$.

Lungimea totală a textului $T'$ este 86.

h2. Soluţie

Problema se rezolvă printr-un algoritm greedy, codarea Huffman. Se pot considera cele $N$ caractere noduri într-un graf, având fiecare un cost egal cu numărul de apariţii al caracterului în textul $T$. La fiecare pas se creeaza un nod nou şi se duc de la acesta $2$ muchii către nodurile de cost minim care nu au fost încă unite, costul acestuia fiind egal cu suma costurilor celor $2$ fii. Pentru a putea reconstitui ulterior codurile, se asociaza celor $2$ muchii valorile $0$ şi $1$. Se va obţine un arbore binar cu $2*N-1$ noduri, suma costurilor nodurilor interne fiind egală cu lungimea textului $T'$.

Problema se rezolvă printr-un algoritm greedy, codarea Huffman. Se pot considera cele $N$ caractere noduri într-un graf, având fiecare un cost egal cu numărul de apariţii al caracterului în textul $T$. La fiecare pas se creeaza un nod nou şi se duc de la acesta $2$ muchii către nodurile de cost minim care nu au fost încă unite, costul acestuia fiind egal cu suma costurilor celor $2$ fii. Pentru a putea reconstitui ulterior codurile, se asociaza celor $2$ muchii valoarile $0$ şi $1$. Se va obţine un arbore binar cu $2*N-1$ noduri, suma costurilor nodurilor interne fiind egală cu lungimea textului $T'$.

Algoritmul se poate generaliza pentru coduri in baza $K$, selectand la fiecare pas cele mai mici K noduri pentru a le uni cu nodul nou creat. De asemenea, trebuie create caractere fictive cu $0$ aparitii, pentru ca numărul iniţial de noduri să fie de forma $X * (K-1) + 1$.
h3. Etape de rezolvare

O 'soluţie':job_detail/370657?action=view-source în care căutarea celor $2$ noduri de cost minim se face liniar are o complexitate $O(N^2^)$ şi obţine $30$ de puncte. Folosind un heap pentru a extrage nodurile de cost minim, complexitatea scade la $O(N log{~2~} N)$. Această 'soluţie':job_detail/370924?action=view-source obţine $70$ de puncte. În cazul în care costurile nodurilor sunt date în ordine crescătoare, se pot ţine $2$ cozi, conţinând nodurile iniţiale, respectiv nodurile interne. Observând că nodurile sunt sortate crescător după cost, se pot extrage cele $2$ minime şi introduce nodul nou în $O(1)$. Această 'soluţie':job_detail/370923?action=view-source obţine $100$ de puncte.

O 'soluţie':job_detail/370657?action=view-source în care căutarea celor $2$ noduri de cost minim se face liniar are o complexitate $O(N^2^)$ şi obţine $30$ de puncte. Folosind un heap pentru a extrage nodurile de cost minim, complexitatea scade la $O(N log~2~ N)$. Această 'soluţie':job_detail/370924?action=view-source obţine $70$ de puncte. În cazul în care costurile nodurilor sunt date în ordine crescătoare, se pot ţine $2$ cozi, conţinând nodurile iniţiale, respectiv nodurile interne. Observând că nodurile sunt sortate crescător după cost, se pot extrage cele $2$ minime şi introduce nodul nou în $O(1)$. Această 'soluţie':job_detail/370923?action=view-source obţine $100$ de puncte.

h2. Probleme propuse