Khôi phục (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1)
Đề bài
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).
3 4
1 0 0 1
-1 -1 -1 -1
1 0 0 1
2 4 2
3 1 1 31 0 0 1
1 1 1 1
1 0 0 13 3
-1 -1 -1
-1 -1 -1
-1 -1 -1
3 2 3
3 2 31 1 1
1 0 1
1 1 1Lờ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.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
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ả 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:
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).
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.
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),mainClà 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ừbaseCostcộ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.
- 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).
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).
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% |
Nhận xét
Đăng nhận xét