}
==

Acest algoritm are complexitatea $O(N*M log N)$ şi nu s-ar fi încadrat în timpul impus, deoarece marea parte a calculelor este efectuată în determinarea celui mai mare divizor comun a două numere. Având în vedere că numerele folosite sunt între $1$ şi $N$ respectiv între $1$ şi $M$, putem să precalculăm o matrice $CMMDC[X][Y]$, $1 ≤ X ≤ N$ şi $1 ≤ Y ≤ M$, în $O(N * M)$. Astfel, complexitatea soluţiei a fost redusă la $O(N * M)$. Mai putem optimiza factorii constanţi ai soluţiei observând că într-un dreptunghi de dimensiuni $H * W$ poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un dreptunghi $W * H$. Acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri.

Acest algoritm are complexitatea $O(N*M log N)$ şi nu s-ar fi încadrat în timpul impus, deoarece marea parte a calculelor este efectuată în determinarea celui mai mare divizor comun a două numere. Având în vedere că numerele folosite sunt între $1$ şi $N$ respectiv între $1$ şi $M$, putem să precalculăm o matrice $CMMDC[X][Y]$, $1 ≤ X ≤ N$ şi $1 ≤ Y ≤ M$, în $O(N * M)$. Astfel, complexitatea soluţiei a fost redusă la $O(N * M)$. Mai putem optimiza factorii constanţi ai soluţiei observând că într-un triunghi de dimensiuni $H * W$ poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un triunghi $W * H$. Acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri.

h2(#concluzii). Concluzii