h1. USACO nov 2005, divizia GOLD

(Categoria _Competitii_, autor(i) _Adrian Diaconu_)

(Creat de ==user(user="DITzoneC" type="tiny")== la data de _2005-11-21_ categoria _Competitii_, autor(i) _Adrian Diaconu_)

Etapa din noiembria a fost una destul de usoara cu $17$ punctaje maxime printre care si $3$ romani:

"Teste si enunturile":http://www.infoarena.ro/downloads?action=download&file=usaco_nov05.zip problemelor sunt disponibile in sectiunea Download.

==Include(page="template/raw")==
 

h2. Asteroids
Vom rezolva aceasta problema folosind un algoritm de cuplaj maxim. Se va construi un graf bipartit in care vom avea pe o parte coloanele matricii ({$1..n$}) pe cealalta liniile matricii ({$1..m$}). Vom avea muchie de la o linie la o coloana daca in pozitia respectiva se afla un bolovan ce trebuie distrus. Graful astfel construit va avea $n+m$ noduri si $k$ muchii (locurile unde sunt plasati bolovanii). Problema se reduce astfel la determinarea unui suport minim pe un graf bipartit care este echivalenta cu gasirea cuplajului maxim pe acest graf. Suportul minim inseamna o multime de noduri de cardinal minim astfel incat fiecare muchie are cel putin un capat in multime.

h2. Walk the Talk

Vom rezolva independent problema pentru fiecare cuvant aflat in dictionar. Vom nota $a{~i,j~}$ matricea cu litere, iar s{~i~} cuvantul pe care il analizam la un anumit moment, acesta avand lungimea {$L$}. Vom construi matricea $sum{~i,j,k~}$ in care se va retine numarul de moduri in care se obtine secventa $s{~1~}, s{~2~}, ... , s{~k~}$ folosind doar dreptungiul cu colturile in ({$1,1$}) si ({$i,j$}) din matricea de litere. Pentru a calcula configuratia ({$i,j,k$}) se numara intai cate se obtin pentru secventa $1..k$ pentru dreptunghiul respectiv fara a considera casuta $(i,j)$ ({$sum{~i-1,j,k~}+sum{~i,j-1,k~}-sum{~i-1,j-1,k~}$}) apoi daca avem $a{~i,j~}=s{~k~}$ adunam cate solutii avem pentru secventa $1..k-1$ pentru dreptunghiul respectiv mai putin casuta $(i,j)$ ({$sum{~i-1,j,k-1~}+sum{~i,j-1,k-1~}-sum{~i-1,j-1,k-1~}$}). In final solutia se va afla in {$sum{~n,m,L~}$}. Complexitatea construirii fiecare configuratii in parte este $O(1)$ deci in total va fi {$O(n*m*L)$}. Memoria necesara este {$O(n*m*L)$}, dar aceasta se poate reduce la $O(n*m)$ daca luam in considerare faptul ca la fiecare moment ne este necesar doar numarul de solutii pentru o secventa cu $1$ mai mica.

Vom rezolva independent problema pentru fiecare cuvant aflat in dictionar. Vom nota a[i][j] matricea cu litere, iar s[i] cuvantul pe care il analizam la un anumit moment, acesta avand lungimea L. Vom construi matricea sum[i][j][k] in care se va retine numarul de moduri in care se obtine secventa s[1], s[2], ... , s[k] folosind doar dreptungiul cu colturile in (1,1) si (i,j) din matricea de litere. Pentru a calcula configuratia (i,j,k) se numara intai cate se obtin pentru secventa 1..k pentru dreptunghiul respectiv fara a considera casuta [i][j] (sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]) apoi daca avem a[i][j]=s[k] adunam cate solutii avem pentru secventa 1..k-1 pentru dreptunghiul respectiv mai putin casuta [i][j] (sum[i-1][j][k-1]+sum[i][j-1][k-1]-sum[i-1][j-1][k-1] ). In final solutia se va afla in sum[n][m][L]. Complexitatea construirii fiecare configuratii in parte este O(1) deci in total va fi O(n*m*L). Memoria necesara este O(n*m*L), dar aceasta se poate reduce la O(n*m) daca luam in
considerare faptul ca la fiecare moment ne este necesar doar numarul de solutii pentru o secventa cu 1 mai mica.