infoarena

Aici puteţi discuta despre problema Carte (http://infoarena.ro/problema/carte).

Cum aţi rezolvat această problemă?

Eu am încercat mai multe soluţii, dar toate fără succes:

• Cu un trie: MLE
• Cu hash-uri folosind set: TLE
• Cu hash-uri de mână: MLE sau TLE (în funcţie de numărul de bucket-uri)

KMP, ca sa vezi pentru fiecare cuvant din dictionar unde se potriveste in sirul mare + bitset, ca sa poti tine minte potrivirile si sa intre in memorie :)


LE: Eu am Match[ i ][ j ] - 1 daca exista vreun cuvant in dictionar care se potriveste pe subsecventa [i...j] in sirul mare, de aceea am nevoie de bitset.

merge si fara bitset, o matrice LxN char[3000][1000] in care bifezi daca pe pozitia L se potriveste sirul N, si acopera intervalul [L, L + lungime[N]].

Hashurile erau mult prea incete (de 3-4 ori mai incete decat limita de timp, de 8 ori mai incete decat solutia oficiala). Cu trie complexitatea crestea, devenea N^2 * sigma. Solutia oficiala e cea pe care a spus Radu. Eu tineam vector<bool>, tot 1 bit pe element consuma.

Eu nu pot sa inteleg de ce la problema asta nu ar intra cu hash-uri. :-k Pana la urma KMP-ul parcurge ambele siruri pentru fiecare sir mic. Asta ar insemna ca face in jur de 3000*1000 + 3000 operatii adica in jur de jumatate din limita de timp. Hash-urile ar procesa fiecare sir o singura data (adica (3000+3000) operatii * operatii cu hash-uri (care mi-e greu sa cred ca sunt de 8000 de ori mai incete decat un O(1) curat)). Chiar daca am lua mod-ul 666013 presupun ca ar intra si in timp si in memorie. Ca sa imi garantez ca minimizez sansa unei coliziuni de valori hash o sa-mi tin 2 valori hash eventual. De asemenea, nu inteleg cum de intra sa iti initializezi o matrice de 3000 pe 3000 la fiecare test (cum zice Visan Radu). De accord ca o matrice de 3000 pe 1000 intra (asa este, de altfel, si solutia mea). Daca cineva cunoaste ceva mai bine astfel de insight-uri si ar vrea sa imi raspunda as fi foarte recunoscator.  :thumbup:

P.S.: Cel mai ciudat lucru este ca daca pun bitset in loc de bool la matricea mea de 3000 pe 1000, merge mai incet. :?

Numarul mediu de coliziuni daca ai sa calculezi e mic. Problema nu sunt colinziunile ci operatiile modulo care sunt mult mult mai incete. In cazul de fata degeaba aveai complexitatea buna. Sursele cu hashuri erau mult mai incete de 3-4. Sursa cu kmp a mea avea cam jumate din limita de timp. Sursa cu hashuri originala avea in jur de 4 secunde pe testul maxim. Si optimizata nu ar fi intrat in timp nici daca dublam limita de timp.

  Pentru cei interesati de metoda cu hash, dupa ce mi-am trimis sursa ca un copil constiincios (KMP + dinamica)  :thumbup:
m-am uitat peste sursele celorlalti si am gasit sursa aceasta : http://www.infoarena.ro/job_detail/1065650, si altele ca si ea din aceeasi
zi. Dar aceasta sursa m-a impresionat!!! :shock: :shock: :shock: (112 ms, 424 kb). O solutie cu KMP scoate fix dublu ca timp, iar ca memorie de 8 ori mai mult!
  Habar nu am ce sunt hash-urile, dar propozitia aceasta: "Sursa cu hashuri originala avea in jur de 4 secunde pe testul maxim"  :-' m-a facut sa caut un curajos care a reusit sa faca cu aceasta metoda.
  Spor!

Salut. Am avut o pățanie rezolvand problema asta. Codul care determina pozitia fiecarui cuvant in carte nu gasea pozitiile care se suprapuneau.

Spre exemplu, daca aveam cartea aaaa si cuvantul aa identificam cuvintele aaaa  si aaaa dar nu si pe aaaa.

Conform solutiei oficiale, trebuie identificat si cuvantul aaaa dar nu am reusit sa gasesc un exemplu in care are vreo importanta faptul ca algoritmul meu rateaza cuvantul asta.

Voi ce ziceti? Imi puteti arata unde am gresit?

Dacă ai cartea baaaac și cuvintele ba, aa respectiv ac răspunsul este 0. Dar singura soluție care îți permite să obții este 0 este cea în care detectezi potrivirea din mijloc.

Ai luat 100 cu greșeala asta?