infoarena

Aici puteţi discuta despre problema Abc2 (http://infoarena.ro/problema/abc2).

Nu reusesc nicicum sa iau testele 8 si 9. Restul intra in sub o secunda, la astea primesc TLE. Folosesc 2 hashuri. Imi dati va rog o sugestie?

parseaza citirea. eu asa am facut ca sa intre in timp.

Cum adica sa parsez citirea, aici? Citesc cu fgets sirul initial si apoi fiecare cuvant in parte tot cu fgets. Daca trimit doar citirea cel mai mare timp e 0.6 pe testul 8. Se poate mai rapid?

ma refeream sa citesti intr-un buffer cu gets tot inputul si apoi sa citesti caracter cu caracter din buffer, dar cred ca e acelasi lucru ca si cum ai face fu gets (mie nu imi intra ca foloseam scanf...). eu am facut alt smen ca sa intre in timp. tu ce parte a inputului "hashuesti" ?

Poti sa scrii cuvintele in baza 3, sortezi sirul care iti rezulta si apoi cauti binar.

A intrat asa :). Mersi!

mie nu mi-a intrat asa... eu fac hash pe dictionar, si pentru un cuvant atribui doua valori : hashul cu functia lui Mircea (aia pe care nu o tineai tu minte) si reprezentarea cuvantului in baza 3. daca am o coliziune cresc prima valoare pana cand dau peste un numar nefolosit sau pana cand dau peste un numar folosit, dar care retine cuvinte cu aceeasi reprezentare in baza 3.

Ai bagat cu cautarea binara ai lui patrascu?

Mie mi-a mers fara cautarea binara lui patrascu, folosind o constanta mai mica pentru hash.

Nu. Am facut cautare binara clasica.

Mie mi-a intrat cu cautare binara clasica.

Care e "hashul cu functia lui Mircea"?

alegi un numar prim foarte mare (p) si functia hash pentru un numar x este (x*P)>>(32-nrb), unde nrb este numarul de biti semnificativi pe care trebuie sa-i pastrezi.

Obtin corect la 6 teste din 10, restul sunt TLE. Imi da si averismentul asta:

Compilare: /tmp/ccai038i.o: In function `main': user.cpp:(.text+0xb6): warning: the `gets' function is dangerous and should not be used.

Poate sa-mi zica cineva ce e asta? As vrea sa stiu ce pot folosi in loc de gets

fgets( sir, dimensiune, stdin );   :thumbup:

Am incercat sa rezolv folosind KMP. Nu ma astept la punctaj maxim (multe TLE-uri :P ), dar ce e gresit in rezolvarea asta:

-citesc pe rand fiecare cuvant si fac KMP pentru el;
-retin intr-un vector fiecare pozitie candidata;
-sortez vectorul cu pozitii canditate si numar cate elemente diferite am in el;
-afisez.

Salut, m-am uitat pe niste surse mai vechi cu cautare binara si numere in baza 3 si observ ca timpul de executie este cu mult peste limita(presupun ca limita a scazut intre timp). Stie cineva daca in noile limite intra cumva solutia cu cautare binara?:D
Multumesc anticipat!