Probleme de acoperire 2

Probleme de acoperire (partea a II-a)

h1. Probleme de acoperire 2

h1. Probleme de acoperire (partea a II-a)

(Categoria _Algoritmi_, autor _Cosmin Negruşeri_)

== include(page="template/implica-te/scrie-articole" user_id="marius") ==

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

(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)

h2. Problema 1 ( _MagicBoxes, TopCoder_ )

(toc){width: 37em}*{text-align:center} *Conţinut:*
* 'Problema 1: MagicBoxes (TopCoder)':probleme-de-acoperire-2#problema1
* 'Problema 2: Pavement (IOI 2001)':probleme-de-acoperire-2#problema2
* 'Problema 3 (ACM ICPC 1997)':probleme-de-acoperire-2#problema3
* 'Problema 4: Hardwood Floor (SGU)':probleme-de-acoperire-2#problema4
* 'Problema 5: CaseysArt (TopCoder)':probleme-de-acoperire-2#problema5
* 'Problema 6: Another chocolate maniac (SGU)':probleme-de-acoperire-2#problema6
* 'Problema 7: Bugs (CEOI 2002)':probleme-de-acoperire-2#problema7
* 'Problema 8 (Lot 2001, SGU Domino, IPSC 2004, Algoritmus 2005, IOI 2005)':probleme-de-acoperire-2#problema8
* 'Aplicaţii':probleme-de-acoperire-2#aplicatii
* 'Bibliografie':probleme-de-acoperire-2#bibliografie

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.

Subiectul acestui articol sunt acoperirile in plan, cu o abordare bazată pe tehnici de programare. În "$...secţiunea precedentă$":probleme-de-acoperire-1 am studiat problemele de acoperire care nu necesită cunoştinţe avansate de algoritmi.
 
h2(#problema1). Problema 1: 'MagicBoxes':http://www.topcoder.com/stat?c=problem_statement&pm=932 (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, 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 $backtracking$ 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. Problema 2 ( _IOI 2001 Pavement, problemă de rezervă_, [1] )

h2(#problema2). Problema 2: Pavement (IOI 2001)

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-acoperire2?P221.jpg!       _Fig. 2_ !probleme-de-acoperire2?P222.jpg!

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

h3. Soluţie:

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.

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 $backtracking$, dar dimensiunile datelor de intrare ne arată că o asemenea rezolvare nu ne rezolvă problema.

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.

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

p=. !probleme-de-acoperire-2?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:

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 $backtracking$ 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 coloana $j$ orice piesă nouă amplasată trebuie să acopere cel puţin un pătrăţel neacoperit de pe coloana $j – 1$. Fie $newBest[j][config12]$ 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 sunt 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!

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

Putem reprezenta această acoperire astfel:

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

Î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 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. 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^)$, dar constanta din faţă este subunitară (mult mai mică decât 1) din cauză că nu vom trece prin stări imposibile.

h2. Problema 3 ( _ACM ICPC 1997_ )

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:

Am văzut în numărul anterior că există o formulă pentru acest număr. Abordarea matematică poate fi generalizată şi pentru mai multe probleme asemănătoare de acoperire, dar cunoştinţele necesare sunt avansate, deci această abordare nu ne prea ajută pe noi ca informaticieni.

Am văzut în 'partea I a articolului':probleme-de-acoperire-1 că există o formulă pentru acest număr. Abordarea matematică poate fi generalizată şi pentru mai multe probleme asemănătoare de acoperire, dar cunoştinţele necesare sunt avansate, deci această abordare nu ne prea ajută pe noi ca informaticieni.

O soluţie care ne va da numărul exact şi ar fi putut fi folosită în concurs este asemănătoare celei expuse mai sus. Vom folosi o combinaţie a metodei $backtracking$ cu metoda $programării dinamice$. Tabloul $numWays[i][config]$ va fi numărul de posibilităţi de a acoperi complet primele $i - 1$ coloane ale unei table, iar pe coloana $i$ pătratele ocupate sunt reprezentate de mulţimea $config$. Astfel, $numWays[i + 1][config1]$  va fi egal cu suma de $numWays[i][config]$ unde putem acoperi cu dominouri două coloane astfel ca pe prima coloană să nu fie acoperite celulele date de $config$ şi pe a doua coloană să fie acoperite celulele date de $config1$. De exemplu, starea dată de $(4, 100100)$ este prezentată în următoarea figură:

O soluţie care ne va da numărul exact şi ar fi putut fi folosită în concurs este asemănătoare celei expuse mai sus. Vom folosi o combinaţie a metodei $backtracking$ cu metoda $programării dinamice$. Tabloul $numWays[i][config]$ va fi numărul de posibilităţi de a acoperi complet primele $i - 1$ coloane ale unei table, iar pe coloana $i$ pătratele ocupate să fie reprezentate de $config$. Astfel, $numWays[i + 1][config1]$ va fi egal cu suma de $numWays[i][config]$, unde putem acoperi cu dominouri două coloane astfel ca pe prima coloană să fie acoperite toate celulele, în afara celor date de $config$, iar pe a doua coloană să fie acoperite celulele date de $config1$. De exemplu, starea dată de $(4, 100100)$ este prezentată în următoarea figură:

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

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

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

Dacă algoritmul pune trei dominouri pe liniile $4$ şi $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 $O(2^N^)$.

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

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

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?P241.jpg!
 
h3. Soluţie:

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

Exemplu: Pentru $N = 3$ şi $M = 2$ avem $5$ acoperiri posibile.

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

h3. Soluţie:

h2. Problema 5 ( _TopCoder, CaseysArt_ )

În rezolvare putem folosi direct ideea de la problema anterioară.

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:

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

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

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:

h3. Soluţie:

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

De exemplu, pentru $N = 3, M = 4$ avem următoarele acoperiri:

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

p=. !probleme-de-acoperire-2?P252.jpg!
 
h3. Soluţie:

Din nou, ideea de rezolvare este cea prezentată în $Problema 2$. Complexitatea soluţiei este $O(N * 4^M^)$, dar trebuie să fim conştienţi că aceasta este o limită superioară mult mai mare decât complexitatea reală. Să vedem şi implementarea unei asemenea soluţii:

Din nou, ideea de rezolvare este cea prezentată în '$Problema 2$':probleme-de-acoperire-2#problema2. Complexitatea soluţiei este $O(N * 4^M^)$, dar trebuie să fim conştienţi că aceasta este o limită superioară mult mai mare decât complexitatea reală. Să vedem şi implementarea unei asemenea soluţii:

== code(java) |

import java.util.*;
 

public class CaseysArt {
    double[][] num;
    int step, w;

        {{1, 1},{0, 1}},
        {{1, 1},{1, 0}}};
    int[][] sol;

    void checksol() {

        int config = 0,config1 = 0;
        for (int i = 0;i < w; i++) {
            if (sol[i][0] == 0) config |= (1<<i);
            if (sol[i][1] == 1) config1 |= (1<<i);

        int config = 0, config1 = 0;
        for (int i = 0; i < w; i++) {
            if (sol[i][0] == 0) config |= (1 << i);
            if (sol[i][1] == 1) config1 |= (1 << i);

        }
        num[1 ^ step][config1] += num[step][config];
    }

    void doit(int x) {

        if (x == w) checksol();

        if (x == w)
            checksol();

        else {
            if (x < w - 1) {
                int i, j, k;
                boolean bool;

                for (k = 0; k < 4; k++) {

                    bool=true;

                    bool = true;

                    for (i = 0; i < 2; i++) {
                        for (j = 0; j < 2; j++) {
                            if (p[k][i][j] == 1)
                                bool = bool && (sol[x + i][j] == 0);
                        }
                    }

                    if (bool) {
                        for (i = 0; i < 2; i++) {
                            for (j = 0; j < 2; j++) {

            doit(x+1);
        }
    }

    public double howManyWays(int l, int w) {
        num = new double[2][1 << w];
        this.w = w;

}
==

În $num[i][config]$ ţinem minte câte posibilităţi sunt să acoperim $i - 1$ linii cu piesele date în problemă, iar linia $i$ să fie ocupată aşa cum arată reprezentarea în baza $2$ a numărului întreg $config$. Se observă folosirea variabilei $step$ care de la un pas la altul se transformă astfel $step ^= 1$, aceast mic truc ne face să putem folosi o matrice de doar $2$ linii în loc să folosim $N$ linii. La momentul $i$, în $num[step][config]$ avem informaţia ce ar fi fost în mod normal în $num[i][config]$, iar în $num[1 ^ step][config1]$ vom calcula ce ar fi fost normal în $num[i + 1][config1]$. În şirul $p$ ţinem minte forma pieselor din problemă.
 
În procedura $doit$ punem pe două linii consecutive piese în toate modurile posibile. Această procedură face ca pe prima linie să avem o configuraţie de pătrăţele libere $config$ şi o configuraţie de pătrăţele ocupate pe a doua linie $config1$. Dacă pătrăţelele reprezentate de $config$ nu au fost ocupate la pasul curent ele trebuie să fi fost ocupate la pasul anterior. Astfel, pentru fiecare pereche de configuraţii $config$ şi $config1$ trebuie să efectuăm operaţia $num[i + 1][config1] += num[i][config]$.

În $num[i][config]$ ţinem minte câte posibilităţi sunt să acoperim $i - 1$ linii cu piesele date în problemă, iar linia $i$ să fie ocupată aşa cum arată reprezentarea în baza $2$ a numărului întreg $config$. Se observă folosirea variabilei $step$ care de la un pas la altul se transformă astfel: $step ^= 1$. Acest mic truc ne face să putem folosi o matrice de doar $2$ linii în loc să folosim $N$ linii. La momentul $i$, în $num[step][config]$ avem informaţia ce ar fi fost în mod normal în $num[i][config]$, iar în $num[1 ^ step][config1]$ vom calcula ce ar fi fost normal în $num[i + 1][config1]$. În şirul $p$ ţinem minte forma pieselor din problemă.

Dacă această rezolvare ar fi fost folosită în timpul concursului ea ar fi ieşit din timp. Pentru optimizarea ei putem face mai multe optimizări. Un exemplu ar fi să generăm direct cele două configuraţii de biţi în procedura $backtraking$ şi să nu mai folosim şirul $sol$. O altă idee care ar fi dus la rezolvarea problemei ar fi fost calcularea tuturor rezultatelor posibile în timpul concursului şi trimiterea unei soluţii care returna aceste rezultate precalculate. Această abordare ar fi fost posibilă pentru că numărul de configuraţii iniţiale este mic.

În procedura $doit$ punem pe două linii consecutive piese în toate modurile posibile. Această procedură face ca pe prima linie să avem o configuraţie de pătrăţele libere $config$, iar pe a doua o configuraţie de pătrăţele ocupate $config1$. Dacă pătrăţelele reprezentate de $config$ nu au fost ocupate la pasul curent ele trebuie să fi fost ocupate la pasul anterior. Astfel, pentru fiecare pereche de configuraţii $config$ şi $config1$ trebuie să efectuăm operaţia $num[i + 1][config1] += num[i][config]$.

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

Dacă această rezolvare ar fi fost folosită în timpul concursului, ea ar fi ieşit din timp. Pentru optimizare putem face mai multe îmbunătăţiri. Un exemplu ar fi să generăm direct cele două configuraţii de biţi în procedura $backtracking$ şi să nu mai folosim şirul $sol$. O altă idee care ar fi dus la rezolvarea problemei în timpul concursului ar fi fost calcularea tuturor rezultatelor posibile şi trimiterea unei soluţii care returna aceste rezultate precalculate. Această abordare ar fi fost posibilă pentru că numărul de configuraţii iniţiale este mic.

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

h2(#problema6). Problema 6: 'Another chocolate maniac':http://acm.sgu.ru/problem.php?contest=0&problem=132 (SGU)

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 suprapună î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-acoperire2?P261.jpg!

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

h3. Soluţie:

Din nou vom folosi $metoda programării dinamice$ îmbinată cu metoda $backtraking$.

Din nou vom folosi $metoda programării dinamice$ îmbinată cu metoda $backtracking$.

Vom umple tabla linie cu linie şi la fiecare pas putem pune dominouri orizontale pe linia curentă şi verticale pe linia curentă şi linia următoare. Trebuie să fim atenţi când trecem de la linia curentă la următoarea să nu lăsăm pe linia curentă loc liber unde poate fi amplasat un domino orizontal, pentru că acest loc nu va putea fi ocupat de piese amplasate mai târziu. Se poate lăsa spaţiu gol pe linia curentă şi linia următoare pentru că o celulă a acestei poziţii va putea fi acoperită la pasul următor. Vedem astfel că dacă linia curentă este linia $i$ atunci avem trei stări posibile pentru ultimele două pătrăţele de pe fiecare coloană: $00$ (celule neocupate), $10$ (penultima celulă ocupată şi ultima goală) $11$ (ambele celule ocupate de dominouri), starea $01$ nu poate exista. În procedura $backtracking$ care generează configuraţiile la care putem ajunge de la o configuraţie dată trebuie să mai avem grijă să nu ocupăm cu un domino o celulă ce nu aparţine tablei. Astfel, pentru a găsi soluţia problemei vom folosi un tablou $min[i][config]$ care va păstra numărul minim de dominouri care trebuie amplasate pe tablă astfel ca pe liniile $1 .. i – 1$ să nu poată fi amplasat vreun domino pe celulele rămase goale, $config$ va fi un număr întreg care atunci cănd e transformat în baza $3$ arată configuraţia liniilor $i – 1$ şi $i$.

Vom umple tabla linie cu linie şi la fiecare pas putem pune dominouri orizontale pe linia curentă şi verticale pe linia curentă şi linia următoare. Trebuie să fim atenţi când trecem de la linia curentă la următoarea să nu lăsăm pe linia curentă loc liber unde poate fi amplasat un domino orizontal, pentru că acest loc nu va putea fi ocupat de piese amplasate mai târziu. Se poate lăsa spaţiu gol pe linia curentă şi linia următoare pentru că o celulă a acestei poziţii va putea fi acoperită la pasul următor. Vedem astfel că dacă linia curentă este linia $i$ atunci avem trei stări posibile pentru ultimele două pătrăţele de pe fiecare coloană: $00$ (celule neocupate), $10$ (penultima celulă ocupată şi ultima goală), $11$ (ambele celule ocupate de dominouri). Starea $01$ nu poate exista. În procedura $backtracking$ care generează configuraţiile la care putem ajunge de la o configuraţie dată trebuie să mai avem grijă să nu ocupăm cu un domino o celulă ce nu aparţine tablei. Astfel, pentru a găsi soluţia problemei vom folosi un tablou $min[i][config]$ care va păstra numărul minim de dominouri care trebuie amplasate pe tablă astfel ca pe liniile $1, 2, ..., i - 1$ să nu poată fi amplasat vreun domino pe celulele rămase goale, iar $config$ va fi un număr întreg care atunci când e transformat în baza $3$ arată configuraţia liniilor $i - 1$ şi $i$.

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(#problema7). Problema 7: 'Bugs':http://acm.pku.edu.cn/JudgeOnline/problem?id=1038 (CEOI 2002)

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-acoperire2?P272.jpg!

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

h3. Soluţie:

Evident, putem încerca o soluţie identică cu cea a $Problemei 1$, dar aici limitele sunt puţin mai mari şi avem nevoie de un algoritm mai eficient.

Evident, putem încerca o soluţie identică cu cea a '$Problemei 1$':probleme-de-acoperire-2#problema1, 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 fi iniţial 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 din 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 ş.a.m.d.):

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

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

Dacă decidem să nu punem piesă în pătrăţelul $(4, 3)$ atunci din starea $(4, 3, 1000212)$ trecem în starea $(5, 3, 10000212)$.

Dacă decidem să nu punem piesă în pătrăţelul $(4, 3)$ atunci din starea $(4, 3, 1000212)$ trecem în starea $(5, 3, 1000212)$.

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

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

Dacă punem o piesă verticală ajungem în starea $(7, 3, 1111212)$.

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

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

Iar dacă punem o piesă orizontală atunci ajungem în starea $(6, 3, 1022212)$.

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

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

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

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$':probleme-de-acoperire-2#problema2, '$3$':probleme-de-acoperire-2#problema3 şi '$4$':probleme-de-acoperire-2#problema4 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(#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-acoperire2?P281.jpg!

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

h3. Soluţie:

Aceasta este o problemă celebră sau aşa se pare după numărul de concursuri în care a fost folosită şi este o generalizare a unei probleme din articolul precedent.

Aceasta este o problemă celebră, sau aşa se pare după numărul de concursuri în care a fost folosită, şi este o generalizare a unei probleme din 'articolul precedent':probleme-de-acoperire-1.
 
Prima idee ar fi să încercăm o abordare $greedy$ şi să punem piese pe tablă într-o ordine oarecare cât timp mai este loc. Dar putem găsi uşor contraexemple pentru acest tip de abordare. Limitele sunt mult prea mari pentru ca o rezolvare bazată pe $programare dinamică$ combinată cu $backtracking$ să meargă. O idee ce am utilizat-o în articolul anterior ne va fi folositoare şi aici. Colorăm tabla noastră în mod asemănător unei table de şah şi numerotăm pătrăţelele tablei.
 
p=. !probleme-de-acoperire-2?P282.jpg!

Prima idee ar fi să încercăm o abordare $greedy$ în care încercăm într-o ordine oarecare să punem piese pe tablă cât timp mai este loc, dar putem găsi uşor contraexemple pentru acest tip de abordare. Limitele sunt mult prea mari pentru ca o rezolvare bazată pe $programare dinamică$ combinată cu $backtraking$ să meargă. O idee ce am utilizat-o în numărul anterior ne va fi folositoare aici. Colorăm tabla noastră în mod asemănător unei table de şah şi numerotăm pătrăţelele tablei.

Acum vedem că un domino amplasat pe tablă trebuie să ocupe o celulă colorată alb şi una negru, celule care sunt adiacente. Dacă realizăm un graf în care nodurile sunt celulele, iar între două noduri există muchie dacă ele sunt adiacente vertical sau orizontal pe tablă, observăm că graful este bipartit. O acoperire cu dominouri corespunde în acest graf unei mulţimi de muchii pentru care nu există două muchii cu acelaşi capăt (o muchie corespunde amplasării posibile a unui domino, iar restricţia menţionată face să nu existe dominouri care se suprapun). Deci pentru a găsi o soluţie maximală pentru problema iniţială, trebuie să găsim o mulţime de muchii neadiacente de cardinal maxim. În acest mod am transformat cerinţa într-o problemă clasică de teoria grafurilor cunoscută sub numele de $cuplaj maxim într-un graf bipartit$. Vedem în imaginea următoare cum a fost transformată tabla într-un graf şi cum soluţia prezentată în exemplu corespunde unui $cuplaj maxim$ în graful asociat tablei.

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

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

Acum vedem că un domino poate fi amplasat pe tablă şi el trebuie să ocupe o celulă colorată alb şi una negru, celule care sunt adiacente. Dacă realizăm un graf în care nodurile sunt celulele iar între două noduri există muchie dacă ele sunt adiacente vertical sau orizontal pe tablă, facem observaţia că graful este bipartit. O acoperire cu dominouri corespunde în acest graf unei mulţimi de muchii pentru care nu există două muchii cu acelaşi capăt (o muchie corespunde amplasării posibile a unui domino, iar restricţia menţionată face ca să nu existe dominouri care se suprapun). Deci pentru a găsi o soluţie maximală pentru problema iniţială, trebuie să găsim o mulţime de muchii de cardinal maxim. În acest mod am transformat cerinţa într-o problemă clasică de teoria grafurilor cunoscută sub numele de $cuplaj maxim într-un graf bipartit$. Vedem în imaginea următoare cum a fost transformată tabla într-un graf şi cum soluţia prezentată în exemplu corespunde unui $cuplaj maxim$ în graful asociat tablei.

h2(#aplicatii). Aplicaţii

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

* 'Pavare':problema/pavare, info{_arena_}
* 'Choco':problema/choco, info{_arena_}
* 'Little Kings':http://acm.sgu.ru/problem.php?contest=0&problem=223, SGU

h2. Aplicaţii

h2(#bibliografie). Bibliografie

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

* [1] "IOI'01 Competition":http://olympiads.win.tue.nl/ioi/ioi2001/contest/A-2001-7.pdf
* [2] "CEOI'02 Competition material":http://ics.upjs.sk/ceoi/
* [3] 'SGU':http://acm.sgu.ru
* [4] 'TopCoder':http://www.topcoder.com/tc
 

3384