Hình vuông lớn nhất tổng nhỏ

Hướng tiếp cận

Bài toán yêu cầu tìm cạnh $k$ lớn nhất sao cho tồn tại một hình vuông $k\times k$ có tổng $\le S$. Hai kĩ thuật then chốt:

1. Tổng tiền tố 2D (2D prefix sum) để tính tổng của một sub-rectangle bất kì trong $O(1)$.
2. Chặt nhị phân (binary search) trên đáp án $k$, dựa trên một tính chất đơn điệu.

Nhận xét quan trọng

1. Đặt $\text{minSum}(k)=min$ tổng trên mọi hình vuông $k\times k$ trong $A$. Vì mọi phần tử của $A$ đều không âm, nên với bất kỳ hình vuông $k\times k$ nào, ta đều có thể "thu nhỏ" nó về một hình vuông $(k-1)\times (k-1)$ bằng cách bỏ bớt một hàng và một cột; tổng của hình vuông $(k-1)\times (k-1)$ không lớn hơn tổng của hình vuông $k\times k$. Do đó $\text{minSum}(k)\ge \text{minSum}(k-1)$ — hàm $\text{minSum}$ không giảm theo $k$.

2. Suy ra: tập các $k$ thoả mãn $\text{minSum}(k)\le S$ là một tiền tố $\{0,1,\dots ,k^{*}\}$. Ta có thể chặt nhị phân để tìm $k^{*}$.

3. Tổng của một hình vuông $k\times k$ tối đa là $250000·{10}^9=2.5·{10}^{14}$, vượt phạm vi $32$-bit. Phải dùng $64$-bit (long long) khi xây mảng tiền tố và khi tính hiệu.

Thuật toán

Bước 1. Xây mảng tiền tố $2$D: $P[i][j]={\sum }_{a\le i,b\le j}{A}_{a,b}$ với công thức

$$P[i][j]=P[i-1][j]+P[i][j-1]-P[i-1][j-1]+A_{i,j}.$$

Bước 2. Định nghĩa hàm fits(k): tồn tại hình vuông $k\times k$ với tổng $\le S$ hay không. Với mỗi vị trí góc trên-trái $(r,c)$ (với $r+k-1\le n$, $c+k-1\le m$), tổng hình vuông tính bằng

$$P[r+k-1][c+k-1]-P[r-1][c+k-1]-P[r+k-1][c-1]+P[r-1][c-1].$$

fits(k) trả về true khi và chỉ khi giá trị nhỏ nhất trong các tổng đó $\le S$. Phép kiểm tra này chạy trong $O((n-k+1)(m-k+1))\le O(nm)$.

Bước 3. Chặt nhị phân trên $k\in [0,min(n,m)]$: tìm $k$ lớn nhất sao cho fits(k) = true.

Độ phức tạp

• Thời gian: $O(nm\log min(n,m))$. Với $n=m=500$, đây là khoảng $500·500·9\approx 2,25·{10}^6$ phép tính — rất nhanh.
• Bộ nhớ: $O(nm)$ cho mảng tiền tố.