|
Titlul: 882 Propozitie2 Scris de: Andrei Grigorean din Mai 03, 2009, 19:10:49 Aici puteti discuta despre problema Propozitie2 (http://infoarena.ro/problema/propozitie2).
Titlul: Răspuns: 882 Propozitie2 Scris de: Pop Tiberiu din Mai 31, 2013, 17:01:23 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. Titlul: Răspuns: 882 Propozitie2 Scris de: FMI Ciprian Olariu din Mai 31, 2013, 17:13:41 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 (http://www.infoarena.ro/job_detail/954894)
Titlul: Răspuns: 882 Propozitie2 Scris de: Pop Tiberiu din Mai 31, 2013, 23:26:47 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)); foloseste < 1 mb de memorie? Titlul: Răspuns: 882 Propozitie2 Scris de: Paul-Dan Baltescu din Iunie 01, 2013, 02:34:49 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.
Titlul: Răspuns: 882 Propozitie2 Scris de: Pop Tiberiu din Iunie 01, 2013, 06:54:21 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). :oops: Titlul: Răspuns: 882 Propozitie2 Scris de: Paul-Dan Baltescu din Iunie 01, 2013, 22:50:07 Pentru ca map-ul salveaza valoarea 0 pentru cheia Y daca o astfel de cheie nu exista deja.
Titlul: Răspuns: 882 Propozitie2 Scris de: Pop Tiberiu din Iunie 01, 2013, 22:59:42 Pentru ca map-ul salveaza valoarea 0 pentru cheia Y daca o astfel de cheie nu exista deja. Multumesc! :thumbup: |