(Categoria _Algoritmi_, autor _Cosmin Negruşeri_)

Aşa cum am promis în numărul anterior, revenim cu un articol la care subiectul este tot acoperiri, care are o abordare mai mult bazată pe tehnici de programare.

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

h3. *Problema 1* (MagicBoxes, TopCoder)

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

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