Đếm số bức ảnh
Đề bài
Vậy là khu vườn của Đang đã hoàn tất! Khu vườn có thể được biểu diễn dưới dạng một hình chữ nhật kích thước $n \times m$ ô vuông. Các hàng được đánh số $1$ tới $n$ từ trên xuống dưới, và các cột được đánh số $1$ tới $m$ từ trái sang phải, ô vuông nằm trên hàng $i$ cột $j$ kí hiệu là ô $(i, j)$ và trồng một loại hoa $f_{(i,j)}$.
Đang muốn chia sẻ khu vườn của mình với các bạn khác. Để làm vậy, anh sẽ chụp một bức ảnh của khu vườn để đăng lên Facebook. Và với máy ảnh hiện có của mình, Đang sẽ chụp được một khu vực hình vuông kích thước $k \times k$. Ngoài ra, Đang cũng phát hiện ra nếu bức ảnh có nhiều hơn $x$ loại hoa khác nhau, nó sẽ trở nên loạn và rất khó nhìn. Tất nhiên anh không muốn điều này xảy ra.
Đang muốn biết, có bao nhiêu bức ảnh mà anh có thể chụp? Lưu ý, bức ảnh phải nằm hoàn toàn bên trong khu vườn. Nói cách khác, mọi ô vuông trong bức ảnh phải chứa một loại hoa.
Yêu cầu: hãy đếm số bức ảnh khác nhau Đang có thể chụp nhé.
Dữ liệu:
- Dòng đầu chứa bốn số nguyên $n, m, k, x$ $(1 \le n, m, k \le 800,\ 1 \le x \le n \times m)$ lần lượt là kích thước khu vườn, kích thước bức ảnh và số loại hoa khác nhau tối đa trong một bức ảnh.
- $n$ dòng sau, dòng thứ $i$ chứa $m$ số nguyên $f_{(i,1)},$ $f_{(i,2)},$ $\dots,$ $f_{(i,m)}$ $(1 \le f_{(i,j)} \le 10^5)$ mô tả khu vườn.
Kết quả: số bức ảnh thoả mãn yêu cầu của Đang.
Ràng buộc:
- Có 30% số test thoả mãn $1 \le n, m, k \le 20$;
- Có 30% số test thoả mãn $1 \le n, m, k \le 100$;
- 40% số test không có ràng buộc gì thêm.
4 4 2 2
1 1 2 3
5 5 1 1
2 2 2 2
4 2 1 35Giải thích: toạ độ góc trên trái của tất cả bức ảnh thoả mãn là: $(1,1)$, $(2,1)$, $(2,3)$, $(3,1)$, $(3,2)$. Chẳng hạn bức ảnh góc $(1,1)$ gồm $1, 1, 5, 5$ – chỉ 2 loại hoa; còn bức ảnh góc $(1,2)$ gồm $1, 2, 5, 1$ có 3 loại hoa $> x = 2$ nên không được.
Lời mở đầu
Bài này là "anh em sinh đôi" của bài Hình vuông (Phú ông tìm mảnh đất phẳng nhất) trong cùng contest: vẫn là đếm số giá trị khác nhau trong mọi hình vuông $k \times k$, chỉ khác là lần này ta đếm xem bao nhiêu hình vuông có số loại hoa $\le x$. Nhưng bộ test của bài này lớn hơn hẳn (tới $800 \times 800$), nên mình sẽ đi qua 3 cách: vét cạn → cửa sổ trượt → cửa sổ trượt đã tối ưu hằng số. Cách thứ 2 đúng thuật toán mà vẫn có thể bị quá thời gian vì một lý do rất "phần cứng", các bạn đọc kỹ nhé.
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ó 100 test, chia đúng 3 subtask như đề: 30 test nhỏ, 30 test vừa, 40 test lớn (20 test cuối đều là $800 \times 800$). Ở subtask 1 loại hoa chỉ từ 1 đến 20; từ subtask 2 trở đi loại hoa ngẫu nhiên tới $10^5$ – gần như ô nào cũng khác loại với ô bên cạnh.
| Test | n × m | k | x | Số loại hoa (cả vườn) | Đáp án |
|---|---|---|---|---|---|
| 1 – 30 | 1..20 × 2..20 | 1 – 18 | 1 – 20 | 4 – 20 | 2 – 400 |
| 31 – 60 | 81..100 × 80..100 | 1 – 95 | 932 – 4433 | 3377 – 4731 | 36 – 9801 |
| 61 – 100 | 704..800 × 702..800 | 6 – 323 | 797 – 32634 | 70899 – 78504 | 158460 – 580644 |
| Subtask | Điều kiện (đề) | Test thật | Cách 1 | Cách 2 | Cách 3 |
|---|---|---|---|---|---|
| 1 | $n, m, k \le 20$ | 1 – 30 | 30/30 | 30/30 | 30/30 |
| 2 | $n, m, k \le 100$ | 31 – 60 | 30/30 | 30/30 | 30/30 |
| 3 | $n, m, k \le 800$ | 61 – 100 | 3/40 | 27/40 | 40/40 |
(số test đúng của bản C++ mỗi cách)
Có 10 test với $k = 1$ (mọi ô đều là một bức ảnh hợp lệ), và 94 test mà mọi vị trí đều chụp được (vì $x$ đủ lớn). Đáp án lớn nhất là $580\,644 = 762^2$ (test 100), vừa kiểu int.
Ý tưởngMảng đếm + cửa sổ trượt
Để biết một bức ảnh có bao nhiêu loại hoa, dùng mảng đếm cnt[v] = số ô trồng hoa loại $v$ trong bức ảnh (loại hoa $\le 10^5$ nên mảng chỉ cỡ $10^5$), cùng biến d = số loại hoa đang có:
- Thêm một ô hoa $v$:
cnt[v]++, nếucnt[v]vừa từ 0 thành 1 thì có thêm 1 loại →d++. - Bỏ một ô hoa $v$:
cnt[v]--, nếucnt[v]về 0 thì mất 1 loại →d--.
Hai bức ảnh cạnh nhau chỉ khác nhau đúng 1 cột (hoặc 1 hàng). Thay vì đếm lại $k^2$ ô, ta trượt khung ảnh: bỏ $k$ ô cũ, thêm $k$ ô mới. Mỗi vị trí, nếu d <= x thì tăng đáp án.
Em sửa khu vườn, $k$, $x$ rồi bấm Tiếp để xem khung ảnh trượt sang phải: ô đỏ là cột vừa bỏ, ô xanh là cột vừa thêm:
Cách 1Vét cạn từng bức ảnh – O(n·m·k²)
Thử mọi góc trên trái $(i, j)$, duyệt $k^2$ ô để đếm số loại hoa bằng mảng cnt, rồi duyệt lại $k^2$ ô đó để trả cnt về 0 (không memset cả mảng mỗi lần).
- Có $(n-k+1)(m-k+1)$ bức ảnh, mỗi bức tốn $2k^2$ thao tác. Với $n = m = 100$ thì nhiều nhất cỡ $2 \cdot 50^2 \cdot 50^2 \approx 1{,}25 \cdot 10^7$ – rất nhanh. Nhưng với $n = m = 800$, $k \approx 270$ thì lên tới hàng chục tỉ.
- Đáp án tối đa là $800^2 = 640\,000$,
intlà đủ; mình đểlong longcho quen tay. - Bản Python dùng
set: gom các lát cắt hàng của bức ảnh vào một set rồi lấylen.
Cách 2Cửa sổ trượt sang phải – O(n·m·k)
Với mỗi dải hàng $i \dots i+k-1$: dựng khung ảnh đầu tiên (cột $1 \dots k$), rồi trượt sang phải từng cột. Mỗi bước trượt chỉ có $k$ lần rem (cột $j$) và $k$ lần add (cột $j + k$). Hết dải thì rem khung cuối cùng để cnt về 0.
- Vòng
for(int j = 1; ; j++): mỗi vòng đếm khung hiện tại trước (if(d <= x) ans++;), rồi nếuj + k > m(không còn cột để thêm) thìbreak, ngược lại mới trượt. - Tổng số thao tác: $(n-k+1) \cdot \big(2k^2 + 2k(m-k)\big)$ $\approx 2 (n-k+1) \cdot m \cdot k$. Tệ nhất khi $k \approx 270$ – $290$ với $n = m = 800$: khoảng $2 \cdot 10^8$ lần
add/rem.
Cách 3Cửa sổ trượt tối ưu hằng số – 100%
Vẫn là cửa sổ trượt, cùng độ phức tạp, nhưng mình sửa 2 chỗ nhỏ:
if(cnt[v] == 1) lúc đúng lúc sai không theo quy luật nào. CPU luôn "đoán trước" nhánh của if để chạy cho nhanh; đoán sai thì phải bỏ hết việc đã làm và chạy lại (branch misprediction), mỗi lần mất cỡ 15–20 chu kỳ. Viết d += (cnt[v]++ == 0); thì biểu thức so sánh cho 0 hoặc 1 và được cộng thẳng vào d – không còn nhánh nào để đoán sai.f[i][1], f[i][2], ... nằm liền nhau trong bộ nhớ. Khi trượt xuống, ta bỏ cả một đoạn hàng $f[i][j..j+k-1]$ và thêm đoạn $f[i+k][j..j+k-1]$ – đọc liền một mạch, rất hợp với bộ nhớ đệm (cache). Còn trượt sang phải thì phải nhảy qua $k$ hàng khác nhau để lấy 1 cột.cnt[v]++ == 0: so sánh giá trị cũ củacnt[v]với 0 (toán tử++viết sau), rồi mới tăng. Đúng → biểu thức bằng 1 →dtăng 1.--cnt[v] == 0: giảmcnt[v]trước rồi so sánh với 0. Về 0 →dgiảm 1.- Mình đã đo riêng từng thay đổi trên 20 test lớn nhất: chỉ bỏ
if(vẫn trượt ngang) là đã xuống khoảng 0,5 giây; chỉ đổi sang trượt dọc (vẫn cóif) thì gần như không đổi (~1,1 giây). Vậy thủ phạm chính của cách 2 là đoán sai nhánh, còn trượt dọc giúp thêm một chút.
if không cứu được Python, nên mình không viết thêm bản Python cho cách 3.Tổng kếtSo sánh 3 cách
| Cách | Độ phức tạp | C++ | Python | Subtask đạt |
|---|---|---|---|---|
| 1. Vét cạn | $O(n m k^2)$ | 63/100 | 60/100 | 1, 2 |
| 2. Trượt ngang | $O(n m k)$ | 87/100 | 60/100 | 1, 2 và phần lớn subtask 3 |
| 3. Trượt dọc, không if | $O(n m k)$ | 100/100 | – | Toàn bộ |