Hình vuông
Đề bài
Phú ông rất giàu có, đất của Phú ông trải dài khắp nơi. Vừa qua có chính sách dồn điền đổi thửa, Phú ông đã đổi để được mảnh đất hình chữ nhật. Sau khi khảo sát, Phú ông đã chia mảnh đất thành $m$ dòng, $n$ cột. Giao giữa dòng $i$ và cột $j$ là ô vuông đơn vị có độ cao là một số nguyên $A_{ij}$ (với $A_{ij} < 0$ thì chỗ đất đó là một hố vũng). Độ bằng phẳng của một mảnh đất là số độ cao khác nhau của các ô vuông đơn vị trong mảnh đất đó.
Phú ông muốn tìm một mảnh đất hình vuông có kích thước $k \times k$ trên mảnh đất của mình để xây biệt thự sao cho tổng các độ cao trong hình vuông là nhỏ nhất và hình vuông thoả mãn đồng thời:
- Các cạnh của hình vuông song song với các cạnh tương ứng của mảnh đất hình chữ nhật;
- Độ bằng phẳng của hình vuông là nhỏ nhất.
Yêu cầu: em hãy giúp Phú ông tính tổng độ cao nhỏ nhất trong hình vuông kích thước $k \times k$ thoả mãn yêu cầu trên.
Dữ liệu vào: đọc từ file văn bản SQUARE.INP gồm:
- Dòng 1 ghi 3 số nguyên dương $m, n, k$ $(k \le m, n \le 800)$ lần lượt là kích thước mảnh đất, kích thước hình vuông của Phú ông;
- $m$ dòng sau, mỗi dòng ghi $n$ số nguyên $A_{ij}$ $(|A_{ij}| \le 10^6)$ là độ cao của ô vuông đơn vị giao giữa dòng $i$ và cột $j$.
Các số trên cùng dòng cách nhau ít nhất 1 khoảng trống.
Kết quả ra: ghi ra file văn bản SQUARE.OUT một số là tổng độ cao nhỏ nhất trong hình vuông kích thước $k \times k$ thoả mãn yêu cầu bài toán.
Ràng buộc:
- Subtask 1: có 30% số test ứng với $m, n, k \le 20$;
- Subtask 2: có 30% số test ứng với $20 < m, n, k \le 100$;
- Subtask 3: có 40% số test ứng với $100 < m, n, k \le 800$.
4 5 3
-1 4 3 2 -2
0 2 3 2 1
1 2 4 4 3
-1 -1 0 4 1263 4 2
-1 1 0 2
1 1 2 2
-1 -1 1 20Giải thích ví dụ 1: có 6 hình vuông $3 \times 3$. Hình vuông góc trên trái ở dòng 1, cột 2 gồm các số $4, 3, 2 \,/\, 2, 3, 2 \,/\, 2, 4, 4$ chỉ có 3 độ cao khác nhau $\{2, 3, 4\}$ – ít nhất trong 6 hình vuông (các hình còn lại có 5 hoặc 6 độ cao khác nhau), nên đáp án là tổng của nó: $26$. Để ý là có hình vuông tổng chỉ bằng $10$ nhưng không được chọn vì nó "gồ ghề" hơn.
Giải thích ví dụ 2: có 3 hình vuông $2 \times 2$ cùng có 2 độ cao khác nhau (ít nhất), tổng của chúng là $2$, $6$ và $0$ → chọn tổng nhỏ nhất là $0$.
SQUARE.INP và ghi file SQUARE.OUT. Code bên dưới dùng mẹo if(fopen("SQUARE.INP", "r")): có file thì đọc/ghi file, không có thì đọc bàn phím – in màn hình, nên nộp ở đâu cũng được.Lời mở đầu
Hai ví dụ trên cho thấy thứ tự ưu tiên của đề: trước hết độ bằng phẳng (số độ cao khác nhau) phải nhỏ nhất, sau đó trong các hình vuông "phẳng nhất" mới chọn tổng nhỏ nhất. Vậy với mỗi hình vuông $k \times k$ ta cần 2 con số: số giá trị khác nhau và tổng. Tổng thì dễ, cái khó là đếm số giá trị khác nhau cho thật nhanh – và đây chính là chỗ cửa sổ trượt của chương 14 phát huy tác dụng.
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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 22 test (không phải 100 test như nhiều bài khác), mình chia theo kích thước bảng đúng như 3 subtask của đề. Đề ghi "$20 < m, n, k$" nhưng thật ra chỉ cần hiểu là bảng lớn dần: test 17 có $k = 1$, test 4 có bảng chỉ 3 hàng.
| Test | m × n | k | Độ cao | Đáp án |
|---|---|---|---|---|
| 1 – 9 | 3..18 × 5..18 | 1 – 12 | -10 … 39 | -10 … 2158 |
| 10 – 18 | 32..99 × 43..94 | 1 – 75 | -100 … 899 | -4968 … 2222898 |
| 19 – 22 | 127..574 × 167..291 | 84 – 186 | -100000 … 31765 | -1855893856 … 531430365 |
| Subtask | Điều kiện (đề) | Test thật | Cách 1 (C++) | Cách 2 (C++) |
|---|---|---|---|---|
| 1 | $m, n, k \le 20$ | 1 – 9 (9 test) | 9/9 | 9/9 |
| 2 | $20 < m, n, k \le 100$ | 10 – 18 (9 test) | 9/9 | 9/9 |
| 3 | $100 < m, n, k \le 800$ | 19 – 22 (4 test) | 3/4 | 4/4 |
Vài điểm đáng chú ý: test 1 có cùng kích thước với ví dụ 1 nhưng số liệu khác (đáp án 21). Test 12 và 13 giống hệt nhau. Test lớn nhất là test 22 với bảng $574 \times 277$, $k = 149$, và mọi độ cao đều âm (từ $-100000$ đến $-67233$) – đáp án là $-1855893856$, rất sát giới hạn $-2^{31} = -2\,147\,483\,648$ của int (mình thử đổi sang int thì test này vẫn lọt, nhưng theo ràng buộc đề tổng có thể tới $6{,}4 \cdot 10^{11}$), nên tổng phải dùng long long. Không có test nào đạt $m = n = 800$, nhưng code vẫn phải chịu được trường hợp đó.
Ý tưởngMảng đếm + cửa sổ trượt sang phải
Để đếm số độ cao khác nhau trong một hình vuông, mình dùng mảng đếm cnt[h] = số ô có độ cao $h$ trong hình vuông, cùng biến d = số độ cao đang có mặt:
- Thêm một ô độ cao $h$:
cnt[h]++; nếucnt[h]vừa từ 0 lên 1 thì đây là độ cao mới →d++. - Bỏ một ô độ cao $h$:
cnt[h]--; nếucnt[h]về 0 thì độ cao này không còn →d--.
Độ cao có thể âm (tới $-10^6$) nên mình cộng thêm $OFF = 10^6$ để làm chỉ số: độ cao $h$ được đếm ở ô cnt[h + OFF], mảng cỡ $2 \cdot 10^6 + 1$ phần tử.
Hai hình vuông cạnh nhau (góc trên trái $(i, j)$ và $(i, j+1)$) có chung tới $k \times (k-1)$ ô, chỉ khác nhau đúng 1 cột. Vậy thay vì đếm lại từ đầu, ta trượt cửa sổ sang phải: bỏ $k$ ô của cột trái cũ, thêm $k$ ô của cột phải mới – chỉ $2k$ thao tác thay vì $k^2$.
Em sửa bảng (các hàng cách nhau dấu phẩy) và $k$ rồi bấm Tiếp để xem cửa sổ trượt: ô đỏ là cột vừa bị bỏ, ô xanh là cột vừa được thêm, bên dưới là mảng đếm cnt:
Cách 1Vét cạn: đếm lại từng hình vuông – O(m·n·k²)
Thử mọi góc trên trái $(i, j)$; với mỗi hình vuông, duyệt $k^2$ ô để vừa cộng tổng vừa đếm số độ cao khác nhau bằng mảng cnt. Xét xong thì trả các ô cnt vừa dùng về 0 (chỉ duyệt lại $k^2$ ô đó, không memset cả mảng $2 \cdot 10^6$ phần tử – làm vậy sẽ rất chậm).
- Dòng
if(cnt[a[x][y] + OFF] == 0) d++;đặt trướccnt[...]++: ô có độ cao chưa từng gặp trong hình vuông này thì tăng số độ cao khác nhau. - Điều kiện cập nhật
d < bestD || (d == bestD && s < bestS)chính là so sánh cặp $(d, s)$ theo thứ tự ưu tiên của đề.bestDkhởi tạo bằngINT_MAXnên hình vuông đầu tiên luôn được nhận. - Tổng có thể tới $800^2 \cdot 10^6 = 6{,}4 \cdot 10^{11}$ (hoặc âm cỡ đó) nên
s,bestSphải làlong long. Bộ test có hẳn một test đáp án là $-1\,855\,893\,856$, chỉ cách giới hạn củaint($-2\,147\,483\,648$) một chút – bộ test này dùngintvẫn lọt, nhưng theo ràng buộc của đề thìintchắc chắn tràn. - Bản Python dùng
setcho gọn:len(set(cells))là số độ cao khác nhau, rồi so sánh tuple(d, s)trực tiếp.
Cách 2Cửa sổ trượt – O(m·n·k)
Với mỗi dải hàng $i \dots i+k-1$: dựng cửa sổ đầu tiên (cột $1 \dots k$) bằng $k^2$ lần add, rồi trượt sang phải từng cột. Hết dải thì rem các ô của cửa sổ cuối cùng để mảng cnt sạch sẽ cho dải sau. Hai hàm nhỏ add(v) và rem(v) giữ đúng 2 đại lượng d (số độ cao khác nhau) và s (tổng) của cửa sổ.
- Vòng
for(int j = 1; ; j++)không có điều kiện dừng ở đầu: mỗi vòng xét cửa sổ hiện tại trước, rồi mới kiểm traif(j + k > n) break;– nếu cột tiếp theo $j + k$ đã vượt quá $n$ thì không trượt được nữa. - Khi trượt từ cột $j$ sang $j+1$: cột bị bỏ là cột $j$, cột được thêm là cột $j + k$. Mỗi hàng $x$ của dải làm 1
rem+ 1add. - Số thao tác cho mỗi dải là $k^2 + 2k(n-k) + k^2$, có $m - k + 1$ dải → tổng cỡ $O(m \cdot n \cdot k)$. Với $m = n = 800$ trường hợp xấu nhất khoảng $2 \cdot 10^8$ phép tính đơn giản – vẫn chạy kịp 1 giây.
- Bản Python dùng
dictlàm mảng đếm,len(cnt)chính là số độ cao khác nhau (khi đếm về 0 thìdelkhoá đó đi).
Tổng kếtSo sánh 2 cách
| Cách | Độ phức tạp | C++ | Python | Subtask đạt |
|---|---|---|---|---|
| 1. Vét cạn | $O(m n k^2)$ | 21/22 | 18/22 | 1, 2 (và 3/4 test của subtask 3 với C++) |
| 2. Cửa sổ trượt | $O(m n k)$ | 22/22 | 21/22 | Toàn bộ (C++) |
d đếm số giá trị khác nhau, thêm/bỏ từng phần tử khi cửa sổ trượt" là khuôn dùng lại cho rất nhiều bài trong chương, ví dụ bài Đếm số bức ảnh cũng trong contest này.
Nhận xét
Đăng nhận xét