(Categoria _Algoritmi_, autor _Cosmin Negruşeri_)

(toc){width: 33em}*{text-align:center} *Cuprins*
* 'Problema 1 ( _MagicBoxes, TopCoder_ ) ':probleme-de-acoperire2#prob1
* 'Problema 2 ( _IOI 2001 Pavement, problemă de rezervă_, [1] ) ':probleme-de-acoperire2#prob2
* 'Problema 3 ( _ACM ICPC 1997_ ) ':probleme-de-acoperire2#prob3
* 'Problema 4 ( _Hardwood Floor, acm.sgu.ru_ ) ':probleme-de-acoperire2#prob4
* 'Problema 5 ( _TopCoder, CaseysArt_ ) ':probleme-de-acoperire2#prob5
* 'Problema 6 ( _Another chocolate maniac, acm.sgu.ru_ ) ':probleme-de-acoperire2#prob6
* 'Problema 7 ( _Bugs, CEOI 2002_, [2] ) ':probleme-de-acoperire2#prob7
* 'Problema 8 ( _CSP 1993, Lot 2001, Dominoes acm.sgu.ru, IPSC 2004 sample task, Algoritmus 2005, IOI 2005 practice task_ ) ':probleme-de-acoperire2#prob8
* 'Aplicaţii':probleme-de-acoperire2#app
 
 

Subiectul acestui articol sunt acoperirile cu o abordare bazată pe tehnici de programare.

h2. Problema 1 ( _MagicBoxes, TopCoder_ )

h2(#prob1). Problema 1 ( _MagicBoxes, TopCoder_ )

bq. Să se determine numărul $N$ maxim astfel ca într-un dreptunghi de dimensiuni $L x W (1 <= L , W <= 30)$ să poată fi dispuse paralel cu axele de coordonate $N$ pătrate de laturi $1 .. N$ astfel ca oricare două pătrate să nu aibă porţiuni care se suprapun.

Această reprezentare pe biţi este foarte utilă în probleme de acest gen, şi cum avem întregi de $64$ de biţi pe care îi putem folosi, avem o metodă foarte simplă de reprezentare a tablelor de mărime până la $64$.

h2. Problema 2 ( _IOI 2001 Pavement, problemă de rezervă_, [1] )

h2(#prob2). Problema 2 ( _IOI 2001 Pavement, problemă de rezervă_, [1] )

bq. Se dă o matrice de dimensiuni $N x M (1 <= N <= 7 şi 1 <= M <= 100)$. Unele celule ale acestei matrici sunt distruse şi trebuie acoperite cu piese de forma din $Fig. 1$. Fiecare celulă rămasă neacoperită se consideră o greşeală, iar dacă o piesă cu care am acoperit celule distruse a trebuit să fie tăiată pentru a acoperi numai celule distruse, fiecare pătrăţel din partea nefolosită a piesei este considerată o greşeală. Se cere acoperirea tablei astfel ca numărul de greşeli să fie minimizat. În $Fig. 2$, pentru prima tablă, acoperirea optimă are două greşeli, aşa cum vedem în al doilea desen.

În acest caz $config$ are valoarea $1 * 3^0^ + 1 * 3^1^ + 1 * 3^2^ + 1 * 3^3^ + 2 * 3^4^ = 202$. Acum, la fiecare pas noi vrem să punem pe coloana $j – 1$ câte o piesă pentru a obţine rezultatele pentru $newBest[j + 1]$, sau să nu punem o piesă acolo. Deci, avem $9$ posibilităţi de a pune piese (fiecare rotaţie şi reflexie a pieselor din problemă) şi posibilitatea de a nu pune piesă în pătrăţelul curent, deci în total $10$ posibilităţi. Astfel, complexitatea algoritmului nostru devine $O(M * 3^N^ * 10^N^)$, constanta din faţă acestei complexităţi este subunitară din cauză că nu vom trece prin stări imposibile.

h2. Problema 3 ( _ACM ICPC 1997_ )

h2(#prob3). Problema 3 ( _ACM ICPC 1997_ )

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $N x M (N <= 15, M <= 15)$ cu dominouri.

Dacă procedura aşezăm trei dominouri pe linia $4$ şi linia $5$ aşa cum vedem mai sus, atunci vom trece în starea $(5, 011000)$. La final, vom returna valoarea aflată în $numWays[N + 1][0]$. Complexitatea ca timp a acestei rezolvări este $O(M * 4^N^)$, iar ca spaţiu este $O(2^N^)$.

h2. Problema 4 ( _Hardwood Floor, acm.sgu.ru_ )

h2(#prob4). Problema 4 ( _Hardwood Floor, acm.sgu.ru_ )

bq. Determinaţi numărul de acoperiri ale unei table de dimensiuni $N x M (1<= N <= 9, 1 <= M <= 9)$ cu piese de tipul:

În rezolvare putem folosi direct ideea de rezolvare a problemei anterioare.

h2. Problema 5 ( _TopCoder, CaseysArt_ )

h2(#prob5). Problema 5 ( _TopCoder, CaseysArt_ )

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $N x M (N <= 18, M <= 15)$ cu piese de forma:

Menţionăm că această problemă a apărut ca întrebare la miniconcursul online de pe forumul "GInfo":http://www.ginfo.ro.

h2. Problema 6 ( _Another chocolate maniac, acm.sgu.ru_ )

h2(#prob6). Problema 6 ( _Another chocolate maniac, acm.sgu.ru_ )

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.

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ă.

h2. Problema 7 ( _Bugs, CEOI 2002_, [2] )

h2(#prob7). Problema 7 ( _Bugs, CEOI 2002_, [2] )

bq. Să se acopere o tablă de dimensiuni $M x N (1 <= M <= 10, 1 <= N <= 150)$ cu un număr maxim de piese de dimensiuni $3 x 2$ şi $2 x 3$. Tabla are unele celule ce trebuie să nu fie acoperite, iar oricare două piese nu se pot suprapune. Pentru tabla de mai jos, numărul maxim de piese cu care se poate acoperi este $3$.

Tablei îi adăugăm la sfârşit o coloană pe care nu pot fi aşezate piese. Rezultatul cerut de problemă se va afla în $max[N][M + 1][0]$. Menţionăm că $Problemele 2, 3$ şi $4$ pot fi rezolvate în mod asemănător în complexitate $O(N * M * 2^M^)$.

h2. Problema 8 ( _CSP 1993, Lot 2001, Dominoes acm.sgu.ru, IPSC 2004 sample task, Algoritmus 2005, IOI 2005 practice task_ )

h2(#prob8). Problema 8 ( _CSP 1993, Lot 2001, Dominoes acm.sgu.ru, IPSC 2004 sample task, Algoritmus 2005, IOI 2005 practice task_ )

bq. Se dă o tablă de dimensiuni $N x M$, din care unele pătrate sunt eliminate. Se cere să se determine o acoperire a tablei cu număr maxim de dominouri $(1 <= N, M <= 200)$. De exemplu, o tablă ce nu are nicio celulă eliminată, de $3 x 3$ pătrăţele poate fi acoperită cu cel mult $4$ dominouri care nu se suprapun. O soluţie posibilă este prezentată în a doua figură.

p=. !probleme-de-acoperire2?P283.jpg!

h2. Aplicaţii

h2(#app). Aplicaţii

* "Pavare":http://infoarena.ro/problema/pavare