Tuyển sinh 🎓 Mình nhận đào tạo lập trình giải thuật thi đấu: thi vào lớp 10 chuyên tin · thi học sinh giỏi tin học cấp tỉnh/thành · thi vào đội tuyển quốc gia · Olympic tin học sinh viên / ICPC · phỏng vấn thuật toán. Bấm vào đây để xem thông tin khóa học → Xem khóa học
Việt Nam Sơn
ZaloĐăng ký họcNhắn Zalo cho thầy

Chọn quà

Chọn quà
Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều Độ khó: Trung bình HSG Tin 9 TP.HCM 2022 Tổng tiền tố 2 chiều

Đề bài

Để khích lệ học sinh tích cực học tập, cô giáo lớp An dùng các nhãn dán khen thưởng khi tổ chức các hoạt động trên lớp. Cuối năm, cô khen thưởng cho các bạn tích lũy được nhiều nhãn. Với sự nỗ lực, An đã tích lũy được $K$ nhãn.

Cô chuẩn bị một khung lưới hình chữ nhật có kích thước $D \times R$. Khung lưới này có $D$ đường ngang và $R$ đường dọc tạo thành $(D-1) \times (R-1)$ hình vuông nhỏ có chiều dài cạnh là 1 đơn vị. Các món quà được treo tại các mối nối giao nhau của những đường ngang và đường dọc trên lưới. Tại một mối nối có thể không có quà hoặc có nhiều nhất một món quà.

Để nhận quà, An được phát cho một khung vợt hình vuông có kích thước $K \times K$ (cách tính đơn vị như khung lưới). An đặt vợt trên khung lưới sao cho 4 cạnh của vợt phải nằm hoàn toàn trên các đường ngang, đường dọc của khung lưới. Khi đó An sẽ nhận các món quà nằm hoàn toàn bên trong 4 cạnh của vợt (các món quà nằm trên cạnh của vợt sẽ không được tính). Bạn hãy giúp An xác định số lượng lớn nhất các món quà mà An có thể nhận.

Yêu cầu: viết chương trình cho biết số lượng món quà lớn nhất mà An có thể nhận khi đặt vợt trên khung lưới.

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

  • Dòng đầu tiên chứa 3 số nguyên $D, R, K$ $(3 \le K \le D, R \le 1000)$ cách nhau một khoảng trắng.
  • Trên $D$ dòng tiếp theo, mỗi dòng chứa $R$ kí tự mô tả hình ảnh khung lưới với các món quà treo trên đó. Kí tự '*' cho biết vị trí một món quà, kí tự '.' cho biết vị trí một mối nối trên khung lưới.

Kết quả: ghi ra tập tin văn bản CHONQUA.OUT một số nguyên cho biết số lượng món quà lớn nhất mà An có thể nhận khi đặt vợt trên khung lưới để nhận quà.

Ràng buộc: 50% test ứng với 50% số điểm của bài có $3 \le D, R \le 100$.

Ví dụ – input
7 6 4
......
.*.*.*
......
.*.*..
..*...
..*...
*....*
Ví dụ – output
2

Chú thích ví dụ (hình trong đề): một cách đặt vợt giúp An lấy tối đa 2 món quà. Lưu ý không tính những món quà nằm trên cạnh của vợt.

......
.*.*.*
+--+..
|*.|..
|.*|..
+--+..
*....*

Lưu ý trên CLUE OJ: bài này đọc/ghi file CHONQUA.INP / CHONQUA.OUT đúng như đề thi. Code bên dưới dùng mẹo if (fopen(...)): có file thì đọc/ghi file, không có thì đọc bàn phím – in màn hình, nên chạy thử trên máy hay nộp bài đều được.

Lời mở đầu

Đây là bài 3 trong đề thi học sinh giỏi Tin học lớp 9 TP.HCM năm 2022. Đọc đề thì hơi rối vì có "đường ngang", "đường dọc", "mối nối", "khung vợt"... nhưng gỡ ra thì bài chỉ là: tìm hình vuông con có nhiều dấu * nhất trong một bảng ký tự. Bài này là ví dụ kinh điển để các bạn làm quen với tổng tiền tố 2 chiều (prefix sum 2D) – một kỹ thuật cực kỳ hay gặp trong các đề thi HSG. Mình sẽ đi từ cách vét cạn (lấy 50% điểm) rồi tối ưu dần lên cách đạt điểm tuyệt đối nha.

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, 2 subtaskÝ tưởngGỡ rối đềCách 1Vét cạn – 50%Cách 2Tiền tố 2D – 100%

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

Bộ test có 100 test, mình kiểm tra trực tiếp thì đúng như ràng buộc của đề: 50 test đầu có $D, R \le 100$, 50 test sau có $D, R$ lên tới 1000 (trong đó chỉ test 58 là còn nhỏ). Mỗi ký tự trong lưới chỉ là . hoặc *, quà chiếm khoảng một nửa số mối nối.

TestDRKSố quàĐáp ánGhi chú
1 – 103 – 94 – 103 – 511 – 301 – 8Nhỏ, kiểm tra tay được
11 – 504 – 974 – 993 – 72175 – 38481 – 2475Ngẫu nhiên vừa
51 – 909 – 96417 – 9985 – 6711071 – 4342549 – 224269Ngẫu nhiên lớn
91 – 1001000 – 10001000 – 1000100 – 10000 – 10000000 – 996004Lớn nhất: 1000 × 1000
SubtaskĐiểmĐiều kiệnTestCách đạt
150%$D, R \le 100$1 – 50Cách 1, Cách 2
250%$D, R \le 1000$51 – 100Cách 2

Vài test đặc biệt đáng chú ý: test 99 ($K = 900$) không có món quà nào nên đáp án là 0; test 100 có $D = R = K = 1000$ và toàn bộ là quà, vợt chỉ có đúng 1 vị trí đặt, đáp án là $998^2 = 996004$. Test 91 – 100 đều là lưới $1000 \times 1000$ với $K = 100, 200, \dots, 1000$ – đây là các test "giết" cách vét cạn: số phép tính của vét cạn lên tới khoảng $6.2 \cdot 10^{10}$.

Ý tưởngGỡ rối đề: vợt K × K "ôm" được bao nhiêu mối nối?

Mỗi ký tự trong input là một mối nối (giao điểm của một đường ngang và một đường dọc), chứ không phải một ô vuông. Khung vợt $K \times K$ có 4 cạnh nằm trên đường lưới, nên mỗi cạnh của vợt đi qua đúng $K$ mối nối (giống khung lưới $D \times R$ có $D$ đường ngang). Ví dụ trong đề có $K = 4$: cạnh vợt là +--+, đi qua 4 mối nối.

  • Nếu góc trên trái của vợt nằm ở mối nối hàng $i$, cột $j$ thì vợt phủ các hàng $i \dots i + K - 1$ và các cột $j \dots j + K - 1$.
  • Bỏ đi 4 cạnh (hàng đầu, hàng cuối, cột đầu, cột cuối) thì phần bên trong vợt là hình vuông các hàng $i + 1 \dots i + K - 2$, các cột $j + 1 \dots j + K - 2$, tức là hình vuông $(K - 2) \times (K - 2)$ mối nối.
  • Vợt phải nằm trọn trong khung lưới nên $1 \le i \le D - K + 1$ và $1 \le j \le R - K + 1$. Hệ quả: phần bên trong vợt không bao giờ chạm được hàng 1, hàng $D$, cột 1, cột $R$ (quà ở viền khung lưới không bao giờ lấy được).
Bài toán thật sự
Thử mọi vị trí góc trên trái $(i, j)$ của vợt, đếm số dấu * trong hình vuông bên trong $(i+1, j+1) \to (i+K-2, j+K-2)$, lấy giá trị lớn nhất.

Em sửa khung lưới, chọn $K$ rồi bấm Tiếp để xem vợt (khung cam) trượt qua mọi vị trí. Quà xanh là quà được nhận, quà đỏ nằm trên cạnh vợt nên không được tính, khung xanh nét đứt là vị trí tốt nhất tới lúc đó:

Ví dụ nhanh:

Câu hỏi còn lại chỉ là: đếm số dấu * trong một hình vuông cho nhanh. Đếm thủ công từng mối nối thì được 50% điểm, dùng tổng tiền tố 2 chiều thì đạt điểm tối đa.

Cách 1Vét cạn: đếm trực tiếp từng mối nối – O(D·R·K²)

Làm đúng như ý tưởng: 2 vòng lặp chọn góc trên trái $(i, j)$ của vợt, 2 vòng lặp nữa duyệt từng mối nối bên trong để đếm. Code dùng chỉ số từ 0 cho gọn với string.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi vị trí vợt, đếm từng mối nối bên trong – O(D·R·K²).
Dữ liệu mẫu:
  1. Điều kiện vòng lặp i + K - 1 < D nghĩa là cạnh dưới của vợt (hàng $i + K - 1$) vẫn còn nằm trong khung lưới. Tương tự cho j.
  2. Hai vòng trong chạy x từ i + 1 tới i + K - 2 và y từ j + 1 tới j + K - 2: chính là phần bên trong vợt, đã bỏ 4 cạnh.
  3. Bản Python dùng a[x].count('*', j + 1, j + K - 1) để đếm cả một đoạn của hàng trong một lần gọi (nhanh hơn vòng lặp tay), nhưng về bản chất vẫn là vét cạn.
Không gian$O(D \cdot R)$
Thời gian$O((D-K+1)(R-K+1)(K-2)^2)$

Số phép tính là $(D - K + 1)(R - K + 1)(K - 2)^2$. Với subtask 1 ($D, R \le 100$) con số này lớn nhất chỉ khoảng $3{,}3 \cdot 10^6$ trên bộ test – chạy vèo vèo. Nhưng với $D = R = 1000$, $K = 500$ thì là $501^2 \cdot 498^2 \approx 6{,}2 \cdot 10^{10}$ – quá chậm.

Kết quả chạy thật cách 1: bản C++ đúng 75/100 test – qua trọn subtask 1 (test 1–50) và thêm 25 test của subtask 2 có $K$ nhỏ hoặc $K$ gần bằng $D, R$ (ít vị trí đặt vợt, ví dụ test 100 có $K = D = R = 1000$ chỉ có đúng 1 vị trí); 25 test còn lại bị quá thời gian. Bản Python đúng 65/100 test.

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

Gọi $s[i][j]$ là số quà trong hình chữ nhật từ mối nối $(1, 1)$ đến mối nối $(i, j)$ (đánh số từ 1, hàng 0 và cột 0 của mảng $s$ toàn số 0). Bảng $s$ tính được trong một lượt duyệt nhờ công thức "bao hàm – loại trừ":

Xây bảng tiền tố
$$s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (\text{ô } (i, j) \text{ có quà} \ ? \ 1 : 0)$$ Cộng hình phía trên với hình bên trái thì phần chung $s[i-1][j-1]$ bị cộng 2 lần, nên trừ đi 1 lần.

Có bảng $s$ rồi, số quà trong hình chữ nhật bất kỳ $(x_1, y_1) \to (x_2, y_2)$ tính bằng 4 phép cộng trừ:

Truy vấn hình chữ nhật
$$cnt = s[x_2][y_2] - s[x_1 - 1][y_2] - s[x_2][y_1 - 1] + s[x_1 - 1][y_1 - 1]$$ Lấy cả hình lớn $(1,1) \to (x_2, y_2)$, bỏ phần phía trên hàng $x_1$, bỏ phần bên trái cột $y_1$; góc trên trái bị bỏ 2 lần nên cộng lại 1 lần.

Với vợt có góc trên trái $(i, j)$ thì $x_1 = i + 1$, $y_1 = j + 1$, $x_2 = i + K - 2$, $y_2 = j + K - 2$. Em bấm Tiếp để xem 4 ô của bảng $s$ được dùng cho từng vị trí vợt (ô xanh mang dấu +, ô đỏ mang dấu −):

Ví dụ nhanh:
C++▶ Chạy tay từng dòng codeCách 2: xây bảng tiền tố s rồi mỗi vị trí vợt chỉ cần 4 phép cộng trừ – O(D·R).
Dữ liệu mẫu:
  1. Mảng s khai báo toàn cục nên tự động bằng 0 – hàng 0 và cột 0 chính là "lề" giúp công thức không bị truy cập chỉ số $-1$.
  2. Ký tự thứ $j$ của hàng (đánh số từ 1) là row[j - 1] vì string đánh số từ 0. Biểu thức (row[j - 1] == '*') có giá trị 1 hoặc 0.
  3. Kết quả lớn nhất là $(K - 2)^2 \le 998^2 < 10^6$ nên kiểu int là đủ.
  4. Bản Python: mỗi hàng của $s$ là hàng trên cộng với tổng dồn của hàng hiện tại (accumulate); khi truy vấn, với mỗi $i$ mình tính sẵn hiệu 2 hàng d = s[i + K - 2] - s[i] rồi lấy max(d[j + K - 2] - d[j]) bằng map để chạy nhanh hơn vòng lặp tay.
Không gian$O(D \cdot R)$
Thời gian$O(D \cdot R)$
Kết quả chạy thật cách 2: bản C++ đúng 100/100 test, test chậm nhất chỉ khoảng 0.01 giây. Bản Python đúng 100/100 test, chậm nhất khoảng 0.28 giây (thời gian CPU đo trên máy của mình).

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

CáchĐộ phức tạpC++PythonSubtask đạt
1. Vét cạn$O(D \cdot R \cdot K^2)$75/10065/100Subtask 1 (50%)
2. Tổng tiền tố 2D$O(D \cdot R)$100/100100/100Cả 2 subtask (100%)
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). Hai điểm dễ sai của bài này: (1) quên bỏ 4 cạnh vợt – phần được tính chỉ là hình vuông $(K-2) \times (K-2)$; (2) cho vợt chạy ra ngoài khung lưới. Kỹ thuật tổng tiền tố 2 chiều ở cách 2 các bạn nên thuộc lòng vì sẽ gặp lại rất nhiều lần.
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 😇

Nhận xét

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)