560 Abc2

[•DITzoneC]

Aici puteţi discuta despre problema Abc2.

[•Dastas]

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?

[•fireatmyself]

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

[•Dastas]

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?

[•fireatmyself]

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" ?

[•wefgef]

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

[•Dastas]

A intrat asa . Mersi!

[•fireatmyself]

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

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.

[•wefgef]

Ai bagat cu cautarea binara ai lui patrascu?

[•cos_min]

Ai bagat cu cautarea binara ai lui patrascu?

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

[•fireatmyself]

Ai bagat cu cautarea binara ai lui patrascu?

Nu. Am facut cautare binara clasica.

[•Dastas]

Mie mi-a intrat cu cautare binara clasica.

Care e "hashul cu functia lui Mircea"?

[•fireatmyself]

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.

[•nparfene2004]

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

[•sima_cotizo]

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

fgets( sir, dimensiune, stdin );   

[•c_e_manu]

Am incercat sa rezolv folosind KMP. Nu ma astept la punctaj maxim (multe TLE-uri ), 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.

[•fluture.godlike]

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?
Multumesc anticipat!