Matrice 3

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 2D a cărui construcţie prealabilă necesită complexitate timp şi spaţiu O(N²log²N). Aşadar soluţia oficială are complexitate timp O(N²log²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.