088 Gard2

[•domino]

Aici puteţi discuta despre problema Gard2.

[•filipb]

La problema asta, imi da TLE pe 5 teste... Exista un algoritm mai destept sau pur si simplu merge in timp si recurenta normala [ in O(N^3 * MAX), unde MAX este numarul de cifre ale rezultatului ] implementata ordonat? Sau poate trebuie sa implementam operatiile pe numere mari intr-o baza mai mare de 10? 

   P.S: In sursa mea, tabelul cu combinarile e preprocesat inainte de a inepe recurentele...

[•domino]

La problema asta, imi da TLE pe 5 teste... Exista un algoritm mai destept sau pur si simplu merge in timp si recurenta normala [ in O(N^3 * MAX), unde MAX este numarul de cifre ale rezultatului ] implementata ordonat? Sau poate trebuie sa implementam operatiile pe numere mari intr-o baza mai mare de 10?  

   P.S: In sursa mea, tabelul cu combinarile e preprocesat inainte de a inepe recurentele...

                       bubbleSORT

Solutie e O(N^2*K*NrMari) , incearca sa optimizezi.

[•MarcvsHdr]

Dap, solutia e O(N^2*K*Lmax). In problema asta, K==N, deci e si O(N^3*Lmax). Ma rog, nu asta conteaza. Vroiam sa zic nu mi-a intrat in timp pe 4 teste pana nu lucrat in baza 10000 (cred ca mergea si 100, dar ma luase cu nervi). Se poate si cu baza 10? 

Constanta ascunsa in formula lui O in cazul meu era 5 (1 pt o copiere, 2 pt o inmultire si 2 pt o adunare)

[•astronomy]

Se poate si O(N*K*nr_mari)