989 Pirati

[•Prostu]

Aici puteţi discuta despre problema Pirati.

[•otilia_s]

Am citit solutia oficiala, dar nu reusesc sa imi dau seama cam de cata memorie am nevoie pentru a calcula LCA. Stiu ca DeÅŸi arborele poate avea O(N ^ 2) noduri, adâncimea sa este de ordinul O(N).  Dar care este numarul maxim de zone conexe? Cu siguranta mai mic decat N*M.

[•wefgef]

De ce nu folosesti STL?

Pe cele mai nasoale teste numarul de zone conexe este aproximativ N * M / 4.

[•otilia_s]

Multumesc! 
Ma gandisem sa calculez LCA folosind matricea stramosilor de ordin 2^k. La STL nu am reusit sa inteleg cum pot afla memoria ocupata de o matrice. Stiu ca pentru un vector de n elemente se aloca cea mai mica puterea a lui 2, mai mare ca n. Dar chiar daca asta teoretic se incadra in memoria disponibila, la mai multe probleme mi s-a intamplat sa iau MLE.
De aceea vroiam sa aloc static si aveam nevoie de nr maxim de zone. Dar presupun ca e prea mare ca sa mearga pe metoda asta.