|
Titlul: 057 Diametrul unui arbore Scris de: Teodor Plop din Ianuarie 28, 2014, 18:25:13 Aici puteti discuta despre problema Diametrului unui arbore (http://infoarena.ro/problema/darb).
Titlul: Răspuns: 057 Diametrul unui arbore Scris de: Cosmin Rusu din Ianuarie 28, 2014, 19:21:24 In primul rand, felicitari tuturor celor implicati in extinderea arhivei educationale :) , iar in al doilea rand cred ca ati uitat sa puneti acces liber si la teste.
Numai bine! Titlul: Răspuns: 057 Diametrul unui arbore Scris de: Panaete Adrian din Februarie 12, 2014, 14:52:21 O solutie tot in O(N) ar fi sa se inceapa o parcurgere BF plecand din frunze cu scaderea gradului odata cu eliminarea unei muchii si introducerea in coada a unui nod numai cand ajunge frunza (ideea e oarecum similara cu cea de la sortarea topologica). In felul asta solutia este suma distantelor pana la ultimele doua noduri parcurse ( distanta este calculata bineinteles din nod pana la cea mai indepartata frunza ). O implementare pe aceasta idee :
http://www.infoarena.ro/job_detail/1106081?action=view-source (http://www.infoarena.ro/job_detail/1106081?action=view-source) Titlul: Răspuns: 057 Diametrul unui arbore Scris de: Sorin Olimpicu din Mai 06, 2015, 08:32:43 Am 2 obiectii
1. Sursa mea de Java care implementeaza tot 2 BFS nu intra in timp. 2. In enunt nu scrie clar, ca radacina este mereu 1. In implementare se vede in schimb ca autorul presupune asta pentru teste. Se vede ca cineva care nu cunoaste o oarecare conventie nu are cum sa stie ca radacina este mereu 1. In mod normal as mai fi pierdut vreme ca sa o determin. Titlul: Răspuns: 057 Diametrul unui arbore Scris de: George Marcus din Mai 06, 2015, 17:31:01 1. Am reusit maxim 90. Nu cred ca intra in Java solutia asta. Ar merge marita putin limita.
2. E arbore fara radacina. Nu conteaza din ce nod pornesti cu primul bfs. Titlul: Răspuns: 057 Diametrul unui arbore Scris de: Alexandru Pana din Iunie 15, 2015, 09:04:00 Salut,
Uitandu-ma peste solutia recomandata de 100pct, am observat urmatorul lucru: Cod: #define MAX_N 1000001 1. al 3-lea argument al lui memset primeste un numar de bytes nu de elemente. In acest caz sizeof(int) * MAX_N ar fi fost corect. Altfel se intializeaza doar o parte din vector. 2. MAX_N e de 10 ori mai mare decat dimensiunea maxima a inputului, ceea ce inseamna ca desi memset-ul primeste argumentul gresit, totusi initializeaza o bucata suficient de mare din array incat sa functioneze pentru problema asta, sizeof(int) fiind cel mai probabil 4. |