h2. Obstacle

Si aceasta problema se rezolva tot programare dinamica. Asadar avem BST(i, 0) = distanta minima parcursa pentru a ajunge la capatul din stanga al gardului numarul i si BST(i, 1) = distanta minima parcursa pentru a ajunge la capatul din dreapta al gardului numarul i. De asemenea notam cu Cap(i, 0) = pozitia capatului din stanga al gardului i in sistemul de coordonte si Cap(i, 1) = analog pentru capatul din dreapta. Avem urmatoarele recurenta:

Si aceasta problema se rezolva tot programare dinamica. Asadar avem $BST{~i, 0~}$ = distanta minima parcursa pentru a ajunge la capatul din stanga al gardului numarul $i$ si $BST{~i, 1~}$ = distanta minima parcursa pentru a ajunge la capatul din dreapta al gardului numarul {$i$}. De asemenea notam cu $Cap{~i, 0~}$ = pozitia capatului din stanga al gardului $i$ in sistemul de coordonte si $Cap{~i, 1~}$ = analog pentru capatul din dreapta. Avem urmatoarele recurenta:

* 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.

* $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 [2]articolului scris pe tema aceasta din sectiunea "Download".

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