h1. USACO decembrie 2004, divizia GOLD - idei de solutii

(Creat de ==user(user="silviug" type="tiny")== la data de _2004-12-18_ categoria _Competitii_, autor(i) _Silviu Ganceanu_)

(Categoria _Competitii_, autor(i) _Silviu Ganceanu_)

"Setul de probleme":http://info.devnet.ro/download.php?page=cat&cat=30 pe marginea caruia voi discuta in urmatoarele randuri se afla disponibil in sectiunea download impreuna cu datele de test si rezultatele finale ale concursului (cei care nu stiu setul de probleme si vor sa citeasca articolul sunt rugati sa parcurga mai intai textele problemelor).

"Setul de probleme":downloads?gold_dec04.zip pe marginea caruia voi discuta in urmatoarele randuri se afla disponibil in sectiunea download impreuna cu datele de test si rezultatele finale ale concursului (cei care nu stiu setul de probleme si vor sa citeasca articolul sunt rugati sa parcurga mai intai textele problemelor).

Voi incepe prin cateva observatii in legatura cu evolutia concurentilor din Romania in acest concurs. Asadar un clasament (neoficial) alcatuit intre acestia ar arata in urmatorul mod:

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

h2. Skiarea