Rotegame (Tin học trẻ toàn quốc 2024 – Vòng sơ khảo – Bảng C1)
Đề bài
Alice có một bảng số $A$ kích thước $3 \times 4$: hàng đánh số $1..3$ từ trên xuống, cột đánh số $1..4$ từ trái sang; ô $(i, j)$ ban đầu chứa số $a_{ij}$. Alice làm liên tiếp một số phép biến đổi và được bảng $B$. Mỗi phép thuộc một trong hai loại:
- Loại 1: lấy hình vuông $3 \times 3$ bên trái (cột 1–3), quay theo chiều kim đồng hồ: ô tâm đứng yên, 8 ô trên viền cùng dịch một ô theo chiều kim đồng hồ (Hình 1).
Hình 1: bảng trước và sau phép Loại 1.
- Loại 2: lấy hình vuông $3 \times 3$ bên phải (cột 2–4), quay ngược chiều kim đồng hồ: ô tâm đứng yên, 8 ô trên viền dịch một ô ngược chiều kim đồng hồ (Hình 2).
Hình 2: bảng trước và sau phép Loại 2.
Yêu cầu: Alice quên mất dãy phép đã làm, chỉ nhớ hai bảng $A$ và $B$. Hãy tìm một dãy phép biến đổi bất kỳ đưa bảng $A$ thành bảng $B$.
Dữ liệu vào:
- Ba dòng đầu, mỗi dòng bốn số nguyên dương (không vượt quá $100$) – một hàng của bảng $A$;
- Ba dòng sau, mỗi dòng bốn số – một hàng của bảng $B$.
Dữ liệu đảm bảo $B$ nhận được từ $A$ sau một số phép như trên.
Kết quả: dòng 1 ghi số phép $t$ ($t \ge 0$); dòng 2 ghi $t$ số, mỗi số là $1$ hoặc $2$ – các phép theo đúng thứ tự thực hiện. Có nhiều đáp án thì in một đáp án bất kỳ.
Subtask:
- Subtask 1 (30%): các số của bảng $A$ chỉ là $1$ hoặc $2$;
- Subtask 2 (30%): có cách biến đổi $A$ thành $B$ với không quá $36$ phép;
- 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.
9 9 9 9
1 2 3 4
5 6 7 8
1 9 9 4
5 9 9 8
6 2 7 32
1 2Giải thích: làm phép Loại 1 rồi phép Loại 2:
9 9 9 9 1 9 9 9 1 9 9 4
1 2 3 4 -> 5 2 9 4 -> 5 9 9 8
5 6 7 8 6 7 3 8 6 2 7 3Đây là bài nhiều đáp án: trình chấm kiểm tra dãy phép của em có thật sự biến $A$ thành $B$ không (không cần giống đáp án mẫu, không cần ngắn nhất).
Lời mở đầu
Bài này là "bài ngược" của bài Rote cùng đề (cho dãy phép, tìm bảng $B$). Chiều xuôi chỉ cần mô phỏng; chiều ngược thì phải tìm kiếm: mỗi bảng là một đỉnh, mỗi phép là một cạnh, cần tìm đường đi từ $A$ tới $B$ – đúng việc của BFS. Cái khó là đồ thị rất lớn ($12! \approx 4{,}8 \cdot 10^8$ trạng thái) và đường đi có thể dài tới 34 phép, nên BFS thường bùng nổ. Lời giải đầy đủ dùng BFS hai chiều – tìm từ hai đầu và gặp nhau ở giữa.
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 tỉ lệ subtask: 20 test (test 1 là ví dụ của đề). Cột "số phép ít nhất" mình tính bằng BFS (đáp án có thể dài hơn, miễn đúng).
| Nhóm | Test | Số giá trị khác nhau trong bảng | Test có 12 số đôi một khác nhau | Số phép ít nhất | Test có $A = B$ |
|---|---|---|---|---|---|
| Subtask 1 | 2–7 | 1, 2 | không có | 0–10 | test 5 |
| Subtask 2 | 1, 8–12 | 4, 9, 12 | test 8–10, 12 | 1–28 | không có |
| Subtask 3 | 13–20 | 2, 3, 12 | test 13–17, 20 | 0–34 | test 20 |
- Mình đã chạy BFS trên toàn bộ $12!$ hoán vị và thấy: hai phép quay sinh ra mọi hoán vị của 12 ô, và bảng xa nhất cũng chỉ cách $A$ đúng 34 phép. Vì vậy điều kiện "không quá 36 phép" của subtask 2 thật ra luôn đúng – điểm khác của subtask 3 là các test được chọn ở rất xa (test 13–15 cần đúng 34 phép).
- Bảng có thể có số trùng nhau (test 1 có bốn số 9); test 5 và 20 có $A = B$ – phải in
0và một dòng trống. - Bài chấm bằng checker (trình chấm riêng) nên các kết quả bên dưới mình chấm bằng chính checker đó, giới hạn 1 giây và 1024 MB.
Kết quả chạy thật các cách bên dưới theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 BFS C++ | Cách 1 Python | Cách 2 BFS 2 chiều C++ | Cách 2 Python |
|---|---|---|---|---|---|---|
| Subtask 1 (30%) | bảng $A$ chỉ gồm số $1$ và $2$ | 2–7 | 6/6 | 6/6 | 6/6 | 6/6 |
| Subtask 2 (30%) | có cách biến đổi với không quá $36$ phép | 1, 8–12 | 3/6 | 3/6 | 6/6 | 6/6 |
| Subtask 3 (40%) | không ràng buộc thêm | 13–20 | 3/8 | 3/8 | 8/8 | 8/8 |
Ý tưởngMỗi phép là một hoán vị 12 ô
Đánh số ô $(r, c)$ (từ 0) thành chỉ số $r \cdot 4 + c$, từ $0$ đến $11$. Mỗi phép chỉ di chuyển giá trị giữa các ô theo một quy tắc cố định – tức là một hoán vị: sau phép $t$, ô $i$ nhận giá trị của ô cũ $P[t][i]$. Đọc từ Hình 1 và Hình 2:
| Ô $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Loại 1: $P[0][i]$ | 4 | 0 | 1 | 3 | 8 | 5 | 2 | 7 | 9 | 10 | 6 | 11 |
| Loại 2: $P[1][i]$ | 0 | 2 | 3 | 7 | 4 | 1 | 6 | 11 | 8 | 5 | 9 | 10 |
Ví dụ Loại 1: ô $0$ (góc trên trái) nhận giá trị ô $4$ (ngay dưới nó) – đúng với "$a_{21}$ lên chỗ $a_{11}$" ở Hình 1.
Mã hoá trạng thái. Giá trị trong bảng $\le 100$ nhưng chỉ có tối đa 12 giá trị khác nhau; nén chúng về $0..11$ (mỗi giá trị cần 4 bit) thì cả bảng là một số 48 bit – cất vừa unsigned long long, làm khoá cho unordered_map rất nhanh.
Vì sao BFS một chiều không đủ? Mỗi bảng có 2 phép đi tiếp, nên số bảng cách $A$ không quá $d$ bước có thể lên tới $2^{d+1}$. Đường đi dài 34 phép thì BFS phải đi qua gần như toàn bộ $4{,}8 \cdot 10^8$ trạng thái – quá thời gian và bộ nhớ. Nhưng nếu tìm từ hai đầu: từ $A$ đi xuôi 17 bước, từ $B$ đi ngược 17 bước, mỗi bên chỉ cỡ $2^{17} \approx 1{,}3 \cdot 10^5$ trạng thái – hai "quả cầu" chạm nhau ở giữa là có đường đi. Đi ngược phép $t$ chính là áp hoán vị nghịch đảo: ô $P[t][i]$ nhận lại giá trị của ô $i$.
Em nhập hai bảng (12 số, đọc theo từng hàng) rồi bấm Tiếp: các bước đầu cho thấy hai phía BFS lớn dần (luôn mở rộng phía có tầng nhỏ hơn) cho tới khi gặp nhau, các bước sau phát lại dãy phép tìm được – 8 ô viền đang quay được tô màu, bảng ở điểm gặp nhau có viền xanh:
Cách 1BFS một chiều từ A (Subtask 1 và các test gần)
BFS từ $A$, lưu par[s] = (bảng trước, phép đã dùng) để lần ngược đường đi. Khi lấy ra được $B$ thì dừng, đi ngược từ $B$ về $A$ theo par rồi đảo dãy.
- Subtask 1 (chỉ số 1 và 2): số bảng khác nhau tối đa là $\binom{12}{6} = 924$ – BFS duyệt hết trong tích tắc.
- Với 12 số khác nhau, BFS chạy được khi $B$ gần $A$ (trên bộ test: tới 16 phép thì nhanh, 20 phép đã mất gần 2 giây); xa hơn thì số trạng thái tăng gấp đôi sau mỗi tầng.
Kết quả chạy thật: Bản C++ đúng 12/20 test, quá thời gian test 8–9, 12–17 (các test đúng chạy lâu nhất 0.021s) → 30 điểm (subtask 1; subtask 2 chỉ qua test 1, 10, 11 có đường ngắn). Bản Python đúng 12/20 test, quá thời gian test 8–9, 12–17 (các test đúng chạy lâu nhất 0.103s).
Cách 2BFS hai chiều – gặp nhau ở giữa (full)
Hai bảng băm: fw cho các bảng đi được từ $A$, bw cho các bảng đi tới được $B$. Mỗi vòng lặp mở rộng một tầng của phía đang có tầng nhỏ hơn (giữ hai phía cân bằng). Ngay khi một bảng mới của phía này đã có trong phía kia, ta có điểm gặp meet: đường đi = ($A$ → meet theo fw) + (meet → $B$ theo bw).
turn(s, t): ô $i$ của bảng mới lấy 4 bit của ô $P[t][i]$ trong bảng cũ.unturn(s, t)làm ngược lại: đặt ô $i$ của $s$ về chỗ $P[t][i]$.bw[v] = {u, t + 1}nghĩa là từ $v$ làm phép $t + 1$ thì được $u$ (gần $B$ hơn) – nên khi ghép đường phía sau ta đi xuôi theobwtừmeettới $B$, không cần đảo.- Trường hợp $A = B$ (test 5, 20):
foundđúng ngay từ đầu, in0. - Vì đường đi luôn $\le 34$, mỗi phía chỉ đi khoảng 17 tầng, tổng cỡ vài trăm nghìn trạng thái.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.268s. Full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.536s – bản Python dùng operator.itemgetter để hoán vị cả bộ 12 ô bằng một lệnh chạy trong C, nên cũng qua hết.
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. BFS một chiều từ $A$ | C++ | 12/20 | 0.021s | 30% |
| Python | 12/20 | 0.103s | 30% | |
| 2. BFS hai chiều (gặp nhau ở giữa) | C++ | 20/20 | 0.268s | 100% |
| Python | 20/20 | 0.536s | 100% |