Biến đổi (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng B, C2)
Đề bài
Cho dãy số nguyên không âm $a_1, a_2, \dots, a_n$ $(4 \le n \le 8;\ a_i \le 10^9)$. Ta muốn biến đổi để mọi phần tử đều bằng 0. Mỗi bước, được chọn 4 phần tử liên tiếp $a, b, c, d$ trong dãy và thay chúng (giữ nguyên vị trí) lần lượt bằng
$$|a - b|,\quad |b - c|,\quad |c - d|,\quad |d - a|.$$
Ví dụ với dãy $0, 1, 3, 5, 9$ có thể biến đổi như sau (ô vàng là 4 phần tử được chọn ở bước đó):
Hãy tính số bước ít nhất để tất cả các phần tử đều bằng 0.
Dữ liệu vào: gồm $n$ dòng, mỗi dòng một số nguyên $a_i$ – đề không cho trước $n$, số phần tử chính là số dòng nên phải đọc tới hết dữ liệu.
Kết quả: một số nguyên là số bước biến đổi ít nhất.
Subtask:
- Subtask 1 (30% số điểm): $n = 4$.
- Subtask 2 (30% số điểm): $n \le 6$.
- Subtask 3 (40% số điểm): không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây, bộ nhớ: 1 GB. Dữ liệu nhập từ bàn phím và in ra màn hình.
Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng B, C2. Đề được mình viết lại cho dễ đọc.
0
1
3
5
97Giải thích: dãy biến đổi ở trên dùng 7 bước và không có cách nào ít hơn. Lưu ý 4 phần tử phải liên tiếp và không được "vòng" từ cuối dãy về đầu dãy (nếu cho vòng thì ví dụ chỉ cần 5 bước).
Lời mở đầu
Bài này là một bài tìm kiếm trên không gian trạng thái: mỗi trạng thái là cả dãy số, mỗi bước có $n - 3$ lựa chọn (vị trí bắt đầu của 4 phần tử). Với $n = 4$ thì chỉ có đúng 1 lựa chọn nên chỉ cần mô phỏng – đây là dãy Ducci nổi tiếng, luôn về 0. Với $n$ lớn hơn ta cần tìm đường đi ngắn nhất: BFS là lựa chọn tự nhiên, nhưng không gian trạng thái nở rất nhanh; cách trọn điểm là tìm kiếm sâu dần (IDDFS) kèm vài nhát cắt tỉa khéo ở các bước cuối.
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 gồm 20 test (mình tự sinh theo đúng ràng buộc của đề). Test 1 là ví dụ ($n = 5$, thuộc subtask 2). Các test khó của subtask 2, 3 là những dãy mình tìm bằng leo đồi (thay đổi dần các số để số bước càng lớn càng tốt) – đáp án 11–13 bước. Lời giải cách 4 mình đã nộp trên bộ chấm chính thức tinhoctre.vn và được 100 điểm.
| Nhóm | Test | Giá trị $n$ | $a_i$ lớn nhất | Đáp án |
|---|---|---|---|---|
| Subtask 1 | 2–7 | 4 | 1.000.000.000 | 0 – 52 |
| Subtask 2 | 1, 8–12 | 5, 6 | 1.000.000.000 | 4 – 13 |
| Subtask 3 | 13–20 | 7, 8 | 869.563.976 | 2 – 13 |
- Test 2 và 7 là bộ "tribonacci" $n = 4$ cần tới 52 bước – mô phỏng vẫn tức thì.
- Test 19 ($n = 8$, đáp án 13) là test "xấu" nhất mình tìm được – cũng là test quyết định cách nào trọn điểm.
- Đề không có chứng minh chặn trên cho số bước khi $n \ge 5$; thực nghiệm (ngẫu nhiên + leo đồi) chưa thấy đáp án nào vượt 13.
Kết quả chạy thật của các cách bên dưới theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 | Cách 2 | Cách 3 | Cách 4 |
|---|---|---|---|---|---|---|
| Subtask 1 (30%) | $n = 4$ | 2–7 | 6/6 | 6/6 | 6/6 | 6/6 |
| Subtask 2 (30%) | $n \le 6$ | 1, 8–12 | 0/6 | 6/6 | 6/6 | 6/6 |
| Subtask 3 (40%) | không ràng buộc thêm ($n \le 8$) | 13–20 | 0/8 | 1/8 | 6/8 | 8/8 |
Ý tưởngĐường đi ngắn nhất trên đồ thị trạng thái
Xem mỗi dãy số là một đỉnh; từ một dãy, chọn cửa sổ 4 phần tử bắt đầu ở vị trí $w$ ($w = 1..n-3$) cho ta một cạnh tới dãy mới. Cần tìm đường đi ngắn nhất từ dãy ban đầu tới dãy toàn 0.
- $n = 4$: mỗi đỉnh chỉ có 1 cạnh đi ra → đi thẳng một mạch (mô phỏng).
- $n \ge 5$: mỗi đỉnh có $n - 3$ cạnh (2 tới 5), độ sâu đáp án tới 13 → cây tìm kiếm có cỡ $5^{13} \approx 10^9$ nút nếu duyệt thô. Phải cắt tỉa.
Em nhập dãy rồi bấm Tiếp để xem một cách biến đổi ít bước nhất (máy tìm bằng BFS) – ô vàng là cửa sổ được chọn ở bước đó:
Cách 1Subtask 1: n = 4 – mô phỏng
Khi $n = 4$ chỉ có đúng một cách chọn 4 phần tử liên tiếp (cả dãy), nên quá trình là duy nhất: cứ biến đổi tới khi dãy toàn 0 và đếm số bước. Người ta đã chứng minh dãy Ducci 4 phần tử luôn về 0, và với $a_i \le 10^9$ thì không quá vài chục bước.
while(cin >> v)đọc tới hết dữ liệu vì đề không cho $n$.- Phải tính đủ 4 giá trị mới
b0..b3rồi mới gán lại – nếu gána[0]trước thì|d - a|sẽ dùng nhầm giá trị mới củaa[0].
Kết quả chạy thật: bản C++ đúng 6/20 test, sai test 1, 8–20 (các test đúng chạy lâu nhất 0.003s) – đúng trọn 6 test $n = 4$ của subtask 1, các test khác sai vì code chỉ xử lý 4 phần tử đầu. Bản Python đúng 6/20 test, sai test 1, 8–20 (các test đúng chạy lâu nhất 0.018s).
Cách 2BFS trên các trạng thái
Duyệt theo chiều rộng: hàng đợi chứa các dãy, map dist lưu số bước tới từng dãy đã gặp. Dãy toàn 0 đầu tiên lấy ra khỏi hàng đợi cho đáp án nhỏ nhất. Chính xác với mọi $n$, nhưng số trạng thái phải lưu tăng theo cấp số nhân với độ sâu.
- Dùng
map<vector<long long>, int>để đánh dấu dãy đã thăm – không cần biết trước có bao nhiêu trạng thái. u[w + (k + 1) % 4]: với $k = 3$ phần tử "kế tiếp" là phần tử đầu cửa sổu[w]– đúng công thức $|d - a|$.
Kết quả chạy thật: bản C++ đúng 13/20 test, quá thời gian test 13–17, 19–20 (các test đúng chạy lâu nhất 0.340s). Qua subtask 1, 2 nhưng ở $n = 7, 8$ với đáp án 9–13 bước số trạng thái lên hàng chục triệu (map rất chậm và tốn bộ nhớ) nên 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.702s).
Cách 3Tìm kiếm sâu dần (IDDFS)
Thay vì lưu cả "biên" BFS, ta hỏi lần lượt: có về 0 được trong đúng $d$ bước không? với $d = 0, 1, 2, \dots$ Mỗi câu hỏi trả lời bằng một hàm đệ quy quay lui (thử từng cửa sổ, đi sâu $d$ tầng). $d$ đầu tiên trả lời "có" chính là đáp án. Bộ nhớ chỉ $O(d \cdot n)$, và tổng thời gian chủ yếu nằm ở tầng cuối cùng (các tầng trước nhỏ hơn nhiều).
Cắt tỉa duy nhất ở cách này: bỏ qua cửa sổ toàn 0 (biến đổi không làm thay đổi gì, chỉ phí 1 bước).
Kết quả chạy thật: bản C++ đúng 18/20 test, quá thời gian test 14, 19 (các test đúng chạy lâu nhất 0.522s). Gần trọn, chỉ trượt 2 test $n = 8$ có đáp án 12–13.
Cách 4IDDFS + cắt tỉa 2 bước cuối
Ở tầng cuối của cây tìm kiếm có rất nhiều nút; ta "chặn" chúng bằng cách trả lời ngay các câu hỏi nhỏ:
- Còn đúng 1 bước (
oneStep): dãy về 0 sau 1 bước ⇔ mọi số khác 0 nằm gọn trong một cửa sổ 4 ô và 4 số trong cửa sổ đó bằng nhau (vì $|a-b|$ $= |b-c|$ $= |c-d|$ $= |d-a|$ $= 0$ ⇔ $a = b = c = d$). Kiểm tra $O(n)$ thay vì thử $n - 3$ nhánh. - Còn đúng 2 bước (
twoSteps): thử cửa sổ cho bước kế tiếp, nhưng trước khi dựng dãy mới, dùng mặt nạ bit các vị trí khác 0 để loại nhanh: nếu các vị trí khác 0 trải dài hơn 4 ô thì 1 bước nữa chắc chắn không đủ. - Hai cửa sổ rời nhau giao hoán: với $n = 8$, cửa sổ $[1..4]$ và $[5..8]$ không chung phần tử nên làm $A$ rồi $B$ hay $B$ rồi $A$ cho cùng kết quả → chỉ xét một thứ tự.
Mình dùng unsigned int (vì $a_i \le 10^9 < 2^{32}$) và mảng tĩnh thay cho vector để mỗi nút rẻ hơn.
- Tham số
lastlà cửa sổ vừa dùng ở bước trước, để áp dụng luật giao hoán: nếu bước trước dùng cửa sổ 4 (tức $[5..8]$) thì bước này không dùng cửa sổ 0 nữa (thứ tự "0 rồi 4" đã được xét ở nhánh khác). __builtin_ctz(m),31 - __builtin_clz(m): vị trí bit 1 thấp nhất / cao nhất của mặt nạ, tức vị trí khác 0 đầu tiên / cuối cùng.
Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.416s. Full điểm – đây là lời giải mình đã nộp trên tinhoctre.vn (100 điểm). Mình có thử bản trung gian chỉ có cắt tỉa "1 bước cuối" + giao hoán: bản đó đúng 19/20 test, quá thời gian test 19 (các test đúng chạy lâu nhất 0.319s) – nghĩa là nhát cắt "2 bước cuối" giúp nhanh hơn khoảng 2,5 lần ở test khó nhấ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 | Ghi chú |
|---|---|---|---|---|
| 1. Mô phỏng ($n = 4$) | C++ | 6/20 | 0.003s | sai 1, 8–20 – chỉ subtask 1 |
| Python | 6/20 | 0.018s | sai 1, 8–20 | |
| 2. BFS trên trạng thái | C++ | 13/20 | 0.340s | quá giờ 13–17, 19–20 – subtask 1, 2 |
| Python | 13/20 | 0.702s | quá giờ 13–17, 19–20 | |
| 3. Tìm kiếm sâu dần (IDDFS) | C++ | 18/20 | 0.522s | quá giờ 14, 19 |
| 3b. IDDFS + cắt tỉa 1 bước cuối | C++ | 19/20 | 0.319s | quá giờ 19 – không in code |
| 4. IDDFS + cắt tỉa 2 bước cuối | C++ | 20/20 | 0.416s | Đúng hết |
Nhận xét
Đăng nhận xét