Hình vuông con

Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều Độ khó: Trung bình Mảng 2 chiều Tổng tiền tố 2 chiều

Đề bài

Bài 5. Hình vuông con

Cho lưới ô vuông $A$ kích thước $N \times N$. Các dòng được đánh số $1$ đến $N$ từ trên xuống dưới, các cột được đánh số $1$ đến $N$ từ trái qua phải. Ô nằm trên giao giữa dòng $i$ và cột $j$ được gọi là ô $(i, j)$ và trên đó có ghi một số nguyên dương $A_{ij}$ $(1 \le i, j \le N)$.

Yêu cầu: hãy lập trình chọn một ô vuông con có kích thước $K \times K$ có tổng giá trị của tất cả các ô của hình vuông con là lớn nhất.

Input: đọc từ file HV.INP:

• Dòng đầu tiên chứa hai số nguyên dương $N, K$ $(N \le 10^3, K \le N)$.
• Dòng thứ $i$ trong số $N$ dòng tiếp theo chứa $N$ số nguyên dương, số thứ $j$ là $A_{ij}$ $(A_{ij} \le 10^3)$.

Output: ghi ra file HV.OUT gồm một dòng duy nhất ghi một số nguyên dương là tổng giá trị lớn nhất theo yêu cầu đề ra.

Ví dụ – input

4 3
1 9 1 1
9 9 9 9
1 9 9 9
1 9 9 14

Ví dụ – output

86

Giải thích ví dụ: hình vuông con $3 \times 3$ ở góc dưới phải (dòng 2–4, cột 2–4) có tổng $9 \cdot 8 + 14 = 86$, lớn nhất trong 4 hình vuông con $3 \times 3$ của bảng.

Lưu ý trên CLUE OJ: bài đọc file HV.INP, ghi file HV.OUT. Code bên dưới dùng mẹo if (fopen("HV.INP", "r")): có file thì đọc/ghi file, không có thì đọc bàn phím – in màn hình.

Lời mở đầu

Đây là bài "kinh điển" nhất để học tổng tiền tố 2 chiều: tính tổng của rất nhiều hình vuông con trên một bảng số. Mình đi từ cách vét cạn cộng từng ô (ăn được các test nhỏ) rồi nâng lên cách tiền tố 2 chiều đạt điểm tối đa. Bạn nào đã làm bài Chọn quà cùng chương sẽ thấy hai bài là "anh em ruột".

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngTrượt khungCách 1Vét cạnCách 2Tiền tố 2D

Bộ testBộ test chính thức có gì?

Bộ test có 100 test. Đề không ghi subtask, nhưng bộ test chia rõ 2 mức: 30 test đầu có $n \le 10$, 70 test sau có $n$ từ 131 tới 1000 (20 test cuối đều $n = 1000$). Mọi số trong bảng đều là số nguyên dương từ 1 đến 999.

Test	n	k	Giá trị ô	Đáp án	Ghi chú
1 – 30	4 – 10	2 – 8	1 – 20	61 – 719	Nhỏ, kiểm tra tay được
31 – 80	131 – 999	1 – 809	1 – 999	999 – 133343221	Ngẫu nhiên, n tới 1000
81 – 100	1000	2 – 968	1 – 999	3789 – 190011046	Lớn nhất: n = 1000

Mức	Điều kiện	Test	Cách đạt
Nhỏ	$n \le 10$	1 – 30	Cách 1, Cách 2
Lớn	$131 \le n \le 1000$	31 – 100	Cách 2 (cách 1 chỉ qua khi $k$ nhỏ hoặc gần $n$)

Đáp án lớn nhất là $190011046$ (test 83, $n = 1000$, $k = 968$) – vẫn vừa kiểu int, nhưng nếu đề cho số lớn hơn thì tổng có thể vượt $2^{31}$, nên mình dùng long long. Có cả test $k = 1$ (đáp án là số lớn nhất của bảng) và test $k = n$ (chỉ có 1 hình vuông là cả bảng).

Ý tưởngTrượt khung k × k qua mọi vị trí

Một hình vuông con $k \times k$ được xác định bởi góc trên trái $(i, j)$ với $1 \le i, j \le n - k + 1$, nên có tất cả $(n - k + 1)^2$ hình vuông con. Ta chỉ việc tính tổng từng hình và lấy giá trị lớn nhất. Câu hỏi duy nhất là tính tổng một hình vuông nhanh tới mức nào.

Em sửa bảng số, chọn $k$ rồi bấm Tiếp để xem khung $k \times k$ trượt qua bảng. Bên dưới là bảng tiền tố $s$ với 4 ô dùng để tính nhanh tổng của khung đang xét (xanh mang dấu +, đỏ mang dấu −):

k Bảng (các hàng cách nhau dấu phẩy)

Ví dụ nhanh:

Cách 1Vét cạn: cộng từng ô – O(n²·k²)

Với mỗi góc trên trái $(i, j)$, dùng 2 vòng lặp nữa cộng $k^2$ ô của hình vuông.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi góc trên trái, cộng từng ô của hình vuông k × k – O(n²·k²).

Dữ liệu vào (stdin) – sửa thoải mái4 3 1 9 1 1 9 9 9 9 1 9 9 9 1 9 9 14

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Điều kiện i + k - 1 <= n đảm bảo hàng cuối của hình vuông (hàng $i + k - 1$) vẫn nằm trong bảng; tương tự cho cột.
2. Tổng lớn nhất có thể tới $n^2 \cdot \max a$ nên mình dùng long long cho biến tổng (với bộ test này đáp án lớn nhất khoảng $1{,}9 \cdot 10^8$ vẫn vừa int, nhưng dùng long long cho chắc).

Không gian$O(n^2)$

Thời gian$O((n-k+1)^2 \cdot k^2)$

Số phép cộng là $(n - k + 1)^2 \cdot k^2$, lớn nhất khi $k \approx n/2$: với $n = 1000$ là khoảng $500^2 \cdot 500^2 = 6{,}25 \cdot 10^{10}$ – quá chậm. Nhưng khi $k$ rất nhỏ hoặc $k$ gần bằng $n$ thì số phép tính lại ít.

Kết quả chạy thật cách 1: bản C++ đúng 84/100 test – qua hết 30 test nhỏ và các test lớn có $k$ nhỏ (hoặc $k$ gần $n$); 16 test bị quá thời gian (test 31, 41, 43, 44, 45, 50, 59, 64, 76, 78, 79, 86, 88, 91, 92, 100). Bản Python đúng 50/100 test.

Cách 2Tổng tiền tố 2 chiều – O(n²)

Gọi $s[i][j]$ là tổng các số trong hình chữ nhật từ ô $(1, 1)$ đến ô $(i, j)$. Bảng này tính ngay khi đọc:

Xây bảng tiền tố

$$s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]$$

Lần này mình chọn $(i, j)$ là góc dưới phải của hình vuông con (với $k \le i, j \le n$) cho công thức gọn hơn: hình vuông gồm các hàng $i - k + 1 \dots i$, các cột $j - k + 1 \dots j$, và

Tổng hình vuông k × k có góc dưới phải (i, j)

$$sum = s[i][j] - s[i-k][j] - s[i][j-k] + s[i-k][j-k]$$ Lấy cả hình lớn $(1,1) \to (i, j)$, bỏ phần phía trên, bỏ phần bên trái; góc trên trái bị bỏ 2 lần nên cộng lại 1 lần.

C++▶ Chạy tay từng dòng codeCách 2: xây bảng tiền tố s khi đọc, mỗi hình vuông chỉ cần 4 phép cộng trừ – O(n²).

Dữ liệu vào (stdin) – sửa thoải mái4 3 1 9 1 1 9 9 9 9 1 9 9 9 1 9 9 14

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không cần lưu mảng a: đọc số nào thì cộng luôn vào s[i][j].
2. Mảng s kiểu long long khai báo toàn cục (khoảng 8 MB), hàng 0 và cột 0 bằng 0 làm "lề" cho công thức.
3. Bản Python: mỗi hàng của $s$ = hàng trên cộng tổng dồn của hàng hiện tại; khi tính đáp án, với mỗi $i$ lấy hiệu 2 hàng d = s[i] - s[i - k] rồi max(d[j] - d[j - k]) bằng map cho nhanh.

Không gian$O(n^2)$

Thời gian$O(n^2)$

Kết quả chạy thật cách 2: bản C++ đúng 100/100 test, chậm nhất khoảng 0.08 giây (chủ yếu là thời gian đọc $10^6$ số). Bản Python đúng 100/100 test, chậm nhất khoảng 0.41 giây.

Tổng kếtSo sánh 2 cách

Cách	Độ phức tạp	C++	Python	Mức đạt
1. Vét cạn	$O(n^2 k^2)$	84/100	50/100	Test nhỏ + test lớn có k nhỏ
2. Tiền tố 2D	$O(n^2)$	100/100	100/100	Toàn bộ

Ghi chú của mình: tất cả code trong bài đều được chấm thật trên toàn bộ 100 test chính thức (giới hạn 1 giây, đo bằng thời gian CPU). Công thức tiền tố 2 chiều dùng chung cho mọi bài "tổng hình chữ nhật con", các bạn nên tự viết lại vài lần cho thuộc.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇