infoarena

Aici puteţi discuta despre problema APDM (http://infoarena.ro/problema/apdm).

Poate cineva sa dea un hint la problema asta.

cauta pe algoritmus. are si solutie oficiala. :thumbup:

Vrei sa imi spui adresa, te rog ?  :)

http://algoritmus.org/index.php

Algoritmus nu mai exista :( sau cel putin linkul nu mai merge...

• Am incercat sa fac dupa postul lui Cho de aici : http://online-judge.uva.es/board/viewtopic.php?p=36766&highlight=%2336766
  Asta ca sa determin nodul din "mijloc" al celui mai lung drum. Gaseam astfel drumul minim si afisam (max+1)/2... Asa iau 20p.
• Apoi am incercat sa fac BFS din nodul ala de mijloc ca sa vad distantele max pana la varfuri, sa sortez distantele si sa le adun pe cele mai mari 2 distante... iar iau 20p, pe alte teste de data asta :)
• Am incercat si sa adun cele mai mari 2 distante diferite si de data asta iau iarasi 20p...

Stiu ca toate cele 3 metode nu sunt in totalitate corecte, dar as vrea sa stiu si eu daca ideea de baza, comuna, e gresita? ... si eventual care e continuarea  :?

http://citeseer.ist.psu.edu/cache/papers/cs/701/http:zSzzSzwww.math.tau.ac.ilzSz~hassinzSztree.pdf/hassin97minimum.pdf

la aceasta problema procedez cam asa. parcurg in latime graful pentru fiecare nod si aleg la final cele mai indepartate 2 noduri fata de nodul din care am inceput sa fac parcurgerea. apoi adun aceste distante si astfel aflu diametrul. Primesc 30 de puncte si incorect pe restul testelor. e gresita ideea de rezolvare sau am eroare pe undeva prin program? va multumesc.

Bogdan, am impresia ca nu ai inteles problema.
Tie nu'ti trebuie distanta dintre cele mai departate doua noduri din graf (si daca ti'ar trebui, nu asta e rezolvarea), ci iti trebuie un arbore partial (un arbore care contine toate nodurile grafului) pentru care distanta intre cele mai departate 2 noduri sa fie cat mai mica.

L.E. : Pe exemplul din problema, daca faci parcurgere in latime din nodul 1, o sa ai d(1,8) = 3 si d(1,3) = 2, deci ar trebui sa'ti dea 5.. raspunsul e 4.

Are ceva special testul 16?

Un hint cine a trecut de testul 16...?

Ce e asa special la testele 9, 10 si 11? Iau incorect pe ele, si nu stiu de ce...