•DITzoneC
|
|
« : Noiembrie 19, 2007, 00:11:15 » |
|
Aici puteţi discuta despre problema Puteri2.
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
|
« Răspunde #1 : Iulie 05, 2012, 10:58:36 » |
|
Am implementat operatiile pe numere mari folosind baza 10000 si am un TLE pe al doilea test. Cu baza 1000000000 am din nou TLE pe testul al doilea. Folosesc cautarea binara. Am incercat si parsarea citirii cu fread dar tot TLE. Mentionez ca folosesc classes si aceleasi operatii pe numere mari ca la problema http://infoarena.ro/problema/numere2 unde am luat 100. Trebuie cumva marita limita de timp sau mai trebuie sa fac ceva optimizari ( desi nu mai am nici o idee )?
|
|
« Ultima modificare: Iulie 05, 2012, 11:04:36 de către Pirtoaca George Sebastian »
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #2 : Iulie 05, 2012, 13:35:19 » |
|
Cel mai probabil e fiindca folosesti clase. Exista o sursa a lui Mihai Popa care intra in 11 secunde acum. Am pus limita la 15. Din pacate cred ca trebuie sa rescrii sursa fara clase, fiindca in forma asta nu intra nici intr-un minut .
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #3 : Iulie 05, 2012, 14:24:02 » |
|
Poti sa faci sa iti intre si cu clase dar tre sa scapi de operatiile in plus. In loc sa iti definesti operator + si sa faci a = b + c fa-ti mai degraba operatorul +=(care sa returneze o referinta spre obiectul curent) si operatorul + fa-l astfel inline huge operator+(const huge &that) const { huge aux(*this); // iti faci un constructor, ai 2 lini in plus de scris return (aux+= that); }
la fel si la operator-. Desi aici mai bine nici nu iti declari operatorul +/- ci mai bine faci a = b, a += c daca vrei sa obtii a = b + c. Alta optimizare ar fi sa scoti 1LL * a.v[ i] * v[j] avand in vedere ca ai baza 10000. Si daca chiar ai nevoie de long long(poate folosesti baza 1 miliard) atunci fa asa static_cast<long long>(a.v[i]) * v[j]; . Merge mai repede asa. Si ca ultima optimizare, desi e mai complicat ar fi sa folosesti baza 2^15 si sa schimbi baza la sfarsit(schimbatul bazei e O(nr_cifre^2).
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
|
« Răspunde #4 : Iulie 05, 2012, 15:04:25 » |
|
Multumesc amandurora pentru indicatii. O sa incerc sa vad ce iese.
PS : Am citit solutia oficiala pana la urma si am gasit 3 optimizari propuse : pe primele 2 le am deja, iar a treia : in cazul cautarii binare, intervalul initial de cautare nu trebuie sa fie [1,N], ci un interval mai restrans (de exemplu, [10 la (X/P)-1, 10 la (X/P)+1]), unde X este numarul de cifre ale numarului N dat. Nu imi dau seama de ce afirmatia este adevarata ( daca am baza 10000 atunci trebuie 10000 la puterile respective ) . Astfel scap de TLE dar iau incorect.
|
|
« Ultima modificare: Iulie 05, 2012, 16:34:40 de către Pirtoaca George Sebastian »
|
Memorat
|
|
|
|
•misino
Strain
Karma: 10
Deconectat
Mesaje: 40
|
|
« Răspunde #5 : Martie 27, 2013, 15:15:00 » |
|
De ce daca maresc dimensiunile vactorilor creste timpul de executie?
|
|
|
Memorat
|
|
|
|
•superman_01
Client obisnuit
Karma: 14
Deconectat
Mesaje: 52
|
|
« Răspunde #6 : Martie 27, 2013, 15:20:06 » |
|
si mie mi s-a intamplat asta la o problema.Si din cate scria acolo e vorba de timpul pe care il ia programul tau sa aloce memoria.
|
|
|
Memorat
|
|
|
|
•scipianus
|
|
« Răspunde #7 : Mai 01, 2013, 15:20:27 » |
|
Cum as putea sa aflu daca sursa mea ( http://www.infoarena.ro/job_detail/945274) e macar pe-aproape de limita de 15s? Folosesc baza 10^8,am pus la cautarea binara pe st si dr ca fiind 10^(nrcif/P-1) si 10^(nrcif/P+1) si fac si exponentierea logaritmic,verificand in timpul ei daca nu depasesc numarul de cifre al rezultatului bun,dar tot ia TLE
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #8 : Mai 01, 2013, 16:50:47 » |
|
Bagi multa informatica, ajuti lumea pe forum, te implici in activitatile infoarena, devii respectat de comunitate, devii admin, editezi limitele de timp dupa cum ai chef si observi rezultatul. Spoiler: Nu iti intra nici in 30 de secunde.
|
|
|
Memorat
|
Am zis
|
|
|
•scipianus
|
|
« Răspunde #9 : Mai 01, 2013, 16:54:30 » |
|
Ok,mersi
|
|
|
Memorat
|
|
|
|
•darkseeker
|
|
« Răspunde #10 : Mai 01, 2013, 18:29:54 » |
|
Sau putin mai simplu, ai putea genera un test mare pe calculatorul tau, iar daca lucrezi pe linux poti incerca folosind : time timeout nr_secunde ./nume_executabil Aceasta comanda o sa-ti opreasca automat rularea programului dupa nr_secunde. Ca sa vezi daca programul tau a rulat in mai putin de nr_secunde poti folosi echo $?, care afiseaza valoarea de retur a ultimei comenzi. Daca echo $? iti afiseaza 0 atunci a rulat in mai putin de nr_secunde, daca iti afiseaza 124 programul a fost oprit fortat.
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #11 : Mai 01, 2013, 18:40:32 » |
|
Bagi multa informatica, ajuti lumea pe forum, te implici in activitatile infoarena, devii respectat de comunitate, devii admin, editezi limitele de timp dupa cum ai chef si observi rezultatul. Spoiler: Nu iti intra nici in 30 de secunde. Paul, pe tine ce problema te-a adus pe calea asta? ).
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #12 : Mai 01, 2013, 19:05:36 » |
|
Secv5. Cum am devenit admin m-am uitat pe sursele de 100 sa vad care-i smenu. (De aceea am dat acces liber la surse de la mine putere.)
|
|
|
Memorat
|
Am zis
|
|
|
•cdt2013
Strain
Karma: -3
Deconectat
Mesaje: 2
|
|
« Răspunde #13 : Mai 02, 2013, 23:49:03 » |
|
Off: Nu pot sa nu observ ce interes crescut este pentru problema asta in ultimele zile
|
|
|
Memorat
|
|
|
|
•Johny_Depp22
Strain
Karma: 3
Deconectat
Mesaje: 25
|
|
« Răspunde #14 : Mai 03, 2013, 10:57:05 » |
|
Off: Nu pot sa nu observ ce interes crescut este pentru problema asta in ultimele zile Poate pentru ca s-a dat una asemanatoare si la FII 13 la runda 5...
|
|
|
Memorat
|
|
|
|
•cdt2013
Strain
Karma: -3
Deconectat
Mesaje: 2
|
|
« Răspunde #15 : Mai 06, 2013, 00:14:31 » |
|
Imi poate da cineva un test mai mare va rog. Ma dispera problema asta
|
|
|
Memorat
|
|
|
|
|