h3. Cerere

Problema este de dificultate medie. O rezolvare $O(N*lg(N))$ este usor de gasit, fiind asemanatoare cu una deja exista in arhiva, "Stramosi":http://www.infoarena.ro/task/stramosi. Dar o astfel de rezolvare n-ar fi adus punctaj maxim in mod normal. Problema se poate rezolva printr-o simpla parcurgere in adancime din radacina implementand manual stiva DF-ului. Cand vom pune un nod $n$ pe pozitia $p$ in stiva, al {$K$}-lea stramos va fi nodul de pe pozitia $p-K$ din stiva, pentru care s-a procesat deja valoarea ceruta. Complexitatea finala a algoritmului va fi {$O(N)$}.

Problema este de dificultate medie. O rezolvare $O(N*lg(N))$ este usor de gasit, fiind asemanatoare cu una deja exista in arhiva, "Stramosi":http://infoarena.ro/problema/stramosi. Dar o astfel de rezolvare n-ar fi adus punctaj maxim in mod normal. Problema se poate rezolva printr-o simpla parcurgere in adancime din radacina implementand manual stiva DF-ului. Cand vom pune un nod $n$ pe pozitia $p$ in stiva, al {$K$}-lea stramos va fi nodul de pe pozitia $p-K$ din stiva, pentru care s-a procesat deja valoarea ceruta. Complexitatea finala a algoritmului va fi {$O(N)$}.

h3. Rubarba