576 Puteri2

[•DITzoneC]

Aici puteţi discuta despre problema Puteri2.

[•SebiSebi]

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

[•klamathix]

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 .

[•freak93]

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

Cod:

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

Cod:

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).

[•SebiSebi]

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.

[•misino]

De ce daca maresc dimensiunile vactorilor creste timpul de executie?

[•superman_01]

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.

[•scipianus]

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 

[•pauldb]

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.

[•scipianus]

Ok,mersi 

[•darkseeker]

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.

[•klamathix]

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?).

[•pauldb]

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.)

[•cdt2013]

Off: Nu pot sa nu observ ce interes crescut este pentru problema asta in ultimele zile 

[•Johny_Depp22]

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...

[•cdt2013]

Imi poate da cineva un test mai mare va rog. Ma dispera problema asta