Printr-o implementare directa a recurentei de mai sus obtinem o solutie care foloseste $O(L)$ memorie si $O(L * B)$ operatii (cu observatia ca spatiul de memorie se poate reduce la {$O(B)$}).

Pentru a reduce complexitatea la $O(L)$ operatii se utilizeaza o coada care pastreaza valorile $BST{~x~}$ cu $x$ in intervalul [{$i - 2*B, i - 2*A$}] sortate crescator. Se observa cum se modifica coada cand se trece de la pozitia $i$ la pozitia $i + 2$ (practic "intra" valoarea $BST{~i + 2 - 2*A~}$ si "iese" valoarea {$BST{~i - 2*B~}$}. Nu voi intra in detalii despre modul cum lucreaza aceasta coada. Pe aceeasi idee (utilizarea acestei cozi) se rezolva si problema "secventa":http://www.infoarena.ro/task/secventa (preOJI 2004 - infoarena) si "trans":http://www.infoarena.ro/task/trans (prima proba a selectiei lotului national largit, Buzau 2004).

Pentru a reduce complexitatea la $O(L)$ operatii se utilizeaza o coada care pastreaza valorile $BST{~x~}$ cu $x$ in intervalul [{$i - 2*B, i - 2*A$}] sortate crescator. Se observa cum se modifica coada cand se trece de la pozitia $i$ la pozitia $i + 2$ (practic "intra" valoarea $BST{~i + 2 - 2*A~}$ si "iese" valoarea {$BST{~i - 2*B~}$}. Nu voi intra in detalii despre modul cum lucreaza aceasta coada. Pe aceeasi idee (utilizarea acestei cozi) se rezolva si problema "secventa":problema/secventa (preOJI 2004 - infoarena) si "trans":problema/trans (prima proba a selectiei lotului national largit, Buzau 2004).

h2. Obstacle

* $BST{~i, j~}$ = $minim(BST{~k, l~} + dst(Cap{~k, l~}, Cap{~i, j~})$ cu $k$ de la $i + 1$ la {$N$}, $l$ si $j$ fiind $0$ sau $1$ si cu proprietatea ca drumul pe Oy dintre $Cap{~k, l~} la gardul $i$ nu se interpune nici un alt gard.

Aceasta recurenta implementata direct ne da o solutie $O(N^2^)$ care, putin optimizata, ar fi putut obtine punctajul maxim. Totusi exista o solutie $O(N log N)$ care utilizeaza o structura de date numita arbori de intervale. Practic noi trebuie sa aflam pentru fiecare gard $i$ care este gardul pe care cade o bila lasata libera din capatul din stanga si din capatul din dreapta. Aceste informatii ne permit reducerea complexitatii recurentei de mai sus la $O(N)$ (nu va mai spun cum, ganditi si voi!). Pentru a afla informatiile despre care vorbeam se parcurg cele $N$ garduri de la $1$ la $N$ (in ordinea asta!) si se proiecteaza, pe rand, pe axa Ox. Practic se pastreaza axa Ox ca un interval [{$-200.000, 200.000$}] si, pentru un gard {$i$}, se egaleaza toate pozitiile din intervalul [{$Cap{~i, 0~}, Cap{~i, 1~}$}] cu {$i$}. Pentru un afla gardul pe care cade bila se interogheaza arborele pentru fiecare capat al gardului {$i$}. Explicatiile mele nu dezvaluie modul in care lucreaza acest arbore de intervale (mi-ar lua cateva zeci de randuri bune
daca as intra in detalii). Pentru cei care nu au idee cum functioneaza acest "monstru informatic" le recomand citirea "articolului":http://info.devnet.ro/download.php?page=cat&cat=24 scris pe tema aceasta din sectiunea "Download":http://www.infoarena.ro/Downloads.

Aceasta recurenta implementata direct ne da o solutie $O(N^2^)$ care, putin optimizata, ar fi putut obtine punctajul maxim. Totusi exista o solutie $O(N log N)$ care utilizeaza o structura de date numita arbori de intervale. Practic noi trebuie sa aflam pentru fiecare gard $i$ care este gardul pe care cade o bila lasata libera din capatul din stanga si din capatul din dreapta. Aceste informatii ne permit reducerea complexitatii recurentei de mai sus la $O(N)$ (nu va mai spun cum, ganditi si voi!). Pentru a afla informatiile despre care vorbeam se parcurg cele $N$ garduri de la $1$ la $N$ (in ordinea asta!) si se proiecteaza, pe rand, pe axa Ox. Practic se pastreaza axa Ox ca un interval [{$-200.000, 200.000$}] si, pentru un gard {$i$}, se egaleaza toate pozitiile din intervalul [{$Cap{~i, 0~}, Cap{~i, 1~}$}] cu {$i$}. Pentru un afla gardul pe care cade bila se interogheaza arborele pentru fiecare capat al gardului {$i$}. Explicatiile mele nu dezvaluie modul in care lucreaza acest arbore de intervale (mi-ar lua cateva zeci de randuri bune daca as intra in detalii). Pentru cei care nu au idee cum functioneaza acest "monstru informatic" le recomand citirea "articolului":http://info.devnet.ro/download.php?page=cat&cat=24 scris pe tema aceasta din sectiunea "Download":http://www.infoarena.ro/Downloads.

h2. Skiarea