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.
Dupa cum au aratat-o si rezultatele, aceasta problema a fost cea mai simpla din concurs. Trebuie sa determinam numarul de dreptunghiuri a caror laturi nu intalnsesc laturile altor dreptunghiuri. De asemenea, sa nu uitam ca dreptunghiurile nu se pot suprapune. In aceste conditii observam ca daca doua dreptunghiuri se intersecteaza atunci se vor intersecta si $2$ segmente verticale sau $2$ segmente orizontale. Putem astfel sa luam mai intai toate segmentele verticale, vedem care dintre acestea se intersecteaza cu altele si marcam dreptunghiurile lor ca fiind rele. Repetam algoritmul si pentru segmentele orizontale, iar la sfarsit numaram cate dreptunghiuri bune ne-au ramas.
Problema pe care trebuie sa o rezolvam acum este urmatoarea: avand $K$ segmente paralele cu axa Oy trebuie sa determinam care dintre acestea se intersecteaza cu altele. Pentru aceasta sortam segmentele in primul rand dupa coordonata $x$ si in al 2-lea rand dupa coordonata $y$ minima. Dupa aceasta sortare putem determina in $O(K)$ segmentele care se intersecteaza. Parcurgem vectorul de la stanga la dreapta, si pentru fiecare pas vedem daca segmentul curent se intersecteaza cu un segment precedent. Pentru aceasta trebuie sa tinem o variabila ls care reprezinta coordonata $y$ maxima atinsa pana la un moment dat. Pentru segmentul $i$ fie {$ymin{~i~}$}, $ymax{~i~}$ si $x{~i~}$ coordonatele lui. Pentru un $i$ daca $x{~i~} != x{~i-1~}$ sau $ymin{~i~} > ls$ initializam $ls$ cu {$ymax{~i~}$}. Altfel marcam segmentul $i$ si segmentul cu care am obtinut maximul $ls$ ca fiind rele, iar $ls$ devine {$MAX(ls, ymax{~i~})$}.
Problema pe care trebuie sa o rezolvam acum este urmatoarea: avand $K$ segmente paralele cu axa Oy trebuie sa determinam care dintre acestea se intersecteaza cu altele. Pentru aceasta sortam segmentele in primul rand dupa coordonata $x$ si in al 2-lea rand dupa coordonata $y$ minima. Dupa aceasta sortare putem determina in $O(K)$ segmentele care se intersecteaza. Parcurgem vectorul de la stanga la dreapta, si pentru fiecare pas vedem daca segmentul curent se intersecteaza cu un segment precedent. Pentru aceasta trebuie sa tinem o variabila ls care reprezinta coordonata $y$ maxima atinsa pana la un moment dat. Pentru segmentul $i$ fie {$ymin{~i~}$}, $ymax{~i~}$ si $x{~i~}$ coordonatele lui. Pentru un $i$ daca $x{~i~} != x{~i-1~}$ sau $ymin{~i~} > ls$ initializam $ls$ cu {$ymax{~i~}$}. Altfel marcam segmentul $i$ si segmentul cu care am obtinut maximul $ls$ ca fiind rele, iar $ls$ devine {$MAX (ls, ymax{~i~})$}.
Problema se rezolva similar si pentru segmentele orizontale. Complexitatea algoritmului este {$O(N logN)$}.
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.
