(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)

(toc){width: 30em}*{text-align:center} *Conţinut:*

(toc){width: 37em}*{text-align:center} *Conţinut:*

* 'Problema 1 (TC MagicBoxes)':probleme-de-acoperire-2#problema1
* 'Problema 2 (IOI 2001 Pavement)':probleme-de-acoperire-2#problema2
* 'Problema 3 (ACM ICPC 1997)':probleme-de-acoperire-2#problema3

În procedura $doit$ punem pe două linii consecutive piese în toate modurile posibile. Această procedură face ca pe prima linie să avem o configuraţie de pătrăţele libere $config$, iar pe a doua o configuraţie de pătrăţele ocupate $config1$. Dacă pătrăţelele reprezentate de $config$ nu au fost ocupate la pasul curent ele trebuie să fi fost ocupate la pasul anterior. Astfel, pentru fiecare pereche de configuraţii $config$ şi $config1$ trebuie să efectuăm operaţia $num[i + 1][config1] += num[i][config]$.

Dacă această rezolvare ar fi fost folosită în timpul concursului ea ar fi ieşit din timp. Pentru optimizarea ei putem face mai multe îmbunătăţiri. Un exemplu ar fi să generăm direct cele două configuraţii de biţi în procedura $backtracking$ şi să nu mai folosim şirul $sol$. O altă idee care ar fi dus la rezolvarea problemei ar fi fost calcularea tuturor rezultatelor posibile în timpul concursului şi trimiterea unei soluţii care returna aceste rezultate precalculate. Această abordare ar fi fost posibilă pentru că numărul de configuraţii iniţiale este mic.

Dacă această rezolvare ar fi fost folosită în timpul concursului, ea ar fi ieşit din timp. Pentru optimizare putem face mai multe îmbunătăţiri. Un exemplu ar fi să generăm direct cele două configuraţii de biţi în procedura $backtracking$ şi să nu mai folosim şirul $sol$. O altă idee care ar fi dus la rezolvarea problemei în timpul concursului ar fi fost calcularea tuturor rezultatelor posibile şi trimiterea unei soluţii care returna aceste rezultate precalculate. Această abordare ar fi fost posibilă pentru că numărul de configuraţii iniţiale este mic.

h2(#problema6). Problema 6 ('SGU Another chocolate maniac':http://acm.sgu.ru/problem.php?contest=0&problem=132)

bq. Se dă o tablă de dimensiuni $M x N (1 ≤ M ≤ 70, 1 ≤ N ≤ 7)$ cu unele pătrate lipsă. Se cere numărul minim de dominouri ce pot fi plasate pe tablă fară să se sprapună între ele, sau să acopere vreun pătrat ce nu aparţine tablei, astfel ca nici o altă piesă de domino să nu se poată adăuga la configuraţie fără ca aceasta să se suprapună peste una veche. Pentru tabla următoare vedem uşor în a doua figură că soluţia optimă va conţine 4 dominouri.

bq. Se dă o tablă de dimensiuni $M x N (1 ≤ M ≤ 70, 1 ≤ N ≤ 7)$ cu unele pătrate lipsă. Se cere numărul minim de dominouri ce pot fi plasate pe tablă fară să se suprapună între ele sau să acopere vreun pătrat ce nu aparţine tablei, astfel ca nici o altă piesă de domino să nu se poată adăuga la configuraţie fără ca aceasta să se suprapună peste una veche. Pentru tabla următoare vedem uşor în a doua figură că soluţia optimă va conţine 4 dominouri.

p=. !probleme-de-acoperire-2?P261.jpg!

Din nou vom folosi $metoda programării dinamice$ îmbinată cu metoda $backtracking$.

Vom umple tabla linie cu linie şi la fiecare pas putem pune dominouri orizontale pe linia curentă şi verticale pe linia curentă şi linia următoare. Trebuie să fim atenţi când trecem de la linia curentă la următoarea să nu lăsăm pe linia curentă loc liber unde poate fi amplasat un domino orizontal, pentru că acest loc nu va putea fi ocupat de piese amplasate mai târziu. Se poate lăsa spaţiu gol pe linia curentă şi linia următoare pentru că o celulă a acestei poziţii va putea fi acoperită la pasul următor. Vedem astfel că dacă linia curentă este linia $i$ atunci avem trei stări posibile pentru ultimele două pătrăţele de pe fiecare coloană: $00$ (celule neocupate), $10$ (penultima celulă ocupată şi ultima goală) $11$ (ambele celule ocupate de dominouri), starea $01$ nu poate exista. În procedura $backtracking$ care generează configuraţiile la care putem ajunge de la o configuraţie dată trebuie să mai avem grijă să nu ocupăm cu un domino o celulă ce nu aparţine tablei. Astfel, pentru a găsi soluţia problemei vom folosi un tablou $min[i][config]$ care va păstra numărul minim de dominouri care trebuie amplasate pe tablă astfel ca pe liniile $1 .. i – 1$ să nu poată fi amplasat vreun domino pe celulele rămase goale, $config$ va fi un număr întreg care atunci cănd e transformat în baza $3$ arată configuraţia liniilor $i – 1$ şi $i$.

Vom umple tabla linie cu linie şi la fiecare pas putem pune dominouri orizontale pe linia curentă şi verticale pe linia curentă şi linia următoare. Trebuie să fim atenţi când trecem de la linia curentă la următoarea să nu lăsăm pe linia curentă loc liber unde poate fi amplasat un domino orizontal, pentru că acest loc nu va putea fi ocupat de piese amplasate mai târziu. Se poate lăsa spaţiu gol pe linia curentă şi linia următoare pentru că o celulă a acestei poziţii va putea fi acoperită la pasul următor. Vedem astfel că dacă linia curentă este linia $i$ atunci avem trei stări posibile pentru ultimele două pătrăţele de pe fiecare coloană: $00$ (celule neocupate), $10$ (penultima celulă ocupată şi ultima goală), $11$ (ambele celule ocupate de dominouri). Starea $01$ nu poate exista. În procedura $backtracking$ care generează configuraţiile la care putem ajunge de la o configuraţie dată trebuie să mai avem grijă să nu ocupăm cu un domino o celulă ce nu aparţine tablei. Astfel, pentru a găsi soluţia problemei vom folosi un tablou $min[i][config]$ care va păstra numărul minim de dominouri care trebuie amplasate pe tablă astfel ca pe liniile $1, 2, ..., i - 1$ să nu poată fi amplasat vreun domino pe celulele rămase goale, iar $config$ va fi un număr întreg care atunci când e transformat în baza $3$ arată configuraţia liniilor $i - 1$ şi $i$.

La fiecare pas, procedura $backtracking$ alege dacă să pună un domino orizontal, unul vertical sau să treacă mai departe, deci o limită superioară ar fi $O(3^M^)$ operaţii (nu toate configuraţiile vor fi posibile). În tablou avem $N x 3^M^$ stări, deci complexitatea algoritmului este $O(N * 9^M^)$. Menţionăm din nou că aceasta este o limită superioară şi că algoritmul se va comporta mult mai bine în practică.

h3. Soluţie:

Evident, putem încerca o soluţie identică cu cea a '$Problemei 1$':probleme-de-acoperire-2#prob1, dar aici limitele sunt puţin mai mari şi avem nevoie de un algoritm mai eficient.

Evident, putem încerca o soluţie identică cu cea a '$Problemei 1$':probleme-de-acoperire-2#problema1, dar aici limitele sunt puţin mai mari şi avem nevoie de un algoritm mai eficient.

Există o rezolvare de complexitate $O(N * M * 3^M^)$ care aşa cum deja v-aţi obişnuit combină metoda $backtracking$ cu metoda $programării dinamice$. Folosim un tablou $max[N][M + 1][3^(M + 1)^]$ care conţine numărul maxim de dale puse pentru o anumită stare. Fiecare element al matricii va avea iniţial $max[i][j][config]$ egal cu $0$. Iterăm rândurile în ordinea $1 .. N$, coloanele în ordinea $1 .. M$ şi configuraţiile în ordine lexicografică. Când vom procesa starea reprezentată de parametrii $(i, j, config)$ vom decide dacă punem una dintre piese cu colţul de stânga sus în $(i, j)$ sau dacă lăsăm celula $(i, j)$ liberă. O stare $(i, j, config)$ se referă la un pătrăţel din matrice şi la o bandă „activă” de pătrăţele ce are lăţimea $2$. Banda conţine celulele $(i1, j + 1), (i1, j + 2)$ pentru $i1 < i$ şi celulele $(i2, j), (i2, j + 1)$ pentru $i &le; i2$. Cifrele în baza $3$ ale parametrului $config$ ne spun starea perechilor de pătrate de pe banda activă: $00$ este reprezentat în $config$ de cifra $0$, $10$ de cifra $1$ şi $11$ de cifra $2$ (configuraţia $01$ nu poate apărea). De exemplu, starea $(4, 3, 1000212)$ va reprezenta configuraţia prezentată în următoarea imagine (ultima cifră corespunde primei perechi de pătrăţele, penultima cifră celei de a doua perechi şamd):

Există o rezolvare de complexitate $O(N * M * 3^M^)$ care, aşa cum deja v-aţi obişnuit, combină metoda $backtracking$ cu metoda $programării dinamice$. Folosim un tablou $max[N][M + 1][3^(M + 1)^]$ care conţine numărul maxim de dale puse pentru o anumită stare. Fiecare element al matricii va fi iniţial egal cu $0$. Iterăm rândurile în ordinea $1 ... N$, coloanele în ordinea $1 ... M$ şi configuraţiile în ordine lexicografică. Când vom procesa starea reprezentată de parametrii $(i, j, config)$ vom decide dacă punem una dintre piese cu colţul din stânga sus în $(i, j)$ sau dacă lăsăm celula $(i, j)$ liberă. O stare $(i, j, config)$ se referă la un pătrăţel din matrice şi la o bandă „activă” de pătrăţele ce are lăţimea $2$. Banda conţine celulele $(i1, j + 1), (i1, j + 2)$ pentru $i1 < i$ şi celulele $(i2, j), (i2, j + 1)$ pentru $i &le; i2$. Cifrele în baza $3$ ale parametrului $config$ ne spun starea perechilor de pătrate de pe banda activă: $00$ este reprezentat în $config$ de cifra $0$, $10$ de cifra $1$ şi $11$ de cifra $2$ (configuraţia $01$ nu poate apărea). De exemplu, starea $(4, 3, 1000212)$ va reprezenta configuraţia prezentată în următoarea imagine (ultima cifră corespunde primei perechi de pătrăţele, penultima cifră celei de a doua perechi şamd):

p=. !probleme-de-acoperire-2?P273.jpg!

h3. Soluţie:

Aceasta este o problemă celebră sau aşa se pare după numărul de concursuri în care a fost folosită şi este o generalizare a unei probleme din articolul precedent.

Aceasta este o problemă celebră, sau aşa se pare după numărul de concursuri în care a fost folosită, şi este o generalizare a unei probleme din articolul precedent.

Prima idee ar fi să încercăm o abordare $greedy$ în care încercăm într-o ordine oarecare să punem piese pe tablă cât timp mai este loc, dar putem găsi uşor contraexemple pentru acest tip de abordare. Limitele sunt mult prea mari pentru ca o rezolvare bazată pe $programare dinamică$ combinată cu $backtracking$ să meargă. O idee ce am utilizat-o în numărul anterior ne va fi folositoare aici. Colorăm tabla noastră în mod asemănător unei table de şah şi numerotăm pătrăţelele tablei.

h2(#bibliografie). Bibliografie

* [1] 'IOI’01 Competition':http://olympiads.win.tue.nl/ioi/ioi2001/contest/A-2001-7.pdf
* [2] 'CEOI’02 Competition material':http://ics.upjs.sk/ceoi/

* [1] "IOI'01 Competition":http://olympiads.win.tue.nl/ioi/ioi2001/contest/A-2001-7.pdf
* [2] "CEOI'02 Competition material":http://ics.upjs.sk/ceoi/

* [3] 'SGU':http://acm.sgu.ru

* [4] 'TopCoder':http://topcoder.com/tc

* [4] 'TopCoder':http://www.topcoder.com/tc