USACO dec 2005, divizia GOLD

(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 problemelor sunt disponibile in sectiunea Download.

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 ts valoarea in baza S a subsirului convertit T[s + 1...s + m]. In cazul in care gasim un subsir cu valoarea ts = 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 ts 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 ts = 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 ymini, ymaxi si xi coordonatele lui. Pentru un i daca xi != xi-1 sau ymini > ls initializam ls cu ymaxi. Altfel marcam segmentul i si segmentul cu care am obtinut maximul ls ca fiind rele, iar ls devine MAX (ls, ymaxi).

Problema se rezolva similar si pentru segmentele orizontale. Complexitatea algoritmului este O(N logN).

Layout

Vom nota pozitiile celor N vaci cu x1, x2 ... xN si vom transforma fiecare relatie care se da intr-o constrangere de forma xi - xj ≤ C. Cum se impune din enunt ca x1 ≤ x2 ≤ ... ≤ xN, vom introduce initial constrangeri de forma xi - xi+1 ≤ 0 (i < N). Apoi, pentru fiecare perechi de vaci i < j care trebuie sa fie la distanta maxim D, vom introduce constrangerea xj - xi ≤ D, iar pentru fiecare pereche i < j care trebuie sa fie la distanta de minim D, vom introduce constrangerea xi - xj ≤ -D. Trebuie acum sa rezolvam acest sistem de constrangeri.

Motivul pentru toate constrangerile sunt de forma xi - xj ≤ C , este pentru a modela aceasta problema folosind teoria grafurilor. Vom considera vacile ca fiind noduri de la 1 la N, iar fiecare constrangere xi - xj ≤ 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 Di ≤ Dj + C, echivalenta cu Di - Dj ≤ 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.