697 Zip

[•astronomy]

Aici puteţi discuta despre problema Zip.

[•tm_radu]

Cod:

Se calculeaza matricea d, cu semnificatia: d[i,j] este drumul de lungime maxima, care trece prin i noduri si se termina in nodul j.

Cum este evitat cazul in care drumul de lungime maxima trece prin acelasi nod de mai multe ori?

[•DITzoneC]

De asemenea, daca au existat bucati identice in fisierul initial, este posibil ca acestea sa apara de mai putine ori, in urma erorii.

Nu conteaza daca un drum trece de mai multe ori printr-un nod.

[•tm_radu]

  Am inteles altceva din fraza aia. Chestia asta m-o incurcat si la Cluj. Mersi pentru raspuns 

[•filipb]

Nici eu nu am inteles prea bine la inceput. Dar oricum, daca puneam restrictia sa nu luam un cuvant de mai multe ori era NP.

[•Dorin]

Cat trebuie sa dea pe exemplul

Cod:

5 3 5
abcba
cbabc
eabcb
abcba
cbeab

[•tm_radu]

Mie imi da 8. Mi-a iesit de 100 dupa ce mi-am dat seama ca pentru 2 cuvinte "abc" si "abc", costul unei muchii ce se poate atasa intre cele 2 cuvinte nu este 3.

[•Marius]

Din enunt deduc ca un cuvant poate fi folosit de mai multe ori. De ce pentru exemplu din enunt secventa de 2 bucati nu este "rado" + "rado", care dupa arhivare are lungimea 4?

[•tm_radu]

Cod:

Pentru doua bucati consecutive se determina cea mai lunga secventa de octeti de la sfarsitul primei bucati, care apare si la inceputul celei de-a doua bucati

Din cate am ineles eu, pentru un cuvant se iau toate sufixele exceptand cuvantul in sine, de aceea distanta dintre rado si rado ar fi 0.

[•Marius]

Foarte ambiguu enuntul.

[•anouk]

Din cate am ineles eu, pentru un cuvant se iau toate sufixele exceptand cuvantul in sine...

Deci, distanta dintre "aaaa" si "aaaa" e 3, nu 4.
Si totusi, chestia asta nu e specificata in enunt.

[•devilkind]

e 3 din cate am inteles eu, adik lungimea celui mai lung sufix al primului care e prefix al celuilalt. Nu stiu exact ce intelegi tu prin distanta.

[•anouk]

e 3 din cate am inteles eu, adik lungimea celui mai lung sufix al primului care e prefix al celuilalt. Nu stiu exact ce intelegi tu prin distanta.

edited out, defapt asa vroiam sa spun 

[•robertstreche]

iau 50 de pct cu wa pe testele 3,4,6,7,8
procedez in felul urmator:
calculez cel mai lung prefix care e sufix al cuvantului precedent pentru fiecare pereche de bucati(inclusiv pentru fiecare bucata si ea insasi) iar apoi fac o dinamica in O(n^3) care arata cam asa:
best[ i ][ j ]=min(best[ i-1 ][ l ]+cost[ l ][ j ]),unde best[ i ][ j ]=lungimea minima cu care scriu i bucati si ultima bucata are nr de ordine j
                                                                       cost[ i ][ j ]=lugimea prefixului maximal al lui j care este sufix al lui i
daca cineva m-ar putea ajuta as fi recunoscator  

[Later edit] dupa cateva ore de debug mi-am dat seama ca greseam KMP-ul