h1. USACO dec 2005, divizia GOLD

(Creat de ==user(user="domino" type="tiny")== la data de _2006-01-05_ categoria __, autor(i) _Daniel Pasaila, Mircea Pasoi_)
 
 ==Include(page="template/raw")==

(Categoria _Concursuri_, autor(i) _Daniel Pasaila, Mircea Pasoi_)

In acest articol veti gasi solutiile pentru problemele propuse la concursul USACO, editia din luna decembrie 2005, divizia GOLD. "Teste si enunturile":http://www.infoarena.ro/downloads?action=download&file=usaco.zip problemelor sunt disponibile in sectiunea Download.

h2. Layout
Vom nota pozitiile celor $N$ vaci cu $x{~1~}, x{~2~} ... x{~N~}$ si vom transforma fiecare relatie care se da intr-o constrangere de forma {$x{~i~} - x{~j~} &le; C$}. Cum se impune din enunt ca {$x{~1~} &le; x{~2~} &le; ... &le; x{~N~}$}, vom introduce initial constrangeri de forma {$x{~i~} - x{~i+1~} &le; 0$} ({$i < N$}). Apoi, pentru fiecare perechi de vaci $i < j$ care trebuie sa fie la distanta maxim {$D$}, vom introduce constrangerea {$x{~j~} - x{~i~} &le; D$}, iar pentru fiecare pereche $i < j$ care trebuie sa fie la distanta de minim {$D$}, vom introduce constrangerea {$x{~i~} - x{~j~} &le; -D$}. Trebuie acum sa rezolvam acest sistem de constrangeri.

Motivul pentru toate constrangerile sunt de forma {$x{~i~} - x{~j~} ≤ C$} , este pentru a modela aceasta problema folosind teoria grafurilor. Vom considera vacile ca fiind noduri de la $1$ la {$N$}, iar fiecare constrangere {$x{~i~} - x{~j~} ≤ C$} va reprezenta o muchia de la $j$ la $i$ cu costul {$C$}. In acest graf vom determina distantele minime de la $1$ la fiecare nod intr-un vector {$D$}. Din definitia distantelor minime in grafuri , pentru o muchie ({$j, i$}) de cost $C$ se respecta relatia {$D{~i~} ≤ D{~j~} + C$}, echivalenta cu {$D{~i~} - D{~j~} ≤ C$}. Asadar vectorul $D$ va respecta fiecare constrangere formulata anterior pentru vectorul {$x$}.

Fiindca graful este rar ({$MD+ML+N-1$} muchii), se va folosi algoritmul Bellman-Ford pentru determinarea distantelor mimine, avand complexitatea O({$N*(MD+ML+N)$}). Modul in care lucreaza algoritmul Bellman-Ford asigura ca distanta dintre vaca $1$ si vaca $N$ este maximizata.
Cazul cand vacile puteau fi asezate oricat de departe se putea detecta verificand daca distanta pana la vaca $N$ este infinit. De asemenea, cazul cand problema nu avea solutie putea fi detectat tot cu Bellman Ford, verificand daca exista un ciclu de cost negative accesibil din nodul {$1$}. Demonstratia ca atunci cand graful contine un ciclu negativ nu exista solutie o lasam pe seama cititorului.

Fiindca graful este rar ({$MD+ML+N-1$} muchii), se va folosi algoritmul Bellman-Ford pentru determinarea distantelor mimine, avand complexitatea O({$N*(MD+ML+N)$}). Modul in care lucreaza algoritmul Bellman-Ford asigura ca distanta dintre vaca $1$ si vaca $N$ este maximizata. Cazul cand vacile puteau fi asezate oricat de departe se putea detecta verificand daca distanta pana la vaca $N$ este infinit. De asemenea, cazul cand problema nu avea solutie putea fi detectat tot cu Bellman Ford, verificand daca exista un ciclu de cost negative accesibil din nodul {$1$}. Demonstratia ca atunci cand graful contine un ciclu negativ nu exista solutie o lasam pe seama cititorului.