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

h3. Soluţie:
 

De exemplu, pentru $N = 3, M = 4$ avem următoarele acoperiri:
p=. !probleme-de-acoperire-2?P252.jpg!

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:

h3. Soluţie:
 
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) {

            if(x < w - 1) {

                int i, j, k;
                boolean bool;

                for (k = 0; k < 4; k++) {
                    bool=true;
                    for (i = 0; i < 2; i++) {
                        for (j = 0; j < 2; j++) {
                            if (p[k][i][j] == 1)

 
                for(k = 0; k < 4; k++) {
                    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++) {
                                if (p[k][i][j] == 1)

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

                                    sol[x + i][j] = 1;
                            }
                        }
                        doit(x + 1);

                        for (i = 0; i < 2; i++) {
                            for (j = 0; j < 2; j++) {
                                if (p[k][i][j] == 1)

                        for(i = 0; i < 2; i++) {
                            for(j = 0; j < 2; j++) {
                                if(p[k][i][j] == 1)

                                    sol[x + i][j]=0;
                            }
                        }

            doit(x+1);
        }
    }

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

        for (int i = 1; i < l; i++) {

        for(int i = 1; i < l; i++) {

            Arrays.fill(num[1 ^ step], 0);
            doit(0);
            step ^= 1;

}
==

Î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ă.
 
Î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 $backtracking$ ş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 optimizarea ei 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 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.

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