|
Titlul: 108 Sediu Scris de: Mircea Pasoi din Septembrie 06, 2005, 09:09:57 Aici puteţi discuta despre problema Sediu (http://infoarena.ro/problema/sediu).
Titlul: Raspuns: 108 Sediu Scris de: Prigoana Alexandru din 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 ?
Titlul: Raspuns: 108 Sediu Scris de: u-92 din Aprilie 05, 2006, 14:20:43 depinde, daca ai declarat mai mult de 63mb da :)
Titlul: Raspuns: 108 Sediu Scris de: Prigoana Alexandru din Aprilie 05, 2006, 14:32:25 am matrice de 16000 pe 16000. ii prea mult ?
Titlul: Re: 108 Sediu Scris de: Valentin Stanciu din 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... Titlul: Raspuns: 108 Sediu Scris de: ditzone din 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... Titlul: Raspuns: 108 Sediu Scris de: Prigoana Alexandru din 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 ?
Titlul: Raspuns: 108 Sediu Scris de: u-92 din 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)
Titlul: Raspuns: 108 Sediu Scris de: Prigoana Alexandru din Aprilie 05, 2006, 14:59:08 ok . mersi ... citesc :D
Titlul: Raspuns: 108 Sediu Scris de: Bondane Cosmin din 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
Titlul: Raspuns: 108 Sediu Scris de: Bogdan-Alexandru Stoica din 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...)
Titlul: Raspuns: 108 Sediu Scris de: ditzone din Octombrie 08, 2006, 11:08:51 Vezi ca atunci cand exista mai multe sedii trebuie afisate pe aceeasi linie nu pe linii separate.
Titlul: Raspuns: 108 Sediu Scris de: Bondane Cosmin din Octombrie 08, 2006, 12:44:20 100 8) . Codul meu era bun, dar nu afisam pe aceiasi linie :oops: . ms ditzone
Titlul: Raspuns: 108 Sediu Scris de: Tabara Mihai din Octombrie 22, 2006, 22:04:24 Imi da si mie cineva un hint la problema va rog.... :oops:
Titlul: Raspuns: 108 Sediu Scris de: u-92 din Octombrie 23, 2006, 14:43:26 este explicatia pe situl campion
Titlul: Răspuns: 108 Sediu Scris de: Ion Ureche din 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..
Titlul: Răspuns: 108 Sediu Scris de: Salajan Razvan din 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; Titlul: Răspuns: 108 Sediu Scris de: Ion Ureche din Iulie 19, 2012, 16:26:02 Multumesc mult pentru explicatie, chiar e frumoasa problema. E mai usor decat credeam. :)
|