|
Titlul: 088 Gard2 Scris de: Mircea Pasoi din August 30, 2005, 12:47:35 Aici puteţi discuta despre problema Gard2 (http://infoarena.ro/problema/gard2).
Titlul: 088 Gard2 Scris de: Filip Cristian Buruiana din August 30, 2005, 14:56:29 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? :-k
P.S: In sursa mea, tabelul cu combinarile e preprocesat inainte de a inepe recurentele... Titlul: 088 Gard2 Scris de: Mircea Pasoi din August 30, 2005, 15:00:56 Citat din mesajul lui: 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? :-k 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. Titlul: Răspuns: 088 Gard2 Scris de: Mihai Leonte din Martie 25, 2007, 19:47:08 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? :-k
Constanta ascunsa in formula lui O in cazul meu era 5 (1 pt o copiere, 2 pt o inmultire si 2 pt o adunare) Titlul: Răspuns: 088 Gard2 Scris de: Airinei Adrian din Martie 25, 2007, 20:07:06 Se poate si O(N*K*nr_mari)
|