h2(#problema1). Problema 1 ('TC MagicBoxes':http://www.topcoder.com/stat?c=problem_statement&pm=932)

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.

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, 2, ..., N$ astfel ca oricare două pătrate să nu aibă porţiuni care se suprapun.

h3. Soluţie:

Această problemă, deşi clasică, este dificil de rezolvat în cazul general si singura abordare a ei este aceea de a folosi metoda $backtracking$.

Această problemă, deşi clasică, este dificil de rezolvat în cazul general şi singura abordare a ei este aceea de a folosi metoda $backtracking$.

Întâi putem stabili o limită superioară a numarului $N$: este evident că $N <= W, N <= L$ şi că $1^2^ + 2^2^ + .. + N^2^ <= L x W$. Putem porni cu $N$ de la limita superioară dată de aceste inegalităţi şi să încercăm să dispunem cele $N$ pătrate în interiorul dreptunghiului. O optimizare simplă care ne-ar fi ajutat să rezolvăm problema, precalculând toate rezultatele, ar fi fost să punem în dreptunghi pătratele în ordinea descrescătoare a înălţimii. Altă observaţie ce reduce timpul de execuţie este că piesa cea mai mare nu trebuie pusă în toate poziţiile posibile ci în un sfert din ele, din cauza soluţiilor simetrice, iar între ea şi margine nu trebuie lăsat spaţiu puţin pentru că acel spaţiu va rămâne nefolosit. Observaţia care ne-ar fi dus la o soluţie care să rezolve un test în două secunde, cât era limita de timp în concurs, este că procedura $backtraking$ pierde mult timp pentru verificarea dacă o piesă poate fi pusă pe o anumită poziţie. Dacă în loc de reprezentarea pe matrice folosim $L$ întregi astfel ca bitul al $j$-lea din întregul $i$ este $1$ dacă celula $(i, j)$ este deja ocupată şi $0$ altfel, vom putea verifica dacă pătratul de latură $i$ poate fi plasat pe o anumită poziţie în $i$ paşi, şi nu în $i^2^$ paşi ca înainte.

Întâi putem stabili o limită superioară a numarului $N$: este evident că $N ≤ W, N ≤ L$ şi că $1^2^ + 2^2^ + ... + N^2^ ≤ L x W$. Putem porni cu $N$ de la limita superioară dată de aceste inegalităţi şi să încercăm să dispunem cele $N$ pătrate în interiorul dreptunghiului. O optimizare simplă care ne-ar fi ajutat să rezolvăm problema, precalculând toate rezultatele, ar fi fost să punem în dreptunghi pătratele în ordinea descrescătoare a înălţimii. Altă observaţie ce reduce timpul de execuţie este că piesa cea mai mare nu trebuie pusă în toate poziţiile posibile, ci într-un sfert din ele, din cauza soluţiilor simetrice, iar între ea şi margine nu trebuie lăsat spaţiu puţin pentru că acela va rămâne nefolosit. Observaţia care ne-ar fi dus la o soluţie care să rezolve un test în două secunde, cât era limita de timp în concurs, este că procedura $backtraking$ pierde mult timp pentru verificarea dacă o piesă poate fi pusă pe o anumită poziţie. Dacă în loc de reprezentarea pe matrice folosim $L$ întregi astfel ca bitul al $j$-lea din întregul $i$ sa fie $1$ dacă celula $(i, j)$ este deja ocupată şi $0$ altfel, vom putea verifica dacă pătratul de latură $i$ poate fi plasat pe o anumită poziţie în $i$ paşi, şi nu în $i^2^$ paşi ca înainte.

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(#problema2). Problema 2 (IOI 2001 Pavement)

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.

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.

p=. _Fig. 1_ !probleme-de-acoperire-2?P221.jpg!       _Fig. 2_ !probleme-de-acoperire-2?P222.jpg!

h2(#problema3). 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.

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.

h3. Soluţie:

h2(#problema4). Problema 4 ('SGU Hardwood Floor':http://acm.sgu.ru/problem.php?contest=0&problem=131)

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:

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:

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

h2(#problema5). Problema 5 ('TC CaseysArt':http://www.topcoder.com/stat?c=problem_statement&pm=1706)

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:

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:

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

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

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

h2(#problema7). Problema 7 ('CEOI 2002 Bugs':http://acm.pku.edu.cn/JudgeOnline/problem?id=1038)

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

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

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

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.

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 <= 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 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):

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

h2(#problema8). Problema 8 (Lot 2001, 'SGU Domino':http://acm.sgu.ru/problem.php?contest=0&problem=101, 'IPSC 2004':http://ipsc.ksp.sk/contests/ipsc2004/practice/problems/t.php, Algoritmus 2005, IOI 2005)

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

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-acoperire-2?P281.jpg!