h2. 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 trebuiesc acoperite cu piese de forma:

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=. !probleme-de-acoperire2?P221.jpg!

_Fig. 1_ !probleme-de-acoperire2?P221.jpg!       _Fig. 2_ !probleme-de-acoperire2?P222.jpg!

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.

h3. Soluţie:

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

* Aşa cum am zis şi în articolul anterior, problemele de acoperire sunt în general $NP complete$, deci prima idee ar fi să încercăm o rezolvare prin metoda $backtraking$, dar dimensiunile datelor de intrare ne arată că o asemenea rezolvare nu ne rezolvă problema.

Pentru prima tablă, acoperirea optimă are două greşeli, aşa cum vedem în al doilea desen.

* Strategii polinomiale de tip $greedy$ sau de tip $programare dinamică$ nu vor rezolva această problemă pe toate cazurile de intrare, şi pentru orice strategie se poate găsi câte un contraexemplu. Totuşi vom putea să folosim o rezolvare bazată pe combinarea tehnicilor de $programare dinamică$ şi $backtraking$. Să vedem cum.
* Construim soluţia optimă coloană cu coloană, dar este evident din următorul exemplu că pentru a construi soluţia optimă pentru coloana $j + 1$ nu este de ajuns să acoperim optim primele $j$ coloane.
 
p=. !probleme-de-acoperire2?P223.jpg!
 
* Evident soluţia optimă pe primele trei coloane ale tablei foloseşte piesa în formă de cruce şi se obţine o acoperire cu $0$ greşeli, dar când vrem să acoperim toate $4$ coloanele tablei folosind prima acoperire obţinem o tablă cu $2$ greşeli, iar folosind două piese de tipul doi orientate înspre stânga, obţinem o acoperire cu o singură greşeală.
* Pentru a obţine o soluţie cu $j + 1$ coloane ne trebuie toate soluţiile cu $j$ coloane la care ştim configuraţia coloanelor $j – 1$ şi $j$ (o piesă poate influenţa configuraţia a cel mult trei coloane). De aici se conturează ideea de a folosi un tablou $best$ unde $best[j][config1][config2]$ conţine numărul minim de greşeli astfel încât coloana $j$ are pătratele rămase neacoperite date de mulţimea $config1$, iar coloana $j - 1$ are pătratele neacoperite date de mulţimea $config2$. Pentru a trece de la $j$ la $j + 1$, facem un $backtracking$ pe o tablă de trei coloane dintre care prima are pătrăţelele ocupate date de $config2$, a doua pătrăţelele ocupate date de $config1$, iar a treia nu are nici un pătrăţel ocupat. După ce am plasat în procedura $backtraking$ nişte piese ajungem la configuraţiile pentru coloane date de mulţimile $c1 c2 c3$ şi actualizăm dacă am obţinut un număr mai mic pe $best[j + 1][c3][c2]$. În procedura recursivă ţinem cont atunci când vom acoperi cu piese un pătraţel deja acoperit sau un pătraţel ce nu este stricat. Ambele mulţimi $config1$ şi $config2$ pot fi reprezentate cu biţii unui întreg, $N$ fiind mic, astfel: primii $7$ biţi ai unui întreg vor reprezenta elementele primei mulţimi iar următorii $7$ biţi elementele celei de a două mulţimi. Memoria folosită de algoritmul nostru are ordinul de complexitate $O(M * 4^N^)$, acesta putând fi uşor micşorat la $O(4^N^)$ pentru că la pasul $j + 1$ avem nevoie numai de linia $j$ a matricii. Pentru a reduce numărul de stări folosite ne vom folosi de observaţia că putem să facem o restricţie asupra acoperirilor, aceea că atunci când ajungem la linia $j$ orice piesă nouă amplasată trebuie să acopere cel puţin un pătrăţel neacoperit de pe linia $j – 1$. Fie $newBest[j][confing12]$ structura care păstrează cele mai bune acoperiri cu această restricţie, atunci soluţia optimă va fi în $newBest[M + 1]$ unde am considerat o nouă coloană $M + 1$ a tablei ce nu are niciun pătrăţel stricat. Pentru tablele astfel acoperite, configuraţiile ultimelor două pătrăţele de pe o linie de forma $11$ şi $10$ şi $00$, configuraţia $01$ nu apare pentru că este evident că nu există o piesă care să acopere un pătrat din ultima coloană, un pătrat cu două coloane înainte şi să nu acopere pătratul imediat în stânga pătratului de pe ultima linie. Astfel avem $O(3^N^)$ configuraţii posibile pentru ultimele două coloane. Mai există multe configuraţii de două coloane la care nu se poate ajunge folosind piesele din problemă, dar o analiză exactă ar fi dificilă şi probabil ar complica inutil implementarea. Să vedem cum arată configuraţiile pe un exemplu:
 
p=. !probleme-de-acoperire2?P224.jpg!
 
* Putem reprezenta această acoperire astfel:
 
00010
01110
11110
00011
 
* Iar ultimele două coloane arată în felul următor:
 
10
10
10
10
11
 
* Î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)
 
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: