h1(#matrice3). 'Matrice 3':problema/matrice3
 
Pentru a putea rezolva problema, trebuie să ştim întâi rezolva problema determinării laturii maxime a unui pătrat plin cu $0$ dintr-o matrice binară. Problema este foarte cunoscută şi se rezolvă cu ajutorul programării dinamice. Vom nota $C[i][j] = latura maximă a unui pătrat plin cu 0 cu colţul dreapta jos în (i, j)$. Pentru a calcula $C[i][j]$, avem nevoie de două informaţii precalculate: $A[i][j] = numărul de 0 consecutivi aflaţi pe linia i exact în stânga poziţiei (i, j)$ şi $B[i][j] = numărul de 0 consecutivi aflaţi pe coloana j exact înaintea poziţiei (i, j)$. Recurenţa devine $C[i][j] = min(C[i-1][j-1]+1, A[i][j], B[i][j])$. Dacă pentru fiecare din cele $Q$ întrebări, ar fi fost aplicată rezolvarea descrisă mai sus strict pe zona din matrice descrisă de întrebare, s-ar fi obţinut $30$ de puncte.
Pentru a rafina ideea descrisă anterior, trebuie sa ne găsim un mod eficient de tratare a unui query. Se observă că este semnificativ mai uşor să răspundem la următoarea întrebare: $În dreptunghiul determinat de celulele (x1, y1) (x2, y2), există un pătrat plin cu 0 de latură L?$ Răspunsul la această intrebare este echivalent cu un query de maxim în matricea $C$ calculată anterior, în dreptunghiul $(x1+L, y1+L) (x2, y2)$. Un astfel de pătrat există dacă şi numai dacă maximul respectiv este $≥ L$. Această observaţie ne duce la ideea de a căuta binar rezultatul pentru fiecare dintre cele $Q$ întrebări. Pentru a putea găsi maximul într-un dreptunghi în mod eficient (complexitate $O(1)$), putem folosi un 'RMQ':problema/rmq 2D a cărui construcţie prealabilă necesită complexitate timp şi spaţiu $O(N^2^log^2^N)$. Aşadar soluţia oficială are complexitate timp $O(N^2^log^2^N + QlogN)$.
Menţionăm că folosirea unui $RMQ 1D$ şi rezolvarea query-ului de maxim în complexitate $O(N)$, ar fi adus $60$ de puncte.

h1(#matrice3). 'Matrice 3':problema/matrice3