Vector (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng C1)
Đề bài
Trong giờ học về vector, cô Alice tạo ra $n$ vector, vector thứ $i$ là $(x_i, y_i, z_i)$. Cô bí mật chọn ra một số vector, cộng lại được vector $(x, y, z)$, rồi đố học sinh: hãy tìm một cách chọn các vector có tổng đúng bằng $(x, y, z)$.
Cho $n$ vector và $x, y, z$, hãy đưa ra một cách chọn thoả mãn. Vì cô đã chọn trước nên luôn tồn tại cách chọn.
Dữ liệu vào:
- Dòng đầu chứa 4 số nguyên $n, x, y, z$ $(n \le 200;\ 0 \le x, y, z \le 10^6)$.
- $n$ dòng tiếp theo, dòng thứ $i$ chứa 3 số nguyên không âm $x_i, y_i, z_i \le 10^6$.
Kết quả: một xâu gồm $n$ kí tự, kí tự thứ $i$ là 1 nếu chọn vector $i$, là 0 nếu không chọn. Có nhiều cách thì in cách bất kỳ.
Subtask: mỗi subtask 25% số test.
- Subtask 1: $n \le 20$.
- Subtask 2: $n \le 40$.
- Subtask 3: $y_i = z_i = 0$ với mọi $i$.
- Subtask 4: 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 C1. Đề được mình viết lại cho dễ đọc.
3 1 2 3
1 1 1
1 0 1
0 1 2101Giải thích: chọn vector 1 và 3: $(1, 1, 1) + (0, 1, 2)$ $= (1, 2, 3)$. Vì có thể có nhiều đáp án nên bài được chấm bằng trình chấm riêng (kiểm tra độ dài xâu và tổng các vector được chọn), không so khớp từng kí tự.
Lời mở đầu
Đây là bài khó nhất vòng loại đợt 1 bảng C1, và là một bài "lạ": về bản chất nó là bài toán tổng tập con 3 chiều – một bài NP-khó, không có thuật toán đa thức tổng quát. Các subtask được thiết kế rất rõ ràng: $n \le 20$ (duyệt mọi tập con), $n \le 40$ (chia đôi tập – meet in the middle), $y = z = 0$ (cái túi 0/1 bằng bitset), và subtask cuối cần dựa vào tính chất của dữ liệu: khi có rất nhiều vector nhỏ thì có vô số cách chọn, và một thuật toán ngẫu nhiên khéo léo sẽ tìm được rất nhanh. Bài viết hơi dài, các bạn đọc từ từ nhé.
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 24 test (mình tự sinh, mỗi subtask 6 test): mỗi test chọn ngẫu nhiên $n$ vector, rồi chọn ngẫu nhiên một tập con làm "bí mật" của cô Alice và lấy tổng làm $(x, y, z)$. Các chế độ sinh: toạ độ đều trong $[0, V]$ với $V$ từ $100$ tới $10^6$, trộn vector lớn và nhỏ, nhiều vector trùng nhau, có vector $(0, 0, 0)$. Bài chấm bằng trình chấm riêng (testlib) nên mình chấm thử bằng chính trình chấm đó. Lời giải đầy đủ 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$ | Toạ độ lớn nhất | Số vector trong đáp án mẫu |
|---|---|---|---|---|
| Subtask 1 | 1–6 | 1, 3, 20 | 2 – 997.658 | 1 – 20 |
| Subtask 2 | 7–12 | 37, 40 | 99 – 986.293 | 2 – 40 |
| Subtask 3 | 13–18 | 150, 200 | 100 – 997.964 | 1 – 200 |
| Subtask 4 | 19–24 | 200 | 998 – 999.828 | 1 – 101 |
- Cột cuối là số vector trong tập "bí mật" (đáp án mẫu) – từ 1 (test rất "thưa", vector lớn) tới 200 (chọn tất cả).
- Subtask 4 có các test "dày": $n = 200$, toạ độ chỉ tới $10^3$–$3 \cdot 10^4$, đáp án mẫu gồm 50–100 vector. Đây là chỗ khó nhất.
Kết quả chạy thật của các cách bên dưới theo từng subtask (chấm bằng trình chấm testlib):
| Subtask | Điều kiện | Test | Cách 1 | Cách 2 | Cách 3 | Cách 4 |
|---|---|---|---|---|---|---|
| Subtask 1 (25%) | $n \le 20$ | 1–6 | 6/6 | 6/6 | 3/6 | 6/6 |
| Subtask 2 (25%) | $n \le 40$ | 7–12 | 0/6 | 6/6 | 2/6 | 6/6 |
| Subtask 3 (25%) | $y_i = z_i = 0$ | 13–18 | 0/6 | 0/6 | 6/6 | 6/6 |
| Subtask 4 (25%) | không ràng buộc thêm | 19–24 | 0/6 | 0/6 | 1/6 | 6/6 |
Ý tưởngChia đôi tập: 2^n thành 2·2^(n/2)
Ý tưởng then chốt cho $n \le 40$: chia các vector thành hai nửa $A$ và $B$. Một cách chọn = (tập con của $A$) + (tập con của $B$). Ta:
- Liệt kê mọi tập con của $A$ ($2^{20} \approx 10^6$ tập), lưu tổng của chúng vào danh sách $L$ rồi sắp xếp.
- Với mỗi tập con của $B$ có tổng $s$, phần còn thiếu là $(x, y, z) - s$ – tìm kiếm nhị phân trong $L$ xem có tập con nào của $A$ có đúng tổng đó không.
Thay vì $2^{40} \approx 10^{12}$ tập con, ta chỉ làm $2 \cdot 2^{20}$ tập con cộng thêm chi phí sắp xếp và tìm kiếm. Để so sánh/sắp xếp bộ 3 số cho nhanh, mình "gói" $(a, b, c)$ thành một số 64 bit: $a \cdot 2^{42} + b \cdot 2^{21} + c$ (mỗi toạ độ $\le 10^6 < 2^{21}$).
Em nhập dữ liệu (các dòng cách nhau bởi dấu /) rồi bấm Tiếp để xem chia đôi tập hoạt động:
Cách 1Subtask 1: duyệt mọi tập con – O(2^n·n)
Mỗi số mask từ $0$ tới $2^n - 1$ biểu diễn một tập con (bit $i$ bằng 1 ⇔ chọn vector $i$). Tính tổng và so với đích.
Kết quả chạy thật: bản C++ đúng 6/24 test, sai test 13–24, quá thời gian test 7–12 (các test đúng chạy lâu nhất 0.065s). Với $n = 20$ chỉ $2 \cdot 10^7$ phép tính; $n = 40$ thì vô vọng. Bản Python đúng 6/24 test, sai test 7–24 (các test đúng chạy lâu nhất 0.788s) (bản Python tính tổng tăng dần theo bit thấp nhất để nhanh hơn).
Cách 2Subtask 2: chia đôi tập – O(2^(n/2)·n)
Cài đặt đúng ý tưởng ở trên. Nửa đầu chỉ lưu các tập con có tổng không vượt đích ở cả 3 toạ độ (vì toạ độ không âm, vượt rồi thì không cứu được).
- Danh sách
Llưu cặp (tổng đã gói, mặt nạ) và sắp xếp theo tổng;lower_boundvớimake_pair(need, 0)trả về phần tử đầu tiên có tổng $\ge$need. - Khi tìm thấy, in mặt nạ của nửa đầu rồi mặt nạ của nửa sau – đúng thứ tự các vector.
Kết quả chạy thật: bản C++ đúng 12/24 test, sai test 13–24 (các test đúng chạy lâu nhất 0.303s). Trọn subtask 1, 2. Bản Python đúng 7/24 test, sai test 13–24, quá thời gian test 7–11 (các test đúng chạy lâu nhất 0.695s) – Python dùng dict thay cho sắp xếp + tìm kiếm nhị phân nhưng vẫn quá chậm ở $n = 40$ (mỗi nửa $10^6$ tập con).
Cách 3Subtask 3: cái túi 0/1 bằng bitset
Khi $y_i = z_i = 0$, bài chỉ còn: chọn tập con có tổng $x_i$ bằng $X$ – bài cái túi 0/1 (subset sum) quen thuộc. Gọi $dp[i]$ là tập các tổng đạt được bằng $i$ vector đầu, lưu dưới dạng bitset (bit $s$ bằng 1 ⇔ đạt được tổng $s$):
$$dp[i] = dp[i-1] \;\text{OR}\; (dp[i-1] \ll x_i).$$
Dịch trái $x_i$ bit nghĩa là "cộng thêm $x_i$ vào mọi tổng cũ". Mỗi phép dịch/OR trên $10^6$ bit chỉ tốn $10^6 / 64 \approx 1{,}6 \cdot 10^4$ phép tính, nên cả bảng $200 \times 10^6$ bit (25 MB) dựng rất nhanh. Truy vết từ $(n, X)$: nếu $dp[i-1]$ đã có bit $s$ thì không cần vector $i$, ngược lại bắt buộc chọn vector $i$ và $s \mathrel{-}= x_i$.
Kết quả chạy thật: bản C++ đúng 12/24 test, sai test 1, 4, 6–7, 9–10, 12, 19–23 (các test đúng chạy lâu nhất 0.024s). Trọn subtask 3; ngoài ra "ăn may" thêm test 2, 3, 5, 8, 11, 24 (bỏ qua $y, z$ mà vẫn ra đúng). Bản Python đúng 12/24 test, sai test 1, 4, 6–7, 9–10, 12, 19–23 (các test đúng chạy lâu nhất 0.040s) – trong Python mình dùng số nguyên lớn làm bitset.
Cách 4Subtask 4: kết hợp + thuật toán "sinh nhật" ngẫu nhiên
Bài tổng quát là NP-khó nên không có thuật toán "đẹp" chắc chắn chạy nhanh với mọi dữ liệu. Nhưng dữ liệu được sinh bằng cách chọn ngẫu nhiên một tập con, nên ta phân ra hai trường hợp:
- Thưa (ít vector được chọn, hoặc vector lớn): cách chia đôi tập ở trên kèm cắt tỉa (bỏ ngay nhánh vượt đích, vector lớn xét trước) chạy rất nhanh dù $n = 200$, vì số tập con không vượt đích rất ít. Mình liệt kê bằng đệ quy và đặt giới hạn: nếu danh sách nửa đầu vượt $2^{20}$ phần tử thì bỏ cuộc.
- Một chiều (subtask 3): dùng cái túi bitset ở cách 3 – chính xác.
- Dày (nhiều vector nhỏ, đích là tổng của 50–100 vector): có cực kỳ nhiều cách chọn đúng. Mình dùng thuật toán sinh nhật 4 danh sách (ý tưởng của Wagner):
- Chia ngẫu nhiên các vector thành 4 nhóm. Mỗi nhóm sinh $K$ tập con ngẫu nhiên (mỗi vector được chọn với xác suất $p$ = tỉ lệ tổng đích / tổng tất cả, để tổng kỳ vọng ≈ đích).
- Chọn một số $c$ ở khoảng giữa. Ghép nhóm 1 với nhóm 2 lấy các cặp có tổng $x$ đúng bằng $c$ (sắp xếp + tìm kiếm nhị phân), lưu tổng $(y, z)$ của chúng.
- Ghép nhóm 3 với nhóm 4 lấy các cặp có tổng $x$ bằng $X - c$, rồi tìm trong danh sách ở bước 2 phần bù $(Y - y, Z - z)$.
- Không thấy thì làm lại với phân nhóm ngẫu nhiên mới và $K$ lớn hơn.
u128(unsigned __int128) làm mặt nạ vì một nửa có thể tới 100 vector.- Mẹo sinh nhanh $K$ tập con ngẫu nhiên: chia nhóm làm 2 nửa, mỗi nửa sinh $h \approx 2\sqrt{K}$ tập con ngẫu nhiên, rồi ghép ngẫu nhiên từng cặp – mỗi tập con chỉ tốn $O(1)$ thay vì $O(\text{số vector trong nhóm})$.
- Bắt đầu với $K = 2^{17}$, chưa tìm được thì nhân đôi (tối đa $2^{19}$) và thử lại với phân nhóm mới.
Kết quả chạy thật: bản C++ đúng 24/24 test, chạy lâu nhất 0.452s. Mình chạy thêm với 8 hạt giống ngẫu nhiên khác nhau trên các test dày (20–22): lâu nhất khoảng 0,35 giây khi bắt đầu từ $K = 2^{17}$ (nếu bắt đầu từ $K = 2^{15}$ thì có lần tới 0,86 giây do phải thử lại nhiều lần).
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. Duyệt mọi tập con | C++ | 6/24 | 0.065s | sai 13–24, quá giờ 7–12 – subtask 1 |
| Python | 6/24 | 0.788s | sai 7–24 | |
| 2. Chia đôi tập (MITM) | C++ | 12/24 | 0.303s | sai 13–24 – subtask 1, 2 |
| Python | 7/24 | 0.695s | sai 13–24, quá giờ 7–11 | |
| 3. Cái túi bitset 1 chiều | C++ | 12/24 | 0.024s | sai 1, 4, 6–7, 9–10, 12, 19–23 – subtask 3 |
| Python | 12/24 | 0.040s | sai 1, 4, 6–7, 9–10, 12, 19–23 | |
| 4. Kết hợp + thuật toán sinh nhật | C++ | 24/24 | 0.452s | Đúng hết |