•domino
|
|
« : Septembrie 06, 2005, 09:09:57 » |
|
Aici puteţi discuta despre problema Sediu.
|
|
|
Memorat
|
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #1 : Aprilie 05, 2006, 14:17:56 » |
|
Programul imi trece de compilare si totusi iau 0 puncte cu mesajul RUN ERROR - SIGKILL la toate testele. Am declarat oare o matricea prea mare ?
|
|
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
u-92
Vizitator
|
|
« Răspunde #2 : Aprilie 05, 2006, 14:20:43 » |
|
depinde, daca ai declarat mai mult de 63mb da
|
|
|
Memorat
|
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #3 : Aprilie 05, 2006, 14:32:25 » |
|
am matrice de 16000 pe 16000. ii prea mult ?
|
|
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
•svalentin
|
|
« Răspunde #4 : Aprilie 05, 2006, 14:35:57 » |
|
cred ca este prea mult .. calculeaza singur insa cata memorie folosesti: 16000*16000*dimensiunea_tipului daca este int (sau integer), inmultesti cu 4, daca este long long (sau int64), inmulteste cu 8.. asa vezi exact cat ocupa oricum, 16000*16000 = 256.000.000, care deja depaseste 64.000.000...
|
|
|
Memorat
|
|
|
|
ditzone
Vizitator
|
|
« Răspunde #5 : Aprilie 05, 2006, 14:37:59 » |
|
Pai e aproape 1Giga de memorie ceea ce inseamna foarte mult... Incearca sa retii arborele prin lista de fii nu matrice de adiacenta...
|
|
|
Memorat
|
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #6 : Aprilie 05, 2006, 14:44:55 » |
|
da ok ... nici nu ma gandeam sa retin arborele cu matrice de adiacenta ... nus batut in cap. Da pentru a construi lista de fii trebuie sa folosesc atuncia O(n^2) care nu intra in timp. nu ? in sensu ca reiau muchiile si caut un varf anume intre printre ele. nu ?
|
|
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
u-92
Vizitator
|
|
« Răspunde #7 : Aprilie 05, 2006, 14:48:22 » |
|
nu, citeste din cormen. Ideea e ca atunci cand aloci dinamic folosesti exact atata memorie cat iti trebuie. Tii pt fiecare nod o lista cu vecinii sai. Complexitatea la parcurgere o sa fie O(N+M)
|
|
|
Memorat
|
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #8 : Aprilie 05, 2006, 14:59:08 » |
|
ok . mersi ... citesc
|
|
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
•cos_min
|
|
« Răspunde #9 : Octombrie 03, 2006, 16:00:28 » |
|
sunt ceva cazuri speciale la testele 4 si 10 ? Pe restul testelor iau OK, iar pe cele 2 iau WA
|
|
|
Memorat
|
vid...
|
|
|
•fireatmyself
|
|
« Răspunde #10 : Octombrie 07, 2006, 19:13:41 » |
|
nu par sa aiba nimic iesit din comun. ai testat cum se comporta programul tau si pentru arbori mai speciali? (gen toate nodurile au exact un fiu, sau exact doi...)
|
|
|
Memorat
|
Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
|
|
|
ditzone
Vizitator
|
|
« Răspunde #11 : Octombrie 08, 2006, 11:08:51 » |
|
Vezi ca atunci cand exista mai multe sedii trebuie afisate pe aceeasi linie nu pe linii separate.
|
|
|
Memorat
|
|
|
|
•cos_min
|
|
« Răspunde #12 : Octombrie 08, 2006, 12:44:20 » |
|
100 . Codul meu era bun, dar nu afisam pe aceiasi linie . ms ditzone
|
|
|
Memorat
|
vid...
|
|
|
Tabara Mihai
Vizitator
|
|
« Răspunde #13 : Octombrie 22, 2006, 22:04:24 » |
|
Imi da si mie cineva un hint la problema va rog....
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #14 : Octombrie 23, 2006, 14:43:26 » |
|
este explicatia pe situl campion
|
|
|
Memorat
|
|
|
|
•ion824
Strain
Karma: 11
Deconectat
Mesaje: 17
|
|
« Răspunde #15 : Iulie 19, 2012, 13:49:59 » |
|
Imi poate da cineva un hint ,cam cum ar arata dinamica pe arbore ? nu prea am facut probleme de asa gen..
|
|
|
Memorat
|
|
|
|
•vendetta
|
|
« Răspunde #16 : Iulie 19, 2012, 14:59:46 » |
|
Presupun ca ai facut solutia in n^2... Pt o(n) idea e sa faci o singura parcurgere df si sa reti cateva informatii despre fiecare nod. Iti alegi un nod(o radacina) si apoi faci un df din acel nod; In arborele df ti pentru fiecare nod cate noduri are in subarbore(fie vectorul a[]) si adancimea maxima de la nodul actual pana la o frunza(fie vectorul b[]). Raspunsul va fi minimul din b[]; doar ca dupa ce faci df-ul trebuie sa actualizezi anumite valori din b[] pentru ca tu in Df ai calculat adancimea maxima de la nod in jos dar poate fi si varianta sa fie in sus; si tot ce ramane de facut e sa actulizezi b[nod] = max(b[nod], n-a[nod]); avand n noduri si tu stiind ca in subarborele cu radacina nod ai a[nod] noduri atunci inseamna ca celalalt drum care exista si nu l-ai luat in considerare in parcurgerea Df va avea n-a[nod] noduri;
|
|
|
Memorat
|
|
|
|
•ion824
Strain
Karma: 11
Deconectat
Mesaje: 17
|
|
« Răspunde #17 : Iulie 19, 2012, 16:26:02 » |
|
Multumesc mult pentru explicatie, chiar e frumoasa problema. E mai usor decat credeam.
|
|
|
Memorat
|
|
|
|
|