882 Propozitie2

[•wefgef]

Aici puteti discuta despre problema Propozitie2.

[•poptibi]

Cred ca limita de timp la aceasta problema este cam mica. Am complexitate O(N * C * 26), aceasta fiind si complexitatea din solutia oficiala.  
Initial, am incercat o solutie cu complexitate mai mica, folosind niste codificari, dar si solutia aceasta lua TLE.

[•scipianus]

La fel zic si eu ca e cam mica limita,asta desi exista punctaje de 100. Totusi cu O(N*C*26) nu cred ca se mai poate lua 100 acum. http://www.infoarena.ro/job_detail/954894

[•poptibi]

Cu valori modulo mai mari + hash de mana + O(N * 100) am reusit sa iau 100 de puncte, desi e cam jeg pentru ca a durat ceva pana sa aleg combinatia potrivita.  

LE: merge si fara bulaneli in O(N * 100).

Poate sa-mi explice si mie cineva de ce secventa de cod (Hash este un map<vector<int>, int>):

Cod:

Hash[Y] ++;

foloseste > 32 mb (iau MLE), pe cand secventa:

Cod:

if(!Hash.count(Y)) Hash.insert(pair<vector<int>, int >(Y, 1));
else Hash[Y] ++;

foloseste < 1 mb de memorie?

[•pauldb]

Nu stiu exact de ce se intampla asa sau macar ce cere problema, dar ar trebui sa ai in vedere ca operatiile principale pe un map au complexitate logaritmica. Daca vrei complexitate medie constanta ar trebui sa folosesti unordered_map.

[•poptibi]

Nu stiu exact de ce se intampla asa sau macar ce cere problema, dar ar trebui sa ai in vedere ca operatiile principale pe un map au complexitate logaritmica. Daca vrei complexitate medie constanta ar trebui sa folosesti unordered_map.

Ok, multumesc!

Imi cer scuze in legatura cu memoria, folosesc > 32 mb daca fac X += Hash[Y], dar folosesc < 1 mb daca fac X += (Hash.count(Y) ? Hash[Y] : 0).  

[•pauldb]

Pentru ca map-ul salveaza valoarea 0 pentru cheia Y daca o astfel de cheie nu exista deja.

[•poptibi]

Pentru ca map-ul salveaza valoarea 0 pentru cheia Y daca o astfel de cheie nu exista deja.

Multumesc!