|
Titlul: 697 Zip Scris de: Airinei Adrian din Aprilie 06, 2008, 14:36:39 Aici puteţi discuta despre problema Zip (http://infoarena.ro/problema/zip).
Titlul: Răspuns: 697 Zip Scris de: Toma Radu din Aprilie 07, 2008, 07:05:50 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? Titlul: Răspuns: 697 Zip Scris de: Adrian Diaconu din Aprilie 07, 2008, 13:30:56 Citat 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. Titlul: Răspuns: 697 Zip Scris de: Toma Radu din Aprilie 07, 2008, 14:14:06 :aha: :aha: Am inteles altceva din fraza aia. Chestia asta m-o incurcat si la Cluj. Mersi pentru raspuns :)
Titlul: Răspuns: 697 Zip Scris de: Filip Cristian Buruiana din Aprilie 07, 2008, 15:20:42 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.
Titlul: Răspuns: 697 Zip Scris de: Oltean Dorin din Aprilie 07, 2008, 21:58:17 Cat trebuie sa dea pe exemplul
Cod: 5 3 5 Titlul: Răspuns: 697 Zip Scris de: Toma Radu din Aprilie 08, 2008, 00:02:45 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.
Titlul: Răspuns: 697 Zip Scris de: Marius Stroe din Aprilie 08, 2008, 15:43:02 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?
Titlul: Răspuns: 697 Zip Scris de: Toma Radu din Aprilie 08, 2008, 15:48:24 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. Titlul: Răspuns: 697 Zip Scris de: Marius Stroe din Aprilie 08, 2008, 17:57:30 Foarte ambiguu enuntul.
Titlul: Răspuns: 697 Zip Scris de: Anca Dumitrache din Aprilie 17, 2008, 19:34:03 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. Titlul: Răspuns: 697 Zip Scris de: Savin Tiberiu din Aprilie 17, 2008, 19:35:11 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.
Titlul: Răspuns: 697 Zip Scris de: Anca Dumitrache din Aprilie 17, 2008, 19:43:20 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 :oops:Titlul: Răspuns: 697 Zip Scris de: Streche Robert din Iulie 08, 2015, 12:37:09 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 ](*,) :fighting: |