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

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

tháng 12 31, 2019

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 😇

Đọc thêm

Khôi phục (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1)

tháng 12 31, 2019

Nguồn: Tin học trẻ 2024 Độ khó: Khó Luồng cực đại Quay lui Tìm kiếm cục bộ BFS 0-1

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1 (bài restore – khôi phục). Đề vòng khu vực dùng chung cho cả ba miền Bắc, Trung, Nam; bài này nằm trong đề Bảng C1 của cả ba miền. Đề 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).

Một bức ảnh chụp một vật thể được lưu thành bảng $m \times n$ (hàng $1..m$, cột $1..n$), mỗi ô chứa $0$ hoặc $1$ (một điểm ảnh). Vật thể là vùng gồm tất cả các ô 1, và vùng này liên thông: từ một ô 1 bất kỳ có thể đi tới mọi ô 1 khác bằng cách bước qua các ô 1 chung cạnh (lên, xuống, trái, phải).

Do lưu trữ không cẩn thận, một số ô bị mất giá trị (ghi là $-1$). Tuy nhiên người ta vẫn biết hàng $i$ có đúng $a_i$ số 1 và cột $j$ có đúng $b_j$ số 1.

Yêu cầu: khôi phục lại bảng: các ô đã biết giữ nguyên, hàng $i$ có đúng $a_i$ số 1, cột $j$ có đúng $b_j$ số 1, và các ô 1 tạo thành một vùng liên thông. Có nhiều đáp án thì in một đáp án bất kỳ.

Dữ liệu vào:

Dòng đầu: hai số $m, n$ ($m, n \le 100$).
$m$ dòng tiếp theo, mỗi dòng $n$ số thuộc $\{0, 1, -1\}$ ($-1$ là ô mất giá trị).
Một dòng $m$ số $a_1, \dots, a_m$; dòng cuối $n$ số $b_1, \dots, b_n$.

Dữ liệu bảo đảm có ít nhất một cách khôi phục thoả mãn mọi điều kiện.

Kết quả: $m$ dòng, mỗi dòng $n$ số 0/1 – bảng khôi phục được.

Subtask:

Subtask 1 (30%): $m, n \le 10$ và không quá 10 ô $-1$;
Subtask 2 (30%): $m, n \le 30$ và không quá 30 ô $-1$;
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. Bài có nhiều đáp án nên được chấm bằng chương trình kiểm tra (checker).

Ví dụ 1 – input

3 4
1 0 0 1
-1 -1 -1 -1
1 0 0 1
2 4 2
3 1 1 3

Ví dụ 1 – output

1 0 0 1
1 1 1 1
1 0 0 1

Ví dụ 2 – input

3 3
-1 -1 -1
-1 -1 -1
-1 -1 -1
3 2 3
3 2 3

Ví dụ 2 – output

1 1 1
1 0 1
1 1 1

Bài học xương máu: đọc kỹ chữ "liên thông"

Thoạt nhìn, đây là bài "điền bảng 0/1 cho đúng tổng hàng, tổng cột" – một bài luồng cực đại kinh điển. Lần nộp đầu tiên của mình lên hệ thống chấm chính thức (tinhoctre.vn) chỉ dùng luồng, không quan tâm vùng ô 1 có liên thông không, và chỉ được 93/100 điểm (bài nộp 3064): checker chính thức có kiểm tra tính liên thông – nằm ở đúng một câu "vật thể là vùng liên thông" trong đề. Sau khi bổ sung phần xử lý liên thông, lời giải được 100/100 điểm (bài nộp 3076).

Lời mở đầu

Bài này có hai lớp. Lớp thứ nhất (đúng tổng hàng/cột) giải trọn vẹn bằng luồng cực đại. Lớp thứ hai (vùng ô 1 liên thông) thì khó hơn hẳn: bài toán tổng quát thuộc loại NP-khó, không có thuật toán đa thức "đẹp". Vì vậy lời giải là sự kết hợp: quay lui có cắt nhánh cho bảng ít ô mất, và cho bảng lớn thì luồng → kiểm tra liên thông → sửa dần bằng các chu trình đổi chỗ (tìm kiếm cục bộ). Mình đi lần lượt 4 cách, mỗi cách đều chạy thật trên bộ test.

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ộ test27 test Ý tưởngluồng + sửa Cách 1quay lui – 60đ Cách 2chỉ luồng Cách 3–4sửa liên thông – 100đ

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 27 test (test 1, 2 là hai ví dụ của đề). Mỗi test được sinh từ một bức ảnh thật sự liên thông (hình khối, hình "con rắn" ngoằn ngoèo, vòng tròn...) rồi xoá bớt một số ô, nên luôn có đáp án. Bài chấm bằng checker kiểm tra: đúng 0/1, giữ ô đã biết, đúng tổng hàng/cột và vùng ô 1 liên thông.

Nhóm	Test	Kích thước lớn nhất	Số ô $-1$	Số ô 1 trong đáp án	Test "bẫy" (luồng cho vùng rời)
Subtask 1	1–6	$10 \times 10$	4 – 10	8 – 40	3/6: test 4–6
Subtask 2	7–12	$30 \times 30$	6 – 30	1 – 400	4/6: test 8–11
Subtask 3	13–27	$100 \times 100$	100 – 10.000	0 – 9.000	12/15: test 13–16, 19, 21–27

Cột cuối đếm các test "bẫy": lời giải chỉ dùng luồng (cách 2) in ra bảng đúng tổng nhưng vùng ô 1 bị rời – có 19/27 test như vậy. Nhiều test bẫy được tạo có chủ đích: giấu 4 góc của một hình chữ nhật dạng $\begin{smallmatrix}1&0\\0&1\end{smallmatrix}$ – đổi chéo thành $\begin{smallmatrix}0&1\\1&0\end{smallmatrix}$ vẫn đúng tổng nhưng có thể làm đứt vùng.
Có các bảng $100 \times 100$ mất toàn bộ giá trị (chỉ biết tổng hàng/cột), bảng toàn 0, bảng chỉ có 1 hàng, và một test "đường mảnh" $27 \times 8$ mà đáp án gần như bị ép từng ô (test 25).

Kết quả trên bộ chấm chính thức

Chỉ luồng (như cách 2): 93 điểm. Luồng + xử lý liên thông: 100 điểm (AC) – cả bản đầy đủ (bài nộp 3076) lẫn chính code cách 4 trong bài này (bài nộp 3077).

Kết quả chạy thật các cách bên dưới theo từng subtask (chấm bằng checker):

Subtask	Điều kiện	Test	Cách 1 C++	Cách 1 Python	Cách 2 C++	Cách 2 Python	Cách 3 C++	Cách 4 C++
Subtask 1 (30%)	$m, n \le 10$, không quá 10 ô $-1$	1–6	6/6	6/6	3/6	3/6	6/6	6/6
Subtask 2 (30%)	$m, n \le 30$, không quá 30 ô $-1$	7–12	6/6	6/6	2/6	2/6	6/6	6/6
Subtask 3 (40%)	không ràng buộc thêm	13–27	6/15	3/15	3/15	3/15	15/15	15/15

Ý tưởngLuồng cho đúng tổng, chu trình xen kẽ để sửa liên thông

1. Chỉ lo tổng hàng/cột – luồng cực đại. Trừ các ô 1 đã biết khỏi $a_i$, $b_j$. Dựng đồ thị: nguồn $S$ → đỉnh hàng $i$ (sức chứa $a_i$ còn lại), đỉnh hàng $i$ → đỉnh cột $j$ cho mỗi ô $(i, j)$ bị mất (sức chứa 1), đỉnh cột $j$ → đích $T$ (sức chứa $b_j$ còn lại). Luồng cực đại "đầy" (bằng tổng các $a_i$ còn lại) cho một cách điền: ô $(i, j)$ bằng 1 khi cạnh hàng $i$ → cột $j$ có luồng.

2. Chu trình xen kẽ – đổi bảng mà vẫn giữ tổng. Lấy một dãy ô chưa biết $(r_1, c_1),$ $(r_1, c_2),$ $(r_2, c_2),$ $(r_2, c_3),$ $\dots$ quay về chỗ cũ, lần lượt bật (0 → 1) và tắt (1 → 0) xen kẽ: mỗi hàng, mỗi cột đi qua có đúng một ô bật và một ô tắt nên tổng không đổi. Đơn giản nhất là 4 góc một hình chữ nhật. Mọi bảng đúng tổng đều biến đổi được sang nhau bằng các chu trình như vậy – nên ta có thể "sửa" bảng của luồng mà không bao giờ làm sai tổng.

3. Sửa dần (tìm kiếm cục bộ). Gọi vùng ô 1 lớn nhất là vùng chính. Điểm phạt $f$ = tổng trên các vùng phụ của (số ô của vùng + số ô 0 ít nhất cần bật để nối nó vào vùng chính – tính bằng BFS 0-1). $f = 0$ khi và chỉ khi vùng ô 1 liên thông. Mỗi bước chọn ngẫu nhiên một vùng phụ rồi:

bắc cầu: bật các ô 0 trên đường ngắn nhất nối nó với vùng chính; mỗi ô bật được bù bằng một chu trình xen kẽ (tìm bằng Dijkstra trên đồ thị hàng–cột, ưu tiên tắt ô của vùng phụ, ưu tiên bật ô sát vùng chính, tránh tắt ô làm đứt vùng chính);
hoặc hoà tan: tắt một ô của vùng phụ, cũng bù bằng một chu trình xen kẽ.

Bước nào làm $f$ không tăng thì nhận, ngược lại trả lại (thỉnh thoảng nhận cả bước tệ hơn để thoát chỗ kẹt; kẹt quá lâu thì làm lại từ đầu). Dừng khi $f = 0$ hoặc hết giờ.

Em nhập bảng (các hàng cách nhau bởi dấu ;, ô mất ghi $-1$) và tổng hàng/cột, rồi bấm Tiếp. Ô xanh lá là vùng chính, các màu khác là vùng phụ, viền xanh/đỏ là ô sắp bật/tắt, số gạch chân là ô đã biết:

Bảng = a = b =

Ví dụ nhanh:

Cách 1Quay lui có cắt nhánh (Subtask 1, 2)

Điền lần lượt các ô $-1$ theo thứ tự hàng, thử 1 trước rồi 0. Hai kiểu cắt nhánh:

Theo tổng: sau khi điền, số 1 còn thiếu của hàng/cột phải nằm trong khoảng $[0, \text{số ô chưa điền còn lại}]$.
Liên thông "lạc quan": coi mọi ô chưa điền là 1; nếu khi đó các ô 1 vẫn không chung một vùng thì chắc chắn hỏng – quay lui ngay. Chỉ cần kiểm tra khi vừa điền một số 0 (điền 1 không làm tình hình xấu đi).

C++▶ Chạy tay từng dòng codeCách 1: quay lui theo thứ tự các ô -1, cắt nhánh theo tổng và liên thông "lạc quan".

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

Dữ liệu mẫu:

Không gian$O(mn)$

Thời gianmũ (theo số ô $-1$), nhờ cắt nhánh nên nhanh khi ít ô mất

Kết quả chạy thật: Bản C++ đúng 18/27 test, quá thời gian test 13–14, 16–17, 19, 21–23, 27 (các test đúng chạy lâu nhất 0.188s). Bản Python đúng 15/27 test, quá thời gian test 13–17, 19–23, 26–27 (các test đúng chạy lâu nhất 0.405s). Cắt nhánh tốt tới mức qua được cả vài test lớn của Subtask 3 (kể cả test 25 "đường mảnh"), nhưng với hàng nghìn ô mất thì số trạng thái vẫn bùng nổ. Được Subtask 1, 2: 60 điểm.

Cách 2Chỉ dùng luồng cực đại (quên mất liên thông)

Đây chính là lời giải "93 điểm" của mình. Luồng dùng cách đơn giản nhất: lặp lại BFS tìm đường tăng luồng, mỗi lần đẩy thêm 1 đơn vị (tổng luồng $\le 5000$, mỗi lần BFS duyệt khoảng $10^4$ cạnh). Cạnh ngược (sức chứa ban đầu 0) cho phép "đổi ý" – trả lại luồng đã đẩy.

C++▶ Chạy tay từng dòng codeCách 2: chỉ luồng cực đại – đúng tổng nhưng có thể không liên thông.

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

Dữ liệu mẫu:

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

Thời gian$O(F \cdot mn)$ với $F \le mn$ là giá trị luồng

Kết quả chạy thật: Bản C++ đúng 8/27 test, sai test 4–6, 8–11, 13–16, 19, 21–27 (các test đúng chạy lâu nhất 0.016s). Bản Python đúng 8/27 test, sai test 4–6, 8–11, 13–16, 19, 21, 23–27, quá thời gian test 22 (các test đúng chạy lâu nhất 0.185s). Mọi test đều đúng tổng hàng/cột – các test sai đều vì vùng ô 1 bị rời. Trên bộ test chính thức chỉ vài test như vậy nên vẫn được 93 điểm; bộ test của mình cố tình "gài bẫy" nhiều hơn.

Cách 3Luồng + sửa liên thông bằng chu trình xen kẽ

Cài đặt đúng phần ý tưởng: luồng → repair(). Các hàm chính:

label(): đánh số các vùng ô 1 (BFS), mainC là vùng lớn nhất; distFromMain(): BFS 0-1 từ vùng chính (bước vào ô 1 mất 0, vào ô 0 chưa biết mất 1, ô 0 đã biết thì cấm); score(): điểm phạt $f$.
safeOff(i, j): xét 8 ô quanh $(i, j)$ – nếu các ô 1 kề cạnh nó đều nằm trên cùng một "cung" ô 1 liên tiếp thì tắt $(i, j)$ không làm đứt vùng (xét cục bộ).
altPath(from, to): Dijkstra trên đồ thị hai phía, hàng $r$ → cột $c$ nghĩa là bật ô $(r, c)$ đang 0, cột $c$ → hàng $r$ nghĩa là tắt ô $(r, c)$ đang 1; chi phí lấy từ baseCost cộng chút ngẫu nhiên.
bridgePath(): BFS 0-1 từ vùng phụ tới vùng chính với thứ tự 4 hướng xáo ngẫu nhiên, để mỗi lần thử có thể ra một cây cầu khác.

C++▶ Chạy tay từng dòng codeCách 3: luồng, rồi repair() sửa dần bằng chu trình xen kẽ.

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

Dữ liệu mẫu:

Bắc cầu: bật ô $z = (r, c)$ làm hàng $r$ và cột $c$ thừa một số 1, nên cần một đường xen kẽ từ cột $c$ về hàng $r$ (tắt – bật – … – tắt). Hoà tan thì ngược lại: tắt $z$ rồi tìm đường từ hàng $r$ tới cột $c$.
Các ô vừa đổi bị "khoá" (locked) trong bước đó để chu trình sau không đổi ngược lại; các ô của cây cầu và của vùng phụ đang nối cũng bị khoá.
Bộ sinh số ngẫu nhiên xorshift với hạt giống cố định nên chương trình chạy ra cùng một kết quả mỗi lần (trừ khi chạm mốc 0,85 giây).

Không gian$O(mn + (m + n)^2)$

Thời gianluồng + mỗi bước thử $O(mn + \text{Dijkstra})$, dừng khi liên thông hoặc 0,85 giây

Kết quả chạy thật: Bản C++ đúng 27/27 test, chạy lâu nhất 0.245s (với hạt giống 2024 trong code). Tuy vậy đây là thuật toán ngẫu nhiên: mình thử thêm 12 hạt giống khác nhau thì test 25 ("đường mảnh", đáp án gần như bị ép từng ô) chỉ đúng 9/12 lần – tìm kiếm cục bộ rất khó "dò" ra một đường đi duy nhất. Bài này mình không viết bản Python cho cách 3, 4: tìm kiếm cục bộ cần thử rất nhiều bước trong 1 giây, Python không kịp.

Cách 4Kết hợp: quay lui cho bảng ít ô mất + cách 3 (full)

Hai cách bổ sung cho nhau rất khéo: quay lui mạnh đúng ở chỗ tìm kiếm cục bộ yếu (bảng nhỏ, đáp án bị ép chặt), còn tìm kiếm cục bộ xử lý các bảng lớn. Vì vậy:

Nếu số ô $-1$ không quá 400: chạy quay lui của cách 1, tối đa 0,3 giây. Tìm được thì in luôn.
Nếu chưa xong: luồng cực đại rồi repair() như cách 3 (dùng chung mốc thời gian, dừng ở 0,85 giây).

C++▶ Chạy tay từng dòng codeCách 4: bảng ít ô -1 thì quay lui (tối đa 0,3 giây) – với dữ liệu nhỏ luôn xong ở bước này.

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

Dữ liệu mẫu:

Không gian$O(mn + (m + n)^2)$

Thời giantối đa 0,3 giây quay lui + như cách 3

Kết quả chạy thật: Bản C++ đúng 27/27 test, chạy lâu nhất 0.309s. Thử với 12 hạt giống khác nhau, tất cả đều đúng cả 27 test. Full điểm.

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. Quay lui + cắt nhánh	C++	18/27	0.188s	60%
	Python	15/27	0.405s	60%
2. Chỉ luồng cực đại	C++	8/27	0.016s	0%
	Python	8/27	0.185s	0%
3. Luồng + sửa bằng chu trình xen kẽ	C++	27/27	0.245s	100%
4. Quay lui (bảng ít ô $-1$) + cách 3	C++	27/27	0.309s	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ách 3, 4 tự dừng ở 0,85 giây nếu chưa tìm được. Hai bài học từ bài này: (1) đọc kỹ từng chữ của đề – một chữ "liên thông" làm mất 7 điểm; (2) với bài khó "thật sự" (NP-khó), cách làm thực tế là kết hợp nhiều kỹ thuật: lời giải đúng đắn cho phần dễ (luồng), vét cạn có cắt nhánh cho dữ liệu nhỏ, và tìm kiếm cục bộ có định hướng cho dữ liệu lớn.

Đọc thêm

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

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

Đề bài

Lời mở đầu

Bộ testBộ test có gì?

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

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

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

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

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

Khôi phục (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1)

Đề bài

Lời mở đầu

Bộ testBộ test có gì?

Ý tưởngLuồng cho đúng tổng, chu trình xen kẽ để sửa liên thông

Cách 1Quay lui có cắt nhánh (Subtask 1, 2)

Cách 2Chỉ dùng luồng cực đại (quên mất liên thông)

Cách 3Luồng + sửa liên thông bằng chu trình xen kẽ

Cách 4Kết hợp: quay lui cho bảng ít ô mất + cách 3 (full)

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

Khóa học Lập trình Thuật toán thi đấu

Lộ trình học thuật toán từ A đến Z

Thành tích học viên