Chọn nhóm học sinh (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 3 – Bảng C1)
Đề bài
Lớp học có $n$ học sinh đánh số $0..n-1$. Thầy chủ nhiệm muốn chọn ra một nhóm học sinh tham gia trò chơi. Mức độ phù hợp của nhóm được đánh giá qua nhiều tiêu chí (có nên chọn riêng học sinh $i$ không, có nên chọn hai học sinh $i$ và $j$ cùng nhau không, ...), nên thầy xây dựng một ma trận đối xứng $Q = (q_{ij})$ kích thước $n \times n$ để chấm điểm.
Mỗi cách chọn là một vector nhị phân $x = (x_0, x_1, \dots, x_{n-1})$, $x_i = 1$ nếu chọn học sinh $i$. Giá trị của cách chọn:
$$f(x) = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} q_{ij}\, x_i\, x_j.$$
Hãy chọn nhóm sao cho $f(x)$ càng lớn càng tốt.
Dữ liệu vào:
- Dòng đầu chứa hai số nguyên $n, m$ $(n \le 500)$: kích thước ma trận và số phần tử khác 0 được liệt kê.
- $m$ dòng tiếp theo, mỗi dòng 3 số nguyên $i, j, q_{ij}$ $(0 \le i, j \le n - 1;\ |q_{ij}| \le 10^9)$. Vì $Q$ đối xứng, nếu chỉ một trong hai phần tử $(i, j)$, $(j, i)$ được liệt kê thì phần tử kia có cùng giá trị. Các phần tử không được nhắc tới bằng 0.
Dữ liệu đảm bảo giá trị $f$ tối ưu luôn dương.
Kết quả: một dòng gồm $n$ số $x_0, x_1, \dots, x_{n-1}$ (mỗi số là 0 hoặc 1).
Cách tính điểm: gọi $GV$ là $f$ của đáp án ban giám khảo, $HS$ là $f$ của bạn, $S$ là điểm tối đa của test, $r = \dfrac{GV - HS}{GV}$.
- $HS \ge GV$: được $S$ điểm.
- $0 < r \le 1\%$: được $(1 - r) \cdot \dfrac{3S}{4}$ điểm.
- $1\% < r < 10\%$: được $(1 - r) \cdot \dfrac{S}{3}$ điểm.
- còn lại: 0 điểm.
Giới hạn thời gian: 3 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 3 – Bảng C1. Đề được mình viết lại cho dễ đọc.
2 2
0 0 5
1 1 -51 0Giải thích: chỉ chọn học sinh 0 cho $f = q_{00} = 5$; chọn thêm học sinh 1 thì $f = 5 + (-5) = 0$; không chọn ai thì $f = 0$. Vậy $5$ là lớn nhất.
Lời mở đầu
Đây là một bài tối ưu chấm điểm từng phần – dạng bài ít gặp ở các kỳ thi học sinh nhưng rất thú vị. Bài toán "tìm vector nhị phân cực đại một dạng toàn phương" có tên là QUBO (Quadratic Unconstrained Binary Optimization) và là bài toán NP-khó: không ai biết thuật toán chính xác nhanh cho $n = 500$. Vì vậy cách làm là: vét cạn khi $n$ nhỏ, còn $n$ lớn thì dùng các thuật toán tìm kiếm cục bộ (leo đồi, ủ mô phỏng, tìm kiếm Tabu) để tìm một lời giải đủ tốt trong thời gian cho phép. Mình sẽ đi từ vét cạn → leo đồi → ủ mô phỏng + Tabu, chạy thật và chấm điểm từng phần cho từng cách.
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 22 test do mình tự sinh, chấm bằng trình chấm điểm từng phần (testlib) đúng công thức trong đề. "Đáp án ban giám khảo" $GV$: với $n \le 22$ là tối ưu thật (vét cạn); với $n$ lớn là giá trị tốt nhất mình tìm được sau nhiều lần chạy dài (10 giây mỗi lần, nhiều hạt giống) – không chứng minh được là tối ưu. Test 21, 22 chỉ liệt kê nửa trên của ma trận ($i \le j$) để kiểm tra cách hiểu phần tử đối xứng. Lời giải cách 3 mình đã nộp trên bộ chấm chính thức tinhoctre.vn và được 100 điểm.
Bảng dưới là thống kê từng test và điểm thật (thang 1 mỗi test) của 3 cách bản C++ (ô xám: được một phần điểm):
| Test | $n$ | $m$ | Kiểu dữ liệu | GV (đáp án mẫu) | Cách 1 | Cách 2 | Cách 3 |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 2 | ví dụ | 5 | 1 | 1 | 1 |
| 2 | 1 | 1 | $n = 1$ | 7 | 1 | 1 | 1 |
| 3 | 10 | 45 | ngẫu nhiên, giá trị nhỏ | 617 | 1 | 1 | 1 |
| 4 | 20 | 400 | dày đặc | 33.067.110.729 | 1 | 1 | 1 |
| 5 | 22 | 245 | mật độ 50% | 26.703.688.532 | 1 | 1 | 1 |
| 6 | 50 | 2.500 | dày đặc | 127.528.382.322 | 0 | 1 | 1 |
| 7 | 100 | 7.986 | mật độ 80% | 355.780.855.538 | 0 | 1 | 1 |
| 8 | 200 | 1.949 | thưa (5%) | 197.893.722.327 | 0 | 1 | 1 |
| 9 | 300 | 90.000 | dày đặc | 1.827.231.247.809 | 0 | 1 | 1 |
| 10 | 500 | 250.000 | dày đặc | 3.438.802.006.742 | 0 | 1 | 1 |
| 11 | 500 | 250.000 | dày đặc | 3.409.374.578.346 | 0 | 0,75 | 1 |
| 12 | 500 | 250.000 | lệch âm, chéo dương | 56.794.493.520 | 0 | 1 | 1 |
| 13 | 500 | 125.964 | mật độ 50% | 2.851.415.968.754 | 0 | 1 | 1 |
| 14 | 500 | 4.979 | rất thưa (2%) | 485.172.855.251 | 0 | 0,75 | 1 |
| 15 | 500 | 227.089 | giá trị $\pm 5$, nhiều hoà | 20.502 | 0 | 1 | 1 |
| 16 | 500 | 5.536 | tập độc lập (đồ thị thưa) | 93.337.183.541 | 0 | 0 | 0,74 |
| 17 | 500 | 250.000 | clique | 87.615.470 | 0 | 0,32 | 1 |
| 18 | 500 | 250.000 | nhóm ẩn (2 lưu vực) | 5.527.006.031.888 | 0 | 1 | 1 |
| 19 | 500 | 250.000 | hầu hết dương | 112.397.208.253.860 | 0 | 1 | 1 |
| 20 | 500 | 250.000 | chéo gần âm | 3.767.737.436.751 | 0 | 1 | 1 |
| 21 | 40 | 820 | chỉ cho nửa trên | 77.778.212.725 | 0 | 1 | 1 |
| 22 | 500 | 125.250 | chỉ cho nửa trên | 3.721.793.600.385 | 0 | 0,75 | 1 |
| Tổng điểm (thang 100) | 22,73 | 88,92 | 98,84 | ||||
- Test 16 (tập độc lập trọng số lớn nhất trên đồ thị thưa: chọn 2 đỉnh kề nhau bị phạt rất nặng) là test khó nhất – ngay cả cách 3 cũng thường chỉ lệch dưới 1% (được khoảng 0,74 điểm).
- Test 18 có "nhóm ẩn" với hai lưu vực xa nhau: một cực đại địa phương $2{,}03 \cdot 10^{12}$ và tối ưu $5{,}53 \cdot 10^{12}$ – thuật toán nào kẹt ở lưu vực sai là mất trắng.
- Kết quả các cách 2, 3 phụ thuộc thời gian chạy (chạy tới 2,4 giây) và máy đang bận hay rảnh, nên chạy lại có thể chênh một chút.
Ý tưởngLợi ích khi lật một bit và cực trị địa phương
Đặt $W_{ij} = q_{ij} + q_{ji}$ (với $i \ne j$) là lượng $f$ được cộng thêm khi chọn cả $i$ và $j$. Viết lại
$$f(x) = \sum_i q_{ii} x_i + \sum_{i < j} W_{ij} x_i x_j.$$
Gọi $h_i = \sum_{j \ne i} W_{ij} x_j$. Khi lật bit $i$ (0 → 1 hoặc 1 → 0), $f$ thay đổi đúng
$$\Delta_i = (1 - 2x_i) \cdot (q_{ii} + h_i).$$
Duy trì mảng $h$: lật bit $i$ thì mỗi $h_j$ chỉ thay đổi $\pm W_{ij}$ – mất $O(\text{số phần tử khác 0 trên hàng } i)$. Đây là "viên gạch" của mọi thuật toán bên dưới:
- Vét cạn mã Gray: đi qua cả $2^n$ vector, mỗi bước chỉ lật 1 bit.
- Leo đồi: còn bit nào có $\Delta_i > 0$ thì lật bit có $\Delta$ lớn nhất; hết thì ta đang ở cực đại địa phương – nhưng chưa chắc là tối ưu.
- Ủ mô phỏng / Tabu: cho phép đôi khi lật bit làm $f$ giảm để thoát khỏi cực đại địa phương.
Em chọn ma trận ngẫu nhiên (theo hạt giống) rồi bấm Tiếp để xem leo đồi: số nhỏ dưới mỗi ô là $\Delta_i$ (xanh = lật có lợi). Cuối cùng so với tối ưu thật (vét cạn) – nhiều khi leo đồi bị kẹt:
Cách 1Vét cạn theo mã Gray – O(2^n·n)
Thứ tự mã Gray đi qua cả $2^n$ vector nhị phân sao cho hai vector liên tiếp chỉ khác nhau đúng 1 bit: ở bước $g$ ta lật bit thứ __builtin_ctzll(g) (số chữ số 0 ở cuối của $g$). Nhờ công thức $\Delta_i$, mỗi bước chỉ tốn $O(n)$ để cập nhật $h$, thay vì $O(n^2)$ để tính lại $f$.
- Phần đọc dữ liệu bổ sung phần tử đối xứng còn thiếu:
has[i][j]đánh dấu phần tử có trong input. best = 0ứng với $x = 0$ (không chọn ai) – đề đảm bảo tối ưu dương nên thế nào cũng tìm được giá trị lớn hơn.
Kết quả chạy thật: bản C++ được 22,73/100 điểm (5/22 test trọn điểm, 0 điểm ở test 6–22). Đúng tuyệt đối với $n \le 22$ (test 1–5), còn $n \ge 40$ thì $2^n$ quá lớn. Bản Python được 18,18/100 điểm (4/22 test trọn điểm, 0 điểm ở test 5–22).
Cách 2Leo đồi + khởi động lại ngẫu nhiên
Xuất phát từ một vector $x$, lặp: tìm bit có $\Delta_i$ lớn nhất; nếu $\Delta_i > 0$ thì lật, ngược lại dừng (cực đại địa phương). Vì mỗi lần leo có thể kẹt ở "đỉnh đồi thấp", ta lặp lại nhiều lần từ các điểm xuất phát ngẫu nhiên cho tới hết 2,4 giây, giữ lời giải tốt nhất.
- Lần đầu xuất phát từ $x = 0$, các lần sau mỗi bit được bật với xác suất $1/2$ (sinh số ngẫu nhiên bằng công thức đồng dư tuyến tính).
- Dùng thời gian thực (
chrono::steady_clock) để dừng ở 2,4 giây, chừa thời gian in kết quả (giới hạn 3 giây). - Ma trận thưa thì
adjchỉ lưu phần tử khác 0, lật bit nhanh hơn nhiều.
Kết quả chạy thật: bản C++ được 88,92/100 điểm (17/22 test trọn điểm, điểm một phần ở test 11, 14, 17, 22, 0 điểm ở test 16). Leo đồi tìm được tối ưu ở phần lớn test ngẫu nhiên, nhưng mất điểm ở các test có cấu trúc "bẫy" (test 16, 17 – tập độc lập, clique) và một số test dày lớn. Bản Python được 68,42/100 điểm (10/22 test trọn điểm, điểm một phần ở test 8–11, 13–15, 20, 22, 0 điểm ở test 12, 16–17) – Python leo được ít vòng hơn nhiều trong 2 giây.
Cách 3Ủ mô phỏng + tìm kiếm Tabu
Hai kỹ thuật kinh điển để thoát cực đại địa phương:
- Ủ mô phỏng (simulated annealing): chọn ngẫu nhiên một bit; nếu lật có lợi thì lật, nếu thiệt ($\Delta < 0$) thì vẫn lật với xác suất $e^{\Delta / T}$. "Nhiệt độ" $T$ giảm dần theo cấp số nhân: lúc đầu nóng – nhảy lung tung khám phá, về cuối nguội – gần như chỉ leo lên. Nhiệt độ đầu được chuẩn hoá theo độ lớn trung bình của $|\Delta|$ để hợp với mọi thang giá trị.
- Tìm kiếm Tabu: mỗi bước lật bit có $\Delta$ lớn nhất kể cả khi âm, nhưng bit vừa lật bị "cấm" (tabu) lật lại trong vài bước (trừ khi lật nó cho kỷ lục mới) – nhờ vậy không quay lại chỗ cũ mà đi được sang "đồi" khác.
Lời giải của mình: $n \le 24$ thì vét cạn mã Gray (chính xác); $n$ lớn thì nửa đầu thời gian lặp các vòng [ủ mô phỏng $1500n$ bước + Tabu tinh chỉnh] với điểm xuất phát luân phiên (toàn 0 / ngẫu nhiên / toàn 1 / lời giải tốt nhất), nửa sau chạy Tabu thuần, khi lâu không cải thiện thì quay về lời giải tốt nhất và lật ngẫu nhiên khoảng $n/10$ bit. Dừng ở 2,4 giây.
- Hàm
gain(i)vàflip(i)chính là công thức $\Delta_i$ và cập nhật $h$ ở phần ý tưởng. - Số bước ủ $1500n$ là con số mình chọn qua thử nghiệm: ủ quá lâu ($4000n$) lại hay kẹt ở lưu vực sai của test 18.
- Code dài nhưng mỗi phần đều là "leo đồi có thêm luật cho phép đi xuống".
Kết quả chạy thật: bản C++ được 98,84/100 điểm (21/22 test trọn điểm, điểm một phần ở test 16). Lần chạy đầu (lúc máy đang chạy nhiều việc khác): được được 97,68/100 điểm (20/22 test trọn điểm, điểm một phần ở test 16–17). Trên bộ chấm chính thức tinhoctre.vn bản này được 100 điểm.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Điểm | Trọn điểm | Ghi chú |
|---|---|---|---|---|
| 1. Vét cạn mã Gray | C++ | 22,73 | 5/22 | chính xác khi $n \le 22$ |
| Python | 18,18 | 4/22 | $n = 20, 22$ quá giờ | |
| 2. Leo đồi + khởi động lại | C++ | 88,92 | 17/22 | chạy hết 2,4 giây |
| Python | 68,42 | 10/22 | chạy 2 giây | |
| 3. Ủ mô phỏng + Tabu | C++ | 98,84 | 21/22 | lần chạy thứ 2 |
| C++ | 97,68 | 20/22 | lần chạy thứ 1 (máy đang bận) |