Scandura

Notam lungimea scandurei finale i cu l[i].

Vom incerca sa reprezentam taieturile scandurilor sub forma unui arbore. Radacina arborelui va fi scandura initiala de lungime . In urma unei taieturi, dintr-o scandura de lungime A vor porni maxim M alte muchii catre noduri a caror suma a lungimilor va fi tot A. Frunzele arborelui vor reprezenta cele N lungimi de scanduri finale. Costul unei modalitati de taiere a scandurii mari va fi atunci egal cu suma valorilor nodurilor din arbore care nu sunt frunze. Datorita faptului ca un nod in arbore are costul egal cu suma costurilor fiilor, putem reprezenta costul fiecarui nod in functie de costul frunzelor. Daca drumul de la frunza i pana la radacina trece prin k noduri (incluzand radacina, neincluzand frunza), atunci costul total produs de frunza i va fi egal cu k * l[i]. Costul total al unei modalitati de taiere va fi egal cu .

Pentru M = 2, putem echivala imediat problema cu cea a determinarii unei codari Huffman. Codarea Huffman este o metoda de comprimare a datelor, cunoscandu-se pentru fiecare caracter din alfabet frecventa cu care el apare in text. Deoarece unele caractere apar mai des decat altele, putem comprima textul asociind lungimi diferite in reprezentarea binara a fiecarui caracter si deci costul total pentru a reprezenta un text va fi egal cu , unde len[i] este lungimea reprezentarii caracterului i, iar frecventa[i] este frecventa cu care apare el. Reprezentarea huffman genereaza un arbore in acelasi mod ca si problema noastra, un bit de 0 simbolizand vecinul stang, un bit de 1 simbolizand vecinul drept. Fiecarei scanduri initiale de lungime l[i] ii putem asocia un caracter distinct cu o frecventa de l[i] si se observa ca problemele devin echivalente.

Pentru M > 2 putem extinde codarea Huffman, considerand ca un caracter este reprezentat in baza M, in loc de baza 2.

Pentru M = 2, o codare Huffman de cost minim se determina extragand la fiecare pas cele 2 noduri cu cost cel mai mic si inlocuirea lor cu un nod de cost egal cu suma lor. Acelasi lucru il vom face si pe cazul generalizat. Observam ca este optim sa taiem la fiecare pas scandura in cat mai multe bucati, doar la ultima taietura rezultand mai putin de M bucati. Pentru a ne usura implementarea vom adauga la inceput cateva scanduri auxiliare de lungime 0 pana cand fiecare scandura o vom putea taia in fix M bucati. La fiecare pas din algoritm vom scoate M noduri din structura si vom adauga unul inapoi, in final ramanand cu un singur nod cu costul egal cu suma scandurilor, deci vom adauga inainte de executarea algorimului scanduri de lungime 0 pana cand N devine de forma (M - 1) * k + 1.

Implementarea in O(N log N) a algoritmului pentru determinarea codarii Huffman, cu ajutorul structurilor de date heap, obtine 70 de puncte. Pentru 100 de puncte este necesara implementarea algoritmului in complexitate O(N), folosind faptul ca lungimile scandurilor in fisierul de intrare sunt sortate.