Pagini: 1 2 3 [4]   În jos
  Imprimă  
Ajutor Subiect: 010 Stramosi  (Citit de 22576 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #75 : Aprilie 15, 2009, 19:59:35 »

nu intzeleg o chestie dc 2^k trb <=n  dak avem totzi stramoshtii (1->2->3->4->5->6) unde primul stramos e 2 iar al 5-ilea 6 iar 2^5>6
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #76 : Aprilie 15, 2009, 22:19:05 »

pai ai A[ k ] [ i ] - cel de-al 2^k-lea stramos a lui i. Daca 2^k > n, atunci cel de-al 2^k-lea stramos a lui i nu exista [ pt ca i are maxim n stramosi ]  Smile
Memorat
mathboy
Moderatori infoarena
Nu mai tace
*****

Karma: 150
Deconectat Deconectat

Mesaje: 259



Vezi Profilul
« Răspunde #77 : Februarie 05, 2010, 14:49:18 »

Fac un df recursiv si am o complexitate de O (N + M). Cu toate acestea primesc KBS 11 pe ultimul test. Am modificat limitele pana la 400 000  si am ajuns sa folosesc 40MB din memorie dar degeaba. Daca ar putea sa ma ajute cineva i-as ramane recunoscator. Multumesc.
Aici e sursa : http://infoarena.ro/job_detail/391337?action=view-source.
« Ultima modificare: Februarie 05, 2010, 18:10:35 de către Rotaru Dragos Alin » Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #78 : Februarie 06, 2010, 07:24:18 »

Poate e din cauza recursivitatii. Incearca sa scrii DFS-ul iterativ.
Memorat

Am zis Mr. Green
mathboy
Moderatori infoarena
Nu mai tace
*****

Karma: 150
Deconectat Deconectat

Mesaje: 259



Vezi Profilul
« Răspunde #79 : Februarie 06, 2010, 13:47:33 »

Am luat suta in sfarsit. Din cauza df-ului recursiv era KBS-ul ala. Multumesc inca o data . Smile
Memorat
mihaionly
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 10



Vezi Profilul
« Răspunde #80 : Februarie 12, 2010, 11:24:11 »

Obțin "Killed by signal 11(SIGSEGV)." oricât de mare mi-aș fi declarat vectorul, iar algoritmul respectă la fix ideea matricii A[log(n)][n].  Read This!
E a noua oară când uploadez sursa cu modificări minore care am crezut eu că pot fi cauza iar răspunsul e tot același.. signal 11
http://infoarena.ro/job_detail/395149?action=view-source
Memorat
tinky
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #81 : Aprilie 11, 2011, 11:44:37 »

a luat cineva 100p cu un program de complexitate n+m*p?
Pentru fiecare query caut stramosul cu ceva de genul x = tata [ x ]; (pentru asta am luat 80 p cu TLE pe ultimele 2)
Am incercat si sa imi 'preprocesez' al p-lea stramos pentru fiecare om si am luat memory limited exceeded pe ultimele 4 teste
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #82 : Iulie 05, 2011, 10:08:41 »

Poate cineva sa-mi explice de ce la intrbarea 5 din exemplu raspunsul e 8 dar nu 10?
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #83 : Iulie 05, 2011, 11:46:31 »

Al 3-lea stramos al lui 13 este 8. Mergand in sus pe arbore primul e 12, al doilea e 10.
Memorat
retrograd
Client obisnuit
**

Karma: 3
Deconectat Deconectat

Mesaje: 50



Vezi Profilul
« Răspunde #84 : Februarie 12, 2015, 21:59:09 »

Complexitatea oficiala este O(m+n)? Eu asa am facut-o, chiar fara multa bataie de cap(ca implementare)
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.212



Vezi Profilul
« Răspunde #85 : Februarie 12, 2015, 22:29:41 »

Sunt 2 soluții, cea pe care o ai tu în O(n + m) și una în O(n log n + m log n) care are avantajul că poate răspunde online la query-uri, nu are nevoie să le știe pe toate de la început. Ambele idei și implementări sunt utile  Smile
Memorat
vlad082002
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #86 : Septembrie 01, 2019, 22:53:53 »

Ok am rezolvat problema cu stramosii de ordin 2^k ai fiecarui nod dar nu inteleg de ce ruleaza mai repede daca inversez indicii din matrice, imi poate explica cineva?
Memorat
Pagini: 1 2 3 [4]   În sus
  Imprimă  
 
Schimbă forumul:  

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