Chọn số (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng B, C1, C2)

Nguồn: Tin học trẻ 2025 – Vòng loại quốc gia đợt 2 Độ khó: Dễ Quay lui Bitmask Quy hoạch động

Đề bài

Cho $n$ số nguyên dương $a_1, a_2, \ldots, a_n$. Em hãy chọn ra một tập $S$ gồm một số phần tử của dãy sao cho không có hai số nào trong $S$ mà số này chia hết cho số kia, và số phần tử của $S$ là nhiều nhất có thể.

Lưu ý: hai số bằng nhau thì chia hết cho nhau, nên hai số bằng nhau không thể cùng được chọn.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương $n$ $(n \le 20)$.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(a_i \le 10^9)$.

Kết quả: In ra một số nguyên là số phần tử nhiều nhất của tập $S$.

Subtask:

• Subtask 1 (50% số điểm): $n = 2$.
• Subtask 2 (30% số điểm): $n = 3$.
• Subtask 3 (20% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 0,1 giây, bộ nhớ: 1024 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

2
5 6

Ví dụ 1 – output

2

Ví dụ 2 – input

2
5 10

Ví dụ 2 – output

1

Ví dụ 3 – input

5
1 2 3 4 5

Ví dụ 3 – output

3

Giải thích:

• Ví dụ 1: $5$ và $6$ không chia hết cho nhau nên chọn được cả hai số.
• Ví dụ 2: $10$ chia hết cho $5$ nên chỉ chọn được một trong hai số.
• Ví dụ 3: có thể chọn ba số $2, 3, 5$ (hoặc $3, 4, 5$). Không thể chọn 4 số: số $1$ xung đột với mọi số, còn $2$ và $4$ không thể đi cùng nhau.

Ghi chú: đề gốc ghi nhầm tên subtask cuối là "Subtask 4" (thực ra chỉ có 3 subtask), mình đã sửa lại cho đúng.

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng B, C1, C2. Đề bài được mình viết lại bằng lời của mình cho dễ hiểu, giữ nguyên ý nghĩa và số liệu.

Lời mở đầu

Đây là bài "dễ thở" nhất của vòng loại quốc gia đợt 2 – đề chung cho cả ba bảng B, C1, C2. Subtask 1 và 2 ($n = 2, 3$) chỉ cần vài câu if là xong 80% số điểm. Nhưng muốn trọn 100% thì phải biết duyệt mọi tập con với $n \le 20$, và lưu ý giới hạn thời gian chỉ có 0,1 giây – viết vét cạn "thô" là bị quá thời gian ngay. Mình sẽ đi từ cách đơn giản nhất tới các cách duyệt tập con thông minh: quay lui có nhánh cận và quy hoạch động trên bitmask.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngđồ thị xung độtCách 1n = 2Cách 2vét cạn bitmaskCách 3quay luiCách 4QHĐ bitmask

Bộ testBộ test có gì?

Bộ test mình dùng có 20 test, chia đúng theo tỉ lệ subtask của đề (test 1–3 là 3 ví dụ của đề). Mình đã kiểm tra từng file: test 1–10 đều có $n = 2$, test 11–16 đều có $n = 3$, test 17–20 là subtask 3.

Nhóm	Test	$n$	$a_i$ nhỏ nhất – lớn nhất	Có số bằng nhau	Có số 1	Đáp án
Subtask 1	1–10	2	1 – 1.000.000.000	test 3–4, 7	test 3, 5, 8	1 – 2
Subtask 2	11–16	3	1 – 1.000.000.000	test 15	test 13	1 – 3
Subtask 3	17–20	5, 20	1 – 999.962.970	không	test 17–19	3 – 20

• Có khá nhiều test "bẫy": hai/ba số bằng nhau (đáp án chỉ là 1), có số 1 (số 1 là ước của mọi số), số lớn sát $10^9$.
• Test 18 và 19 có nhiều quan hệ chia hết đan xen (ví dụ test 19 là các số từ 1 đến 20), test 20 gồm 20 số không chia hết cho nhau (đáp án 20 – chọn hết).

Lời giải cuối cùng (cách 4) mình đã nộp thử trên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được AC (100 điểm) (Accepted – đúng hết các test chính thức). Kết quả chạy thật các cách bên dưới trên bộ test của mình, theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 $n = 2$	Cách 2 bitmask $O(2^n n^2)$	Cách 3 quay lui	Cách 4 QHĐ bitmask
Subtask 1 (50%)	$n = 2$	1–10	10/10	10/10	10/10	10/10
Subtask 2 (30%)	$n = 3$	11–16	3/6	6/6	6/6	6/6
Subtask 3 (20%)	$n \le 20$	17–20	0/4	3/4	4/4	4/4

Ý tưởngĐồ thị "xung đột" và duyệt tập con

Gọi hai số $a_i, a_j$ là xung đột nếu số này chia hết cho số kia ($a_i \bmod a_j = 0$ hoặc $a_j \bmod a_i = 0$). Vẽ mỗi số là một đỉnh, nối hai đỉnh xung đột bằng một cạnh. Bài toán trở thành: chọn nhiều đỉnh nhất sao cho không có cạnh nào nối hai đỉnh được chọn.

Bài toán này trong trường hợp tổng quát không có thuật toán nhanh, nhưng $n \le 20$ nên số tập con chỉ là $2^{20} \approx 10^6$ – duyệt hết được. Vấn đề chỉ là duyệt sao cho đủ nhanh với 0,1 giây:

• Vét cạn thô: với mỗi tập con lại kiểm tra mọi cặp số bằng phép % → $2^{20} \cdot 190$ phép tính, quá chậm.
• Tính trước xung đột của từng số thành một bitmask conf[i], rồi duyệt bằng quay lui: chỉ chọn số $i$ khi conf[i] không "đụng" các số đã chọn – các nhánh sai bị cắt ngay từ đầu.

Em nhập dãy số (tối đa 8 số, mỗi số ≤ 1000) rồi bấm Tiếp để xem quay lui chọn / bỏ từng số trên đồ thị xung đột:

Dãy số:

Ví dụ nhanh:

Cách 1Subtask 1: chỉ có hai số

Với $n = 2$: nếu số này chia hết cho số kia thì chỉ chọn được 1 số, ngược lại chọn được cả 2. Chú ý trường hợp hai số bằng nhau: $a \bmod b = 0$ nên đáp án là 1 – đúng như đề yêu cầu.

C++▶ Chạy tay từng dòng codeCách 1: chỉ xét hai số đầu – đúng cho n = 2.

Dữ liệu vào (stdin) – sửa thoải mái2 5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Chương trình đọc $n$ nhưng chỉ đọc đúng 2 số tiếp theo, nên khi $n \ge 3$ nó chỉ "nhìn thấy" hai số đầu và in sai (em thử bấm dữ liệu "Test đề 3" trong khung chạy tay).

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 13/20 test, sai test 13–14, 16–20, test đúng chạy lâu nhất 0,004 giây. Bản Python đúng 13/20 test, sai test 13–14, 16–20, test đúng chạy lâu nhất 0,019 giây. Ăn trọn subtask 1 (50% số điểm); các test đúng thêm ở subtask 2 chỉ là "ăn may" vì hai số đầu tình cờ cho đúng đáp án.

Cách 2Vét cạn mọi tập con bằng bitmask

Mỗi tập con của $n$ số ứng với một số nguyên mask từ $0$ đến $2^n - 1$: bit thứ $i$ bằng 1 nghĩa là chọn $a_i$. Với mỗi mask, kiểm tra mọi cặp $(i, j)$ cùng được chọn, gặp một cặp chia hết cho nhau thì tập đó hỏng. Tập nào hợp lệ thì cập nhật đáp án bằng số bit 1 của mask.

C++▶ Chạy tay từng dòng codeCách 2: duyệt mọi mask, kiểm tra từng cặp số được chọn.

Dữ liệu vào (stdin) – sửa thoải mái3 2 3 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. mask >> i & 1 lấy bit thứ $i$ của mask – cho biết $a_i$ có được chọn không.
2. __builtin_popcount(mask) đếm số bit 1 = số phần tử của tập.
3. Dùng long long cho $a_i$ cho chắc ($a_i \le 10^9$ vừa kiểu int, nhưng không mất gì).

Không gian$O(n)$

Thời gian$O(2^n \cdot n^2)$

Kết quả chạy thật: bản C++ đúng 19/20 test, quá thời gian test 20, test đúng chạy lâu nhất 0,020 giây. Bản Python đúng 17/20 test, quá thời gian test 18–20, test đúng chạy lâu nhất 0,021 giây.

Test 20 (20 số không ai chia hết cho ai) là trường hợp xấu nhất: mọi tập con đều hợp lệ nên với tập nào cũng phải kiểm tra đủ mọi cặp – khoảng $2^{20} \cdot 190 / 2 \approx 10^8$ phép % trên số 64 bit, mất hơn 0,3 giây, vượt giới hạn 0,1 giây. Vì subtask 3 bị chấm theo cả nhóm nên cách này được 80% số điểm.

Cách 3Quay lui chọn / bỏ + nhánh cận

Hai cải tiến so với cách 2:

1. Tính trước xung đột: conf[i] là bitmask các chỉ số $j$ xung đột với $i$. Khi đó "số $i$ có xung đột với tập chosen không" chỉ là một phép AND: conf[i] & chosen.
2. Quay lui: hàm go(i, chosen, cnt) lần lượt quyết định chọn hay bỏ số thứ $i$. Chỉ đi vào nhánh "chọn" khi số $i$ không xung đột – nên các tập hỏng không bao giờ được sinh ra. Thêm nhánh cận: nếu cnt + (n - i) <= best thì dù chọn hết các số còn lại cũng không vượt kỷ lục → bỏ nhánh này.

C++▶ Chạy tay từng dòng codeCách 3: quay lui chọn / bỏ từng số, cắt nhánh khi không thể vượt kỷ lục.

Dữ liệu vào (stdin) – sửa thoải mái4 2 3 4 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Khi tới i == n, nhờ nhánh cận ở dòng trên ta biết chắc cnt > best, nên gán thẳng best = cnt.
2. Thử nhánh "chọn" trước giúp tìm được tập lớn sớm, kỷ lục best tăng nhanh nên nhánh cận cắt được nhiều hơn. Với test 20 (chọn được hết), nhánh đầu tiên đã cho best = 20 và mọi nhánh sau bị cắt ngay.
3. Độ sâu đệ quy chỉ là $n + 1 \le 21$.

Không gian$O(n)$

Thời gian$O(n^2 + 2^n)$ (thực tế nhanh hơn nhiều nhờ cắt nhánh)

Kết quả chạy thật: bản C++ đúng 20/20 test, test đúng chạy lâu nhất 0,005 giây. Bản Python đúng 20/20 test, test đúng chạy lâu nhất 0,024 giây – nhờ nhánh cận nên Python cũng qua được giới hạn 0,1 giây trên bộ test của mình.

Lưu ý về độ phức tạp

Nhánh cận không làm giảm độ phức tạp trong trường hợp xấu nhất (vẫn có thể là $O(2^n)$ lời gọi), nhưng số tập không xung đột thường ít hơn $2^n$ rất nhiều nên trên thực tế chạy rất nhanh. Nếu muốn chắc chắn tuyệt đối về thời gian, hãy xem cách 4.

Cách 4Quy hoạch động trên bitmask – O(2ⁿ)

Đây là lời giải mình đã nộp chính thức. Gọi ok[mask] = 1 nếu tập mask không có hai số xung đột. Lấy ra bit thấp nhất low của mask, phần còn lại là rest = mask & (mask - 1) (một số nhỏ hơn mask, đã tính rồi):

Công thức

ok[mask] = ok[rest] && !(conf[low] & rest)
Tập mask hợp lệ ⇔ phần còn lại hợp lệ và số low không xung đột với phần còn lại.

Ví dụ với dãy $1, 2, 3, 4, 5$ (chỉ số 0..4): mask = 01110 (chọn $2, 3, 4$), low = 1 (số 2), rest = 01100 (chọn $3, 4$) hợp lệ, nhưng conf[1] chứa bit 3 (vì $4$ chia hết cho $2$) → ok[01110] = 0.

C++▶ Chạy tay từng dòng codeCách 4: QHĐ trên bitmask – ok[mask] tính từ ok[mask bỏ bit thấp nhất].

Dữ liệu vào (stdin) – sửa thoải mái5 1 2 3 4 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. __builtin_ctz(mask) đếm số bit 0 ở cuối = chỉ số của bit 1 thấp nhất.
2. mask & (mask - 1) xoá bit 1 thấp nhất – mẹo kinh điển với bitmask.
3. Mảng ok kiểu char có $2^{20}$ phần tử, chỉ khoảng 1 MB.

Không gian$O(2^n)$

Thời gian$O(n^2 + 2^n)$

Kết quả chạy thật: bản C++ đúng 20/20 test, test đúng chạy lâu nhất 0,006 giây. Bản Python đúng 17/20 test, quá thời gian test 18–20, test đúng chạy lâu nhất 0,026 giây – Python phải lặp đủ $2^{20}$ lần nên không kịp 0,1 giây ở các test $n = 20$ (với Python, cách 3 lại nhanh hơn nhờ cắt nhánh).

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. Chỉ xử lí $n = 2$	C++	13/20	0,004 s	50%
	Python	13/20	0,019 s	50%
2. Vét cạn bitmask	C++	19/20	0,020 s	80%
	Python	17/20	0,021 s	80%
3. Quay lui + nhánh cận	C++	20/20	0,005 s	100%
	Python	20/20	0,024 s	100%
4. QHĐ trên bitmask	C++	20/20	0,006 s	100%
	Python	17/20	0,026 s	80%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình với giới hạn 0,1 giây. Cách 1 đủ 50% điểm chỉ với một câu if; vét cạn thô (cách 2) được 80%; muốn trọn điểm cần duyệt tập con khéo hơn: quay lui có cắt nhánh (cách 3) hoặc quy hoạch động trên bitmask (cách 4, đã AC trên hệ thống chấm chính thức). Bài học: khi $n \le 20$, hãy nghĩ ngay tới duyệt $2^n$ tập con, và cố gắng làm mỗi bước kiểm tra chỉ còn $O(1)$ bằng thao tác bit.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇