Paznici3

[•savim]

Aici se pot pune întrebări legate de problema Paznici3 de la Runda 3 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

[•stardust]

Cum se facea problema asta ?

[•S7012MY]

bst[0/1][nod] costul de a acoperi subarborele lui nod fara/cu nodul nod .
Pentru fiecare nod o sa te intereseze paznicii care pazesc o pereche de noduri cu lca-ul in nod.

[•razvan.popa]

Daca vrei sa calculezei Bst[1][nod], nod fiind lca-ul unei perechi din cele M, nu trebuie sa separi nodurile de pe lant de celelalte?
Cum se face asta in timp logaritmic?

[•PlayLikeNeverB4]

bst[0/1][nod] costul de a acoperi subarborele lui nod fara/cu nodul nod .
Pentru fiecare nod o sa te intereseze paznicii care pazesc o pereche de noduri cu lca-ul in nod.

M-am gandit si eu la asta, dar nu stiu daca merge. In exemplu, daca esti in nodul 1 si iei (3, 7) de unde stii ca nodurile 4 si 6 nu sunt acoperite?

Edit: Sau ce a zis Razvan mai sus

[•visanr]

O solutie cu complexitate teoretica O(N * M) (parcurge lanturile in O(N)), dar care are fast kill, obtine 100 pct, timp maxim 770 ms.  

[•PlayLikeNeverB4]

Se intampla ceva ciudat. Primesc "Wall time limit exceeded.". Cred ca timpii afisati de evaluator nu sunt corecti.

Edit: Ori e ceva dubios la sursa mea ori au ceva testele.