Diferente pentru usaco-dec-2005-divizia-gold intre reviziile #5 si #9
Nu exista diferente intre titluri.
Diferente intre continut:
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] <= C. Cum se impune din enunt ca x[1] <= x[2] <= ... <= x[N], vom introduce initial constrangeri de forma x[i] - x[i+1] <= 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] <= D, iar pentru fiecare pereche i < j care trebuie sa fie la distanta de minim D, vom introduce constrangerea x[i] - x[j] <= -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.
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~} ≤ C$}. Cum se impune din enunt ca {$x{~1~} ≤ x{~2~} ≤ ... ≤ x{~N~}$}, vom introduce initial constrangeri de forma {$x{~i~} - x{~i+1~} ≤ 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~} ≤ D$}, iar pentru fiecare pereche $i < j$ care trebuie sa fie la distanta de minim {$D$}, vom introduce constrangerea {$x{~i~} - x{~j~} ≤ -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.
