infoarena > infoarena - concursuri, probleme, evaluator, articole > Arhiva de probleme > Subiect: 088 Gard2
Pagini: [1]   În jos
« mesajul precedent următorul mesaj »
  Imprimă  
Ajutor Subiect: 088 Gard2  (Citit de 2013 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« : August 30, 2005, 12:47:35 »
Aici puteţi discuta despre problema Gard2.
Memorat
•filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #1 : 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?  Think

   P.S: In sursa mea, tabelul cu combinarile e preprocesat inainte de a inepe recurentele...
« Ultima modificare: Martie 25, 2007, 20:08:45 de către Filip Cristian Buruiana » Memorat
•domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #2 : 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?  Think

   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.
Memorat
•MarcvsHdr
Strain
*

Karma: 1
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #3 : 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?  Think

Constanta ascunsa in formula lui O in cazul meu era 5 (1 pt o copiere, 2 pt o inmultire si 2 pt o adunare)
Memorat
•astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #4 : Martie 25, 2007, 20:07:06 »
Se poate si O(N*K*nr_mari)
Memorat
Pagini: [1]   În sus
  Imprimă  
infoarena > infoarena - concursuri, probleme, evaluator, articole > Arhiva de probleme > Subiect: 088 Gard2
 « mesajul precedent următorul mesaj »
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines