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:

# Vladu Adrian 783 puncte
# Stancu-Mara Sorin 782 puncte
# Andrei-Marius Teodorescu 710 puncte
# Fechete Dan Ionut 490 puncte
# Pasaila Daniel 436 puncte
# Paul Diac 406 puncte

table. |_. 1 | Vladu Adrian | 783 puncte|
|_. 2 | Stancu-Mara Sorin | 782 puncte |
|_. 3 | Andrei-Marius Teodorescu | 710 puncte |
|_. 4 | Fechete Dan Ionut | 490 puncte |
|_. 5 | Pasaila Daniel | 436 puncte |
|_. 6 | Paul Diac | 406 puncte |

Restul concurentilor au avut punctaje sub $400$ de puncte. Primii doi din clasamentul "nostru" au reusit sa se strecoare intre primele $20$ de locuri din clasamentul final dar, din nou, remarc lipsa unui roman in topul celor mai buni. Sper mai multe de la concursurile viitore! Mai vreau sa precizez ca Romania nu a dispus de tot arsenalul avut in dotare si concurenti cu rezultate in competiile internationale anterioare precum Dan Crestez si Dan Spatarel nu au fost prezenti in concurs (cel putin nu cu numele lor!). Ei sunt rugati sa participe in viitoarele concursuri (sau sa renunte la pseudonime - daca e cazul), spre binele lor si spre prestigiul Romaniei!

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