Tưới ruộng

Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều Độ khó: Dễ HSG Tin 9 TP.HCM 2018 Đánh dấu trên mảng 2 chiều

Đề bài

Tưới ruộng – FARM.* Trên khu đất ruộng hình chữ nhật, được chia thành từng thửa vuông đều nhau có cạnh là một đơn vị để cho các tá điền thuê lại trồng trọt. Tại một số thửa ruộng, bạn Bờm cho đào giếng để lấy nước tưới. Vì năm nay trời hạn nên mỗi giếng chỉ đủ nước để tưới cho các thửa ruộng xung quanh trong phạm vi bán kính 2 ô vuông đơn vị. Các tá điền không thể đưa nước đi xa vì họ không có dụng cụ cũng không đủ sức đưa đi.

Yêu cầu: hãy đếm xem có bao nhiêu thửa ruộng sẽ không tưới được.

Ví dụ: với diện tích ruộng $6 \times 9$ như hình bên dưới có 3 giếng nước tại các ô ở dòng 2 cột 6, dòng 3 cột 2 và dòng 5 cột 7. Các ô tô đen chính là những ô không thể tưới.

Dữ liệu vào: trong tập tin văn bản FARM.INP gồm:

• Dòng đầu là hai số nguyên dương $M$ và $N$ cách nhau một dấu cách cho biết kích thước khu đất $(1 < M, N \le 100)$;
• Dòng thứ hai là một số nguyên dương $K$ cho biết số giếng đã đào trên khu đất;
• Trên $K$ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương tương ứng với chỉ số dòng và cột của từng giếng đào trên khu đất, các số cách nhau một dấu cách. Chỉ số dòng được đánh số từ 1, tính từ trên xuống dưới của bảng. Chỉ số cột được đánh số từ 1, tính từ trái sang phải của bảng $(0 \le K \le 10^4)$.

Kết quả: ghi vào tập tin văn bản FARM.OUT gồm một số nguyên duy nhất là số thửa ruộng không thể tưới.

Ví dụ – input

6 9
3
2 6
3 2
5 7

Ví dụ – output

6

Lưu ý trên CLUE OJ: (1) bài này không nhập/xuất chuẩn mà đọc file FARM.INP, ghi file FARM.OUT đúng tên như đề thi; (2) mỗi bạn chỉ được nộp 1 lần duy nhất, nên hãy kiểm tra thật kỹ trước khi bấm nộp. Code trong bài dùng mẹo if (fopen("FARM.INP", "r")): có file thì đọc/ghi file, không có thì đọc bàn phím – in màn hình, nên vừa chạy thử trên máy vừa nộp bài được luôn.

Lời mở đầu

Bài 2 đề HSG Tin 9 TP.HCM năm 2018. Chỗ cần suy nghĩ duy nhất là hiểu cho đúng cụm từ "bán kính 2 ô"; hiểu đúng rồi thì bài là một bài đánh dấu trên mảng 2 chiều rất cơ bản. Vì chỉ được nộp 1 lần nên mình sẽ làm 2 cách để kiểm tra chéo nhau, và chạy thật cả 2 cách trên bộ test chính thức.

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ưởngHình vuông 5 × 5Cách 1Xét từng thửaCách 2Đánh dấu

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

Bộ test có 100 test. Đề không chia subtask, và thật ra mọi test đều nhỏ: $M, N \le 100$ và số giếng nhiều nhất chỉ 532 (đề cho phép tới $10^4$).

Test	M	N	K (số giếng)	Đáp án	Ghi chú
1 – 30	2 – 28	1 – 23	0 – 27	0 – 137	Nhỏ
31 – 60	1 – 48	5 – 54	2 – 75	12 – 1355	Vừa
61 – 100	1 – 100	3 – 100	0 – 532	18 – 4149	Lớn hơn (test 100 là 100 × 100)

Mấy điều đáng chú ý khi mình soi bộ test:

• Có 8 test với $K = 0$ (test 2, 4, 7, 10, 18, 19, 24, 84): không có giếng nào, đáp án là $M \times N$. Code phải xử lý được trường hợp này (vòng lặp đọc giếng chạy 0 lần).
• Đề ghi $1 < M, N$ nhưng có 5 test có $M = 1$ hoặc $N = 1$ (test 7, 10, 25, 56, 95) – khu đất chỉ là 1 hàng hoặc 1 cột. Code dùng max/min để cắt vùng tưới thì vẫn chạy đúng.
• Mọi giếng đều nằm trong khu đất và không có 2 giếng trùng vị trí.

Vì bộ test nhỏ nên cả 2 cách bên dưới (kể cả cách xét từng thửa) đều qua hết. Tuy vậy mình vẫn phân tích trường hợp xấu nhất theo đề ($K = 10^4$) để các bạn biết cách nào an toàn hơn khi đi thi.

Ý tưởng"Bán kính 2 ô" là hình vuông 5 × 5

Nhìn hình ví dụ: giếng ở dòng 3 cột 2 tưới được cả ô dòng 1 cột 4 (lệch 2 dòng và 2 cột, tức là đi chéo). Còn ô dòng 6 cột 1 không được tưới vì lệch tới 3 dòng. Vậy "bán kính 2 ô" ở đây nghĩa là:

Điều kiện được tưới

Thửa $(x, y)$ được giếng $(r, c)$ tưới khi và chỉ khi $|x - r| \le 2$ và $|y - c| \le 2$.
Tức là mỗi giếng tưới một hình vuông 5 × 5 có tâm là giếng (bị cắt bớt nếu giếng ở gần mép khu đất).

Mình kiểm tra lại ví dụ: giếng $(2, 6)$ tưới dòng 1–4, cột 4–8; giếng $(3, 2)$ tưới dòng 1–5, cột 1–4; giếng $(5, 7)$ tưới dòng 3–6, cột 5–9. Còn lại đúng 6 ô khô: ô $(1, 9)$, $(2, 9)$ và 4 ô $(6, 1)$ … $(6, 4)$ – khớp với hình ✓. Mình cũng đã kiểm tra cách hiểu này khớp với đáp án của cả 100 test.

Em nhập kích thước và vị trí các giếng rồi bấm Tiếp để xem từng giếng tưới vùng nào (ô xanh đậm là ô vừa được tưới thêm):

M N Các giếng (dòng cột, ...)

Ví dụ nhanh:

Cách 1Xét từng thửa ruộng – O(M·N·K)

Cách nghĩ trực tiếp nhất: với mỗi thửa $(x, y)$, duyệt qua tất cả $K$ giếng xem có giếng nào đủ gần không. Không có giếng nào thì thửa đó khô, tăng biến đếm.

C++▶ Chạy tay từng dòng codeCách 1: mỗi thửa ruộng duyệt qua mọi giếng, không giếng nào đủ gần thì thửa đó khô.

Dữ liệu vào (stdin) – sửa thoải mái6 9 3 2 6 3 2 5 7

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Biến wet đặt lại bằng false cho từng thửa. Gặp được 1 giếng đủ gần là break luôn, không cần xét các giếng còn lại.
2. Hàm abs lấy giá trị tuyệt đối, viết điều kiện $|x - r| \le 2$ và $|y - c| \le 2$ rất gọn.
3. Chỉ cần lưu toạ độ các giếng vào 2 mảng r[], c[], không cần mảng 2 chiều cho khu ruộng.

Không gian$O(K)$

Thời gian$O(M \cdot N \cdot K)$

Theo đề, trường hợp xấu nhất là $M = N = 100$, $K = 10^4$: khoảng $10^4 \times 10^4 = 10^8$ phép so sánh. Mình tự tạo thử một test như vậy (mọi giếng dồn vào 1 góc để hầu hết thửa ruộng phải xét hết $10^4$ giếng): bản C++ vẫn chạy khoảng 0,09 giây, nhưng bản Python thì mất hơn 7 giây – quá chậm.

Kết quả chạy thật cách 1: bản C++ đúng 100/100 test, chậm nhất khoảng 0.01 giây; bản Python đúng 100/100 test, chậm nhất khoảng 0.23 giây. Bộ test chính thức "hiền" hơn đề (nhiều nhất chỉ 532 giếng) nên cả Python cũng qua.

Cách 2Đánh dấu vùng tưới của từng giếng – O(25·K + M·N)

Đảo ngược cách nhìn: thay vì mỗi thửa đi tìm giếng, ta để mỗi giếng tự đánh dấu các thửa mà nó tưới được vào mảng wet. Mỗi giếng chỉ đánh dấu tối đa $5 \times 5 = 25$ ô. Cuối cùng đếm số ô chưa bị đánh dấu.

C++▶ Chạy tay từng dòng codeCách 2: mỗi giếng đánh dấu hình vuông 5 × 5 quanh nó, cuối cùng đếm ô chưa đánh dấu.

Dữ liệu vào (stdin) – sửa thoải mái6 9 3 2 6 3 2 5 7

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Phần dòng của hình vuông là từ $r - 2$ tới $r + 2$, nhưng phải cắt vào trong khu đất: max(1, r - 2) đến min(m, r + 2). Tương tự cho cột. Nhờ vậy giếng ở sát mép không làm ghi ra ngoài mảng.
2. Nhiều giếng có vùng tưới chồng lên nhau cũng không sao: ô đã true gán true lần nữa vẫn là true, không bị đếm trùng.
3. Mảng wet khai báo toàn cục nên ban đầu tất cả là false.

Không gian$O(M \cdot N)$

Thời gian$O(25K + M \cdot N)$

Với test xấu nhất tự tạo ở trên ($K = 10^4$) cách 2 chỉ tốn khoảng $25 \cdot 10^4 + 10^4$ phép gán: bản C++ chạy khoảng 0,01 giây, bản Python khoảng 0,04 giây.

Kết quả chạy thật cách 2: bản C++ đúng 100/100 test, chậm nhất khoảng 0.00 giây; bản Python đúng 100/100 test, chậm nhất khoảng 0.03 giây.

Mở rộng

Nếu bán kính tưới không phải 2 mà là một số $d$ lớn (ví dụ $d = 50$), mỗi giếng phải đánh dấu $(2d + 1)^2$ ô và cách 2 sẽ chậm lại. Khi đó có thể dùng mảng hiệu 2 chiều: mỗi giếng chỉ cộng/trừ ở 4 góc, cuối cùng lấy tổng tiền tố 2 chiều để biết ô nào được tưới ít nhất 1 lần – tổng cộng $O(K + M \cdot N)$. Kỹ thuật tổng tiền tố 2 chiều các bạn xem thêm ở bài Chọn quà cùng chương nhé.

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

Cách	Độ phức tạp	C++	Python	Test xấu nhất theo đề
1. Xét từng thửa	$O(M \cdot N \cdot K)$	100/100	100/100	C++ ổn, Python quá chậm
2. Đánh dấu 5 × 5	$O(25K + M \cdot N)$	100/100	100/100	Cả 2 đều rất nhanh

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). Vì đề chỉ cho nộp 1 lần, các bạn nên tự viết cả 2 cách rồi sinh test ngẫu nhiên so sánh với nhau trước khi nộp; và đừng quên đọc/ghi đúng tên file FARM.INP, FARM.OUT.

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 😇