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 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.
 
h2. Probleme propuse
 
'Fence repair':http://acm.pku.edu.cn/JudgeOnline/problem?id=3253 - PKU
'Aviamachinations':http://acm.sgu.ru/problem.php?contest=0&problem=323 - SGU
'Hyperhuffman':http://acm.sgu.ru/problem.php?contest=0&problem=203 - SGU
'Scandura':problema/scandura

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