* $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":downloads?arbori_de_interval.zip scris pe tema aceasta din sectiunea "Download":downloads.

h2. Skiarea