1337 Kdist

[•dushmi]

Aici puteti discuta despre problema Kdist.

Multumiri lui Robert Simoiu pentru adaugarea ei.

[•tzipleatud]

Salut!

Am citit solutia oficiala la aceasta problema, si din cadrul acesteia am scos o observatie de care nu imi dau seama de ce e mereu corecta.
Pentru cei care nu au chef sa citeasca problema si solutia, voi face un rezumat: "Se da un arbore, in care anumite noduri sunt colorate in negru. Trebuie sa se determine setul format din nodurile care reprezinta LCA-urile oricarei perechi de noduri colorate in negru."
Din solutia oficiala a acestei probleme, rezulta ca trebuie facuta sortarea in ordinea parcurgerii DF a nodurilor colorate in negru.
(Functia DF arata cam asa):

Cod:

void DF (int nod) {
if (culoare[nod]==negru) V.push_back(nod);
...
parcurgere_DF_fii;
...
}

Apoi, este de ajuns sa se insereze intr-un set LCA-urile nodurilor negre aflate pe pozitii consecutive in vectorul V. Conform solutiei oficiale, acest set reprezinta set-ul cautat (cel format din nodurile care reprezinta LCA-urile oricarei perechi de noduri colorate in negru din arbore).

Raman recunoscator daca ar putea sa imi explice cineva de ce aceasta tehnica este corecta, iar in caz contrar, sa imi atraga atentia asupra faptului ca poate am interpretat gresit solutia oficiala.

Multumesc anticipat!

[•Steve]

Din cate inteleg intrebarea ta este: Setul de noduri pe care il aleg asa acopera toate LCA-urile nodurilor negre?
Raspunsul este da, hai sa vedem de ce.
Numim setul de LCA-uri ce trebuie gasit S
Fie un nod x care face parte din S (unul din alea care trebuie gasit). Trebuie sa demonstram ca algoritmul tau in gaseste pe x. x se afla in S, deci exista 2 noduri negre in subarbori diferiti ai lui x, pe care ii notam A1, A2. Daca A1 si A2 sunt subarbori consecutivi (nu exista un nod negru in V intre nodurile negre din A1 si nodurile negre din A2), atunci e evident ca va exista in V un nod negru din A1 langa un nod negru din A2. Daca A1 si A2 nu sunt subarbori consecutivi (exista cel putin un nod negru in V intre nodurile negre din A1 si nodurile negre din A2) atunci in V vom avea o secventa de forma (...nA1, nA1, nA1, a, b, c,...., p, nA2, nA2...)
unde nA1 = un nod negru din A1, nA2 = un nod negru din A2, a, b, c, d,...p noduri negre random, consecutive din subarbori ai lui x, care se afla intre A1 si A2. Cand faci LCA (ultimul nA1, a) o sa-l gasesti pe x. Ambele cazuri sunt satisfacute, deci x va fi gasit de algoritmul tau, no matter what.
Sper ca ai inteles dem, daca ai vreo nelamurire/am ratat ceva, da un PM sau scrie aici

[•tzipleatud]

Misto demonstratia! Am inteles, multumesc mult! 

[•Bodo171]

Am descoperit ca formatul testelor e precizat gresit.Se spune ca valorile c sunt pe linii diferite,dar,de fapt sunt pe aceesi linie.