Probleme de acoperire 2

(Categoria Algoritmi, autor Cosmin Negruşeri)

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

Problema 1 (MagicBoxes, TopCoder)

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.

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² + .. + N² <= 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² 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.

Problema 2 (IOI 2001 Pavement, problemă de rezervă [1])

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:

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.

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

Soluţie: