|
Titlul: 457 Maimute Scris de: Filip Cristian Buruiana din Mai 22, 2007, 14:15:01 Aici puteţi discuta despre problema Maimute (http://infoarena.ro/problema/maimute).
Titlul: Răspuns: 457 Maimute Scris de: Puni Andrei Paul din Mai 22, 2007, 16:44:05 Citat Pe urmatoarele N-1 linii se vor afla cate 2 numere X si Y reprezentand faptul ca intre maimuta X si Y exista o relatie directa nu cred ca am inteles bine, relatia aia este X este tatal lui Y sau Y este tatal lui X ?Titlul: Răspuns: 457 Maimute Scris de: Savin Tiberiu din Mai 22, 2007, 17:05:40 poate fi ori una ori cealalta, nu are importanta.
Titlul: Răspuns: 457 Maimute Scris de: Andrei Misarca din Aprilie 14, 2008, 19:23:33 Daca de exemplu intre 1 si 2, si 1 si 3 exista o relatie de rudenie, se poate ca si intre 2 si 3 sa existe o relatie de rudenie?
Titlul: Răspuns: 457 Maimute Scris de: Savin Tiberiu din Aprilie 14, 2008, 20:07:22 Citat arborele genealogic al familiei acestora Deci nu. Titlul: Răspuns: 457 Maimute Scris de: Andrei Misarca din Aprilie 14, 2008, 20:12:00 Mersi :D
Titlul: Răspuns: 457 Maimute Scris de: vladiana micu din Iunie 15, 2008, 19:28:27 Am facut un LCA cu arbore de intervale.....prima data rulez un df si stabilesc adancimile si una dintre pozitile pe care apare fiecare nod. Apoi fac un update pe arbore iar apoi fiecare interogare in O(log N)......stie cineva cumva dc iau 4 TLE si ma poate ajuta? compl finala ar fii: O(2*n + log n * (m + n))
Titlul: Răspuns: 457 Maimute Scris de: Bondane Cosmin din Iunie 15, 2008, 19:49:19 Se poate face o singura parcurgere, dupa care sa raspunzi in O(1) pt fiecare intrebare.
Titlul: Răspuns: 457 Maimute Scris de: vladiana micu din Iunie 15, 2008, 20:05:10 si in parcurgere ce aflu si cum rasp in O(1) ?
Titlul: Răspuns: 457 Maimute Scris de: Marius Stroe din Iunie 15, 2008, 21:16:22 Nu stiu problema, dar iti pot spune ca poti raspunde la LCA in O(1) cu hashuri cu o preprocesare in O(N log*N) cu multimi disjuncte.
Titlul: Răspuns: 457 Maimute Scris de: Savin Tiberiu din Iunie 15, 2008, 21:19:08 Exista o solutie mai simpla. Complexitatea oficiala e O(N+M). Gandestete daca nu te poate ajuta intrun fel acea parcurgere euler.
Titlul: Răspuns: 457 Maimute Scris de: vladiana micu din Iunie 15, 2008, 21:33:25 nu prea imi vine in cap decat daca unul dintre cele 2 noduri se afla intre 2 aparitii ale celuilalt nod in parcurgerea euler :D
Titlul: Răspuns: 457 Maimute Scris de: Paul-Dan Baltescu din Iunie 15, 2008, 22:08:04 Exact. Si pentru ce iti trebuie LCA atunci? :)
Titlul: Răspuns: 457 Maimute Scris de: Alexandru-Iancu Caragicu din Aprilie 07, 2010, 13:31:13 O maimuta poate avea mai multi parinti?
Titlul: Răspuns: 457 Maimute Scris de: Paul-Dan Baltescu din Aprilie 07, 2010, 18:37:23 Nu.
Titlul: Răspuns: 457 Maimute Scris de: Adrian Craciun din Noiembrie 10, 2011, 11:02:12 cred ca ar trebui marit un pic timpul de executie
http://infoarena.ro/job_detail/631524 (http://infoarena.ro/job_detail/631524) |