Xếp hậu (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B)

Nguồn: Tin học trẻ 2024 Độ khó: Trung bình Quay lui Vét cạn Nhánh cận

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B (bài Xếp hậu). Vòng khu vực dùng chung một đề cho cả ba miền Bắc, Trung, Nam. Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Có một bàn cờ $n \times n$, hàng đánh số $1..n$ từ trên xuống, cột đánh số $1..n$ từ trái sang. Ô ở hàng $i$, cột $j$ gọi là ô $(i, j)$ và có một trọng số $w_{ij}$ (số nguyên không âm).

Ta cần đặt đúng $k$ quân hậu lên bàn cờ sao cho không có hai quân nào chiếu nhau. Hai quân hậu chiếu nhau khi chúng cùng hàng, hoặc cùng cột, hoặc cùng một đường chéo (chéo xuôi hay chéo ngược đều tính).

Yêu cầu: gọi $s$ là tổng trọng số của các ô có đặt hậu. Hãy đặt sao cho $s$ lớn nhất và in ra giá trị đó.

Dữ liệu vào:

Dòng 1: hai số nguyên $n, k$ ($1 \le k \le n \le 8$).
$n$ dòng tiếp theo: dòng thứ $i$ gồm $n$ số nguyên không âm $w_{i1}, w_{i2}, \dots, w_{in}$ (mỗi số không quá $10^6$).

Dữ liệu đảm bảo luôn có cách đặt $k$ quân hậu không chiếu nhau.

Kết quả: một số nguyên là giá trị lớn nhất của $s$.

Subtask:

Subtask 1 (30%): $k = 1$;
Subtask 2 (30%): $k \le 3$;
Subtask 3 (40%): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ví dụ – input

Ví dụ – output

Giải thích: đặt 2 quân hậu ở ô $(1, 3)$ và $(3, 2)$: hai ô này khác hàng, khác cột và không cùng đường chéo (hiệu hàng là 2, hiệu cột là 1). Tổng trọng số $2 + 2 = 4$. Không có cách nào được nhiều hơn: ô $(2, 3)$ cũng có trọng số 2 nhưng nó cùng cột với $(1, 3)$ và cùng đường chéo với $(3, 2)$.

Lưu ý: đề gốc chỉ ghi $1 \le k \le n \le 8$. Có hai trường hợp không thể đặt được: $n = k = 2$ và $n = k = 3$. Bộ test trên CLUE tránh hai trường hợp này (mình ghi rõ "dữ liệu đảm bảo luôn có cách đặt"); các lời giải bên dưới nếu gặp thì in $-1$.

Lời mở đầu

Bài toán 8 quân hậu là bài "nhập môn quay lui" kinh điển. Đề Tin học trẻ 2024 đổi đi một chút: không bắt đặt đủ $n$ quân mà chỉ đúng $k$ quân, và mỗi ô có trọng số, cần tổng lớn nhất. Vì $n \le 8$ nên bài này hoàn toàn là bài vét cạn có suy nghĩ: vét cạn "ngây thơ" thì chậm, còn vét cạn theo hàng có cắt nhánh thì chạy trong nháy mắt. Mình đi từ cách dễ nhất (chỉ ăn subtask 1) tới cách full điểm.

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ộ test20 test Ý tưởngmỗi hàng 1 hậu Cách 1k = 1 – 30đ Cách 2vét cạn – 60đ Cách 3quay lui – 100đ Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ điểm subtask của đề: 20 test (test 1 là ví dụ của đề, thuộc subtask 2 vì $k = 2$). Mỗi bảng có đủ kiểu: trọng số ngẫu nhiên, toàn số 0, toàn số $10^6$, bàn cờ có vài ô rất lớn nằm chiếu nhau để "bẫy" lời giải tham lam.

Nhóm	Test	Các giá trị $n$	Các giá trị $k$	Trọng số lớn nhất	Bàn cờ mọi ô bằng nhau	Đáp án lớn nhất
Subtask 1	2–8	1, 2, 5, 7, 8	1	1.000.000	test 2, 4, 6	1.000.000
Subtask 2	1, 9–12	3, 6, 8	2, 3	1.000.000	không có	2.963.462
Subtask 3	13–20	4, 7, 8	4, 5, 6, 7, 8	1.000.000	test 20	8.000.000

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng (cách 3) mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới theo từng subtask (ô xanh = đúng hết các test của subtask đó):

Subtask	Điều kiện	Test	Cách 1 chỉ k = 1	Cách 2 vét cạn bộ ô	Cách 2 Python	Cách 3 quay lui	Cách 3 Python
Subtask 1 (30%)	$k = 1$	2–8	7/7	7/7	7/7	7/7	7/7
Subtask 2 (30%)	$k \le 3$	1, 9–12	0/5	5/5	5/5	5/5	5/5
Subtask 3 (40%)	không ràng buộc thêm	13–20	0/8	4/8	1/8	8/8	8/8

Ý tưởngMỗi hàng có nhiều nhất một quân hậu

Nhận xét quan trọng nhất: hai quân hậu cùng hàng thì chiếu nhau, nên mỗi hàng có tối đa 1 quân hậu. Vậy ta đi lần lượt từng hàng $1, 2, \dots, n$, với mỗi hàng chỉ có $n + 1$ lựa chọn:

bỏ trống hàng này, hoặc
đặt 1 quân hậu vào một cột $j$ chưa bị chiếu (cột $j$ chưa có hậu, hai đường chéo đi qua ô đó chưa có hậu).

Để kiểm tra "bị chiếu" trong $O(1)$, ta đánh dấu 3 mảng: cot[j], cheo1[i + j] (các ô trên cùng đường chéo ngược có cùng $i + j$) và cheo2[i - j + n - 1] (cùng đường chéo xuôi có cùng $i - j$; cộng $n - 1$ để chỉ số không âm).

Khi đã đặt đủ $k$ quân thì cập nhật đáp án. Thêm một phép cắt nhánh: nếu số hàng còn lại $n - i$ ít hơn số quân còn phải đặt $k - cnt$ thì đi tiếp cũng vô ích, quay lui luôn. Em nhập bàn cờ rồi bấm Tiếp để xem quá trình quay lui (ô đỏ nhạt = đang bị chiếu, hàng viền vàng = hàng đang xét):

n = k = Bảng w (hàng cách nhau bởi ;) =

Ví dụ nhanh:

Cách 1k = 1: chỉ cần ô lớn nhất (Subtask 1)

Khi $k = 1$ thì chỉ có một quân hậu, không có chuyện chiếu nhau. Đáp án chính là trọng số lớn nhất của bàn cờ. Đọc tới đâu lấy max tới đó:

C++▶ Chạy tay từng dòng codeCách 1: k = 1 – đọc bàn cờ, lấy trọng số lớn nhất.

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

Dữ liệu mẫu:

Đáp án không âm (trọng số không âm) nên khởi tạo best = 0 là được.

Không gian$O(1)$

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

Kết quả chạy thật: Bản C++ đúng 7/20 test, sai test 1, 9–20 (các test đúng chạy lâu nhất 0.003s) → 30 điểm (subtask 1). Các test có $k \ge 2$ đều sai vì chương trình vẫn chỉ in một ô.

Cách 2Vét cạn mọi bộ k ô (Subtask 1, 2)

Cách "thật thà" nhất: đánh số các ô từ $0$ tới $n^2 - 1$ (ô số $x$ nằm ở hàng $x / n$, cột $x \% n$), sinh mọi tổ hợp $k$ ô theo thứ tự tăng dần, khi đã chọn đủ $k$ ô mới kiểm tra từng cặp có chiếu nhau không. Hai ô $(r_1, c_1)$ và $(r_2, c_2)$ chiếu nhau khi cùng hàng, cùng cột, cùng $r - c$ (chéo xuôi) hoặc cùng $r + c$ (chéo ngược).

C++▶ Chạy tay từng dòng codeCách 2: sinh mọi bộ k ô theo thứ tự tăng dần, đủ k ô mới kiểm tra chiếu nhau.

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

Dữ liệu mẫu:

Hàm chon(id, cnt): đã chọn cnt ô, ô tiếp theo phải có số thứ tự từ id trở đi – nhờ vậy mỗi bộ ô chỉ được sinh đúng một lần.
Không cắt nhánh gì cả: kể cả khi 2 ô đầu đã chiếu nhau, chương trình vẫn sinh hết các ô còn lại rồi mới phát hiện.

Số bộ phải thử là $\binom{n^2}{k}$: với $n = 8$, $k = 3$ chỉ có $41\,664$ bộ, nhưng $k = 5$ đã là $7{,}6$ triệu, $k = 8$ là $4{,}4$ tỉ bộ.

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

Thời gian$O\left(\binom{n^2}{k} \cdot k^2\right)$

Kết quả chạy thật: Bản C++ đúng 16/20 test, quá thời gian test 13–15, 20 (các test đúng chạy lâu nhất 0.571s). Ăn trọn subtask 1, 2; subtask 3 chỉ qua được các test có $k \le 6$ hoặc bảng nhỏ (test 13, 14, 20 có $n = k = 8$, test 15 có $n = 8, k = 7$ đều quá thời gian). Bản Python đúng 13/20 test, quá thời gian test 13–17, 19–20 (các test đúng chạy lâu nhất 0.050s) – Python chậm hơn nhiều nên rớt thêm vài test của subtask 3.

Cách 3Quay lui theo từng hàng + cắt nhánh (full)

Làm đúng như phần ý tưởng: hàm dat(i, cnt, s) xét hàng $i$ khi đã đặt cnt quân với tổng trọng số s.

C++▶ Chạy tay từng dòng codeCách 3: quay lui theo hàng – mỗi hàng đặt 1 hậu vào cột chưa bị chiếu hoặc bỏ trống, cắt nhánh khi không đủ hàng.

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

Dữ liệu mẫu:

if(cnt == k): đủ $k$ quân thì cập nhật best và dừng nhánh này (không đặt thêm vì đề yêu cầu đúng $k$ quân).
if(n - i < k - cnt) return; – cắt nhánh: còn $n - i$ hàng (hàng $i..n-1$, đếm từ 0) mà cần thêm $k - cnt$ quân thì không thể đủ. Dòng này cũng thay cho điều kiện dừng i == n.
Đặt hậu: đánh dấu 3 mảng, gọi đệ quy, rồi gỡ đánh dấu (đây chính là bước "quay lui").
Cuối cùng thử phương án bỏ trống hàng $i$.

Vì sao nhanh? Các nhánh bị chiếu bị loại ngay khi đặt, không đợi đủ $k$ quân. Mình đếm thử với $n = 8$: số lần gọi hàm dat lớn nhất là khoảng $97\,000$ (khi $k = 5$), còn $k = 8$ chỉ $4\,022$ lần – so với $4{,}4$ tỉ bộ của cách 2.

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

Thời giantối đa $O((n+1)^n)$ trên lý thuyết, thực tế với $n = 8$ chưa tới $10^5$ lần gọi hàm

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.080s – bài này Python cũng thoải mái.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Điểm theo subtask
1. Chỉ lấy ô lớn nhất (k = 1)	C++	7/20	0.003s	30%
	Python	7/20	0.018s	30%
2. Vét cạn mọi bộ k ô	C++	16/20	0.571s	60%
	Python	13/20	0.050s	60%
3. Quay lui theo hàng + cắt nhánh	C++	20/20	0.004s	100%
	Python	20/20	0.080s	100%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây, các test quá giờ bị dừng ở khoảng 4 giây). Điều đáng nhớ ở bài này: cùng là "vét cạn" nhưng vét cạn theo cấu trúc bài toán (mỗi hàng một quân, loại ngay ô bị chiếu, cắt nhánh khi không đủ hàng) nhanh hơn vét cạn mù quáng hàng chục nghìn lần. Khi $n$ nhỏ (ở đây $n \le 8$), hãy nghĩ tới quay lui trước khi nghĩ tới công thức phức tạp.

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 😇

Lập Trình Thuật Toán