|
Titlul: 989 Pirati Scris de: Stefan-Alexandru Filip din Martie 21, 2010, 15:30:04 Aici puteţi discuta despre problema Pirati (http://infoarena.ro/problema/pirati).
Titlul: Răspuns: 989 Pirati Scris de: Otilia Stretcu din Martie 23, 2010, 00:05:51 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.
Titlul: Răspuns: 989 Pirati Scris de: Andrei Grigorean din Martie 23, 2010, 00:33:50 De ce nu folosesti STL?
Pe cele mai nasoale teste numarul de zone conexe este aproximativ N * M / 4. Titlul: Răspuns: 989 Pirati Scris de: Otilia Stretcu din Martie 23, 2010, 11:40:59 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. |