h1. USACO dec 2005, divizia GOLD
(Creat de '_domino_':user/domino la data de _2006-01-05_ categoria __, autor(i) _Daniel Pasaila, Mircea Pasoi_)
*Continut scurt:*
In acest articol veti gasi solutiile pentru problemele propuse la concursul USACO, editia din luna decembrie 2005, divizia GOLD. Testele si enunturile sunt disponibile la sectiunea Download.
==Include(page="template/raw")==
In acest articol veti gasi solutiile pentru problemele propuse la concursul USACO, editia din luna decembrie 2005, divizia GOLD. Testele si enunturile sunt disponibile la sectiunea Download.
*Continut lung:*
Cow Patterns
Solutia propusa in acest articol foloseste un algoritm de genul Rabin Karp. In aceasta problema alfabetul folosit este Sigma = {1, 2, ... S}, deci putem privi un sir de K caractere consecutive ca reprezentand un numar in baza S de lungime K. Spunem ca modelul este vectorul P[1..K] iar textul dat este T[1..N].
Fiind dat modelul P[1..K] notam cu p valoarea sa corespunzatoare in baza S. Intr-o maniera similara, fiind dat textul T[1..N], notam cu t_s valoarea in baza S a subsirului convertit T[s + 1...s + m]. In cazul in care gasim un subsir cu valoarea t_s = p atunci am gasit o potrivire a modelului pe text. Dificultatile care apar in rezolvarea problemei tin de convertirea sirului T in timp real, dupa conditiile impuse de enuntul problemei. Astfel, ne deplasam cu un sablon de lungime K spre dreapta. Pentru fiecare deplasament trebuie sa modificam valoarea t_s corespunzator. La deplasarea cu o pozitie apar urmatoarele cazuri:
1. din sablon iese o valoare unica sau intra o valoare care nu exista in deplasamentul curent.
2. din sablon iese o valoare care va exista si in deplasamentul urmator, si intra o valoare care exista deja in deplasamentul curent
Vom rezolva cazul 1 in O(K), convertind subsirul curent dupa regulile din enunt. Observam ca in cazul 2 dupa efectuarea deplasamentului sablonul va contine aceleasi cifre. Aceasta operatie este deci doar o deplasare, deci o putem efectua in O(1) exact ca la Rabin Karp.
Desi complexitatea algoritmului pare ca este O(N * K), la o analiza mai atenta ne dam seama ca ea este de fapt O(N * S). Sa incercam sa calculam de cate ori poate aparea cazul 1 in deplasare. Trebuie sa observam ca un element odata intrat in sablon mai poate genera cazul 1 abia dupa K elemente, deci numarul total in cel mai defavorabil caz este N/K * S. Complexitatea algoritmului devine acum O(K * N/K * S + N) deci O(N * S).
La implementare, toate operatiile se fac modulo Q (unde Q este un numar prim destul de mare). Acum poate vi se pare ca de fiecare data cand t_s = p ar trebui sa comparam in O(K) cele doua subsiruri, complexitatea totala crescand. O analiza probabilistica ne arata ca pentru Q prim si destul de mare sansele ca doua subsiruri diferite de lungime K sa fie echivalente modulo Q sunt foarte mici, deci o solutie care compara doar modulele numerelor va lua punctajul maxim fara probleme.
Barn expansion
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 se rezolva similar si pentru segmentele orizontale. Complexitatea algoritmului este O(N logN).
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.
==Include(page="template/raw")==
Cow Patterns
Solutia propusa in acest articol foloseste un algoritm de genul Rabin Karp. In aceasta problema alfabetul folosit este Sigma = {1, 2, ... S}, deci putem privi un sir de K caractere consecutive ca reprezentand un numar in baza S de lungime K. Spunem ca modelul este vectorul P[1..K] iar textul dat este T[1..N].
Fiind dat modelul P[1..K] notam cu p valoarea sa corespunzatoare in baza S. Intr-o maniera similara, fiind dat textul T[1..N], notam cu t_s valoarea in baza S a subsirului convertit T[s + 1...s + m]. In cazul in care gasim un subsir cu valoarea t_s = p atunci am gasit o potrivire a modelului pe text. Dificultatile care apar in rezolvarea problemei tin de convertirea sirului T in timp real, dupa conditiile impuse de enuntul problemei. Astfel, ne deplasam cu un sablon de lungime K spre dreapta. Pentru fiecare deplasament trebuie sa modificam valoarea t_s corespunzator. La deplasarea cu o pozitie apar urmatoarele cazuri:
1. din sablon iese o valoare unica sau intra o valoare care nu exista in deplasamentul curent.
2. din sablon iese o valoare care va exista si in deplasamentul urmator, si intra o valoare care exista deja in deplasamentul curent
Vom rezolva cazul 1 in O(K), convertind subsirul curent dupa regulile din enunt. Observam ca in cazul 2 dupa efectuarea deplasamentului sablonul va contine aceleasi cifre. Aceasta operatie este deci doar o deplasare, deci o putem efectua in O(1) exact ca la Rabin Karp.
Desi complexitatea algoritmului pare ca este O(N * K), la o analiza mai atenta ne dam seama ca ea este de fapt O(N * S). Sa incercam sa calculam de cate ori poate aparea cazul 1 in deplasare. Trebuie sa observam ca un element odata intrat in sablon mai poate genera cazul 1 abia dupa K elemente, deci numarul total in cel mai defavorabil caz este N/K * S. Complexitatea algoritmului devine acum O(K * N/K * S + N) deci O(N * S).
La implementare, toate operatiile se fac modulo Q (unde Q este un numar prim destul de mare). Acum poate vi se pare ca de fiecare data cand t_s = p ar trebui sa comparam in O(K) cele doua subsiruri, complexitatea totala crescand. O analiza probabilistica ne arata ca pentru Q prim si destul de mare sansele ca doua subsiruri diferite de lungime K sa fie echivalente modulo Q sunt foarte mici, deci o solutie care compara doar modulele numerelor va lua punctajul maxim fara probleme.
Barn expansion
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 se rezolva similar si pentru segmentele orizontale. Complexitatea algoritmului este O(N logN).
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.
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")==
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. Cow Patterns
Solutia propusa in acest articol foloseste un algoritm de genul Rabin Karp. In aceasta problema alfabetul folosit este {$Sigma = {1, 2, ... S}$}, deci putem privi un sir de $K$ caractere consecutive ca reprezentand un numar in baza $S$ de lungime {$K$}. Spunem ca modelul este vectorul $P[1..K]$ iar textul dat este {$T[1..N]$}.
Fiind dat modelul $P[1..K]$ notam cu $p$ valoarea sa corespunzatoare in baza {$S$}. Intr-o maniera similara, fiind dat textul {$T[1..N]$}, notam cu $t{~s~}$ valoarea in baza $S$ a subsirului convertit {$T[s + 1...s + m]$}. In cazul in care gasim un subsir cu valoarea $t{~s~} = p$ atunci am gasit o potrivire a modelului pe text. Dificultatile care apar in rezolvarea problemei tin de convertirea sirului $T$ in timp real, dupa conditiile impuse de enuntul problemei. Astfel, ne deplasam cu un sablon de lungime $K$ spre dreapta. Pentru fiecare deplasament trebuie sa modificam valoarea $t{~s~}$ corespunzator. La deplasarea cu o pozitie apar urmatoarele cazuri:
# din sablon iese o valoare unica sau intra o valoare care nu exista in deplasamentul curent.
# din sablon iese o valoare care va exista si in deplasamentul urmator, si intra o valoare care exista deja in deplasamentul curent
Vom rezolva cazul $1$ in {$O(K)$}, convertind subsirul curent dupa regulile din enunt. Observam ca in cazul $2$ dupa efectuarea deplasamentului sablonul va contine aceleasi cifre. Aceasta operatie este deci doar o deplasare, deci o putem efectua in $O(1)$ exact ca la Rabin Karp.
Desi complexitatea algoritmului pare ca este {$O(N * K)$}, la o analiza mai atenta ne dam seama ca ea este de fapt {$O(N * S)$}. Sa incercam sa calculam de cate ori poate aparea cazul $1$ in deplasare. Trebuie sa observam ca un element odata intrat in sablon mai poate genera cazul $1$ abia dupa $K$ elemente, deci numarul total in cel mai defavorabil caz este {$N/K * S$}. Complexitatea algoritmului devine acum $O(K * N/K * S + N)$ deci {$O(N * S)$}.
La implementare, toate operatiile se fac modulo $Q$ (unde $Q$ este un numar prim destul de mare). Acum poate vi se pare ca de fiecare data cand $t{~s~} = p$ ar trebui sa comparam in $O(K)$ cele doua subsiruri, complexitatea totala crescand. O analiza probabilistica ne arata ca pentru $Q$ prim si destul de mare sansele ca doua subsiruri diferite de lungime $K$ sa fie echivalente modulo $Q$ sunt foarte mici, deci o solutie care compara doar modulele numerelor va lua punctajul maxim fara probleme.
h2. Barn expansion
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 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.
