111 Asmax

[•domino]

Aici puteţi discuta despre problema Asmax.

[•Stilgar]

nu intelg ...ori is singuru prost care nu pricepe cum poate fi rez problema ori is printre putinii la care le pasa de ea,oricum nu prea vad cum scap de 0(n^2).
pls help

[VladS]

Merge si in O(n) cu un DF modificat.

[•Cosmin]

DF-modificat ... mai mult o programare dinamica, poti oricand sa pui bfs acolo sau ce parcurgere vrei tu atata timp cat fii unui nod sunt procesati inainte de tata lor.

[•Stilgar]

10x pt expl dar dupa ce m-am chiorat uimit la ele 5 min am inteles de ce nu pricepeam nimic..... io ma gandeam la xor max nu la asmax.... asa ca scuze pt deranj  

[•cristy]

ma...eu am gandit in felul urmator...am tinut un vector de tati...si un vector care tineam minte numarul de muchii adiacente cu nodul respectiv...procesam tot timpul nodurile care erau frunze, si daca retinea un numar >0 atunci il adunam tatalui sau si decrementam numarul de muchii adiacente la taica-su cu o unitate, in caz contrar, scadeam o unitate de la tata fara sa fac nimic altceva...inainte sa scad o muchie de la tatal sau, ii verificam valoarea, o comparam cu un maxim...si tot reiau ciclu asta...si iau 50 de pct...cu ciclu infinit...pe restu testelor...ce am gresit?..sau...dati-mi va rog un contraexemplu, de ce nu ar merge?

[Tabara Mihai]

Hm....si eu am facut un DF in care pur si simplu cand iese din recursie adaug suma maxima daca e mai mare ca 0

Cod:

if(best[p->vf] > 0) best[nod] += best[p->vf];

P.S.am retinut vecinii in liste de adiacenta.....cu toate astea iau 90........si am folosit long int.....

Asadar are cineva o idee?

[•cos_min]

exista si cazul in care suma ii negativa ... deci trateaza si cazu asta (cred k asta ii  )

[•tm_radu]

Cred ca e tratat cazul asta....daca initializeaza best[nod] cu valoarea atasata acestuia, n-are rost sa mai adauge o suma negativa calculata din fii lui

[Tabara Mihai]

exista si cazul in care suma ii negativa ... deci trateaza si cazu asta (cred k asta ii  )

Iep...asta era ( )......eu intializam maximul cu 0.......mersi mult!

[•megabyte]

ce are asa special testul 5???
 Am initializat max cu -16 777 216 , am pus totul long long ,  cand ies din apel la DFS adaug numai sumele pozitive la suma actuala,
imi merge si pentru teste negative si tot iau WA pe testul 5. pls help

[•pauldb]

Exemplul nu corespunde descrierii datelor de intrare. Apare un 4 acolo care nu ar trebui sa existe.

ce are asa special testul 5??? 
 Am initializat max cu -16 777 216 , am pus totul long long ,  cand ies din apel la DFS adaug numai sumele pozitive la suma actuala,
imi merge si pentru teste negative si tot iau WA pe testul 5. pls help

Cat iti da pe testul asta?
4
-10 4 1 2
1 2
1 3
3 4

Rezultatul e evident 4.

[•megabyte]

4 imi da, si am incercat si alte teste de ex pt

Cod:

6
-5 1 -1 -1 4 -1
2 1
2 3
3 4
3 6
6 5

imi da 5 si pt :

Cod:

6
-5 -3 -2 -128 -41 -2
2 1
2 3
3 4
3 6
6 5

imi da -2

[•cos_min]

pt primul test : 4
pt al doilea test : -2

[•megabyte]

ahh, scuze, am pus rezultatul de la alt test

Cod:

6
-5 3 -1 -1 4 -1
2 1
2 3
3 4
3 6
6 5

deci la asta imi da 5, ideea era ca sa fie rezultatul suma de la mai multe nivele (subarborele 2,3,6,5), si o calculeaza bine.Pentru primul test imi da si mie 4( costul nodului 5).
 Prima data am presupus ca radacina este prima extremitate a primei muchii,  dupaia am cautat nodul care nu are tata si tot iau WA pe testul 5.Probabil aici gresec, nu stiu de unde sa pornesc DFS sau ca memorez arborele ca si graf orientat. 

[•cos_min]

pai ii graf neorientat 

Nu conteaza ce nod alegi ca si sursa, ia de exemplu nodul 1.

[•megabyte]

 asta era, si totusi nu-mi vine sa cred ca am luat 90 pct cu greseala aia
mersi

[•Iceman_ftg]

deci, pe cuvant daca reusesc sa gasesc  vre-un exemplu care sa se comporte ca testul 5
(la ex din forum merge bine);

memorez in vectorul v valorile initiale ale nodurilor
dupa care fac o lista de fii pentru fiecare nod
dupa care fac o programare dinaminca
  daca suma fiilor e mai mare decat 0
   suma nodului = v[nod] +suma fiiloor
daca  suma fiilor e mai mica <0
 suma nodului = v[nod] (deci suma poate fi negativa)

asa mi se pare logic.
la ce teste am incercat eu merge bine , si obtin si sume negative
daca se poate dati-mi un test care sa se comporte ca si testul 5 ca poate ma prind de greseala.( daca nu nu)
merci anticipat.

[•devilkind]

daca ai un un nod care are 2 fii, unul pozitiv si unul negativ iti merge??
spre exemplu ai urmatorul test:

Cod:

3
1 -2 1
1 2
1 3

Raspunsul ar trebui sa fie 2. Din ce am inteles eu de la tine iti da 1.

[•fireatmyself]

  daca suma fiilor e mai mare decat 0
   suma nodului = v[nod] +suma fiiloor

nu e bine cu suma fiilor.

[•Iceman_ftg]

m-am exprimat gresit
defapt suma fiilor e suma fiilor cu valori pozitive
sau
0 daca toti fiii au valori negative

si da imi da doi la testul respectiv devilkind

[•DITzoneC]

Cod:

4
1 1 1 1
1 2
1 3
4 3

Raspunsul e 4. Ai grija ca muchiile nu se dau sub forma (i,j) i parinte al lui j, ci pur si simplu intre i si j exista muchie. Nu este un arbore cu radacina fixa.

[•Iceman_ftg]

Ai grija ca muchiile nu se dau sub forma (i,j) i parinte al lui j, ci pur si simplu intre i si j exista muchie. Nu este un arbore cu radacina fixa.

ahaa, ca idiotul aici am gresit
testul explica totul , arigatoh.

[•breahnadavid]

Îmi spune și mie cnv. unde greșesc . !?!?!?! 

http://www.infoarena.ro/job_detail/1200524?action=view-source
Vă rog mult !!