Next (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1, C2)

Nguồn: Tin học trẻ 2024 Độ khó: Khá Xử lý bit Tổ hợp Đếm thứ tự

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1, C2 (bài Next). Vòng khu vực dùng chung một đề cho cả ba miền Bắc, Trung, Nam. Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Với số nguyên dương $x$, gọi $\text{Next}(x)$ là số nguyên dương nhỏ nhất lớn hơn $x$ có cùng số lượng bit 1 với $x$ (khi viết trong hệ nhị phân). Ví dụ $\text{Next}(1) = 2$, $\text{Next}(6) = 9$.

Kí hiệu $\text{Next}^k(x)$ là kết quả khi áp dụng hàm $\text{Next}$ liên tiếp $k$ lần bắt đầu từ $x$: $\text{Next}^k(x)$ $= \text{Next}(\text{Next}(\dots\text{Next}(x)))$.

Yêu cầu: cho số nguyên dương $x \le 10^{15}$ và số nguyên dương $k$, tìm $\text{Next}^k(x)$. Nếu giá trị này vượt quá $10^{15}$ thì in $-1$.

Dữ liệu vào:

• Dòng 1: số nguyên dương $t$ – số truy vấn.
• $t$ dòng tiếp theo, mỗi dòng hai số nguyên dương $x$ và $k$ ($x \le 10^{15}$).

Kết quả: $t$ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Subtask:

• Subtask 1 (50%): $k \le 10^2$; $t \le 10$;
• Subtask 2 (50%): $k \le 10^{15}$; $t \le 1000$.

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.

Ví dụ – input

2
1 2
6 1

Ví dụ – output

4
9

Giải thích: $1 = 1_2$, $\text{Next}(1) = 2 = 10_2$, $\text{Next}^2(1)$ $= \text{Next}(2)$ $= 4$ $= 100_2$. Còn $6 = 110_2$ có hai bit 1; số nhỏ nhất lớn hơn 6 có hai bit 1 là $9 = 1001_2$ (vì $7 = 111_2$ có ba bit, $8 = 1000_2$ có một bit).

Lưu ý: đáp án đúng bằng $10^{15}$ vẫn hợp lệ (chỉ "vượt quá" mới in $-1$) – bộ test có nhiều truy vấn như vậy. Đề gốc không ghi giới hạn dưới của $k$ ở subtask 2; bộ test dùng $1 \le k \le 10^{15}$.

Lời mở đầu

Nếu xếp tất cả các số có đúng $c$ bit 1 theo thứ tự tăng dần thì $\text{Next}$ chỉ là "bước sang số kế tiếp" trong dãy đó, và $\text{Next}^k(x)$ là số đứng sau $x$ đúng $k$ vị trí. Với $k$ nhỏ ta cứ bước từng bước; với $k$ tới $10^{15}$ thì phải "nhảy" thẳng bằng đếm tổ hợp: tính thứ tự của $x$ trong dãy, cộng $k$, rồi dựng lại số có thứ tự đó.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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ưởngthứ tự + kCách 1tăng dần – TLECách 2mẹo bit – 50đCách 3tổ hợp – 100đTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ điểm subtask của đề: 20 test (test 1 là ví dụ của đề). Có đủ các kiểu $x$: lũy thừa của 2, toàn bit 1, sát $10^{15}$, $x$ có rất nhiều hoặc rất ít bit 1.

Nhóm	Test	$t$ lớn nhất	Tổng số truy vấn	$k$ lớn nhất	$x$ lớn nhất	Số truy vấn in $-1$	Số truy vấn đáp án đúng bằng $10^{15}$
Subtask 1	1–10	10	83	100	$10^{15}$	13	2
Subtask 2	11–20	1.000	10.000	$10^{15}$	$10^{15}$	2.714	243

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng (cách 3) mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

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 tăng dần	Cách 2 mẹo bit	Cách 2 Python	Cách 3 tổ hợp	Cách 3 Python
Subtask 1 (50%)	$k \le 10^2$; $t \le 10$	1–10	3/10	10/10	10/10	10/10	10/10
Subtask 2 (50%)	$k \le 10^{15}$; $t \le 1000$	11–20	0/10	0/10	0/10	10/10	10/10

Ý tưởngThứ tự trong dãy các số có c bit 1

Gọi $c$ là số bit 1 của $x$. Vì $10^{15} < 2^{50}$, mọi số ta quan tâm đều dưới $2^{50}$, tức viết được bằng 50 bit (bit $49$ tới bit $0$). Hai việc cần làm:

1. Thứ tự của $x$ = số số $y \le x$ có đúng $c$ bit 1. Một số $y < x$ khác $x$ lần đầu tiên (đi từ bit cao xuống) tại một bit $b$ mà $x$ có bit 1 còn $y$ có bit 0. Khi đó các bit cao hơn $b$ giống $x$ (đã dùng $daGap$ bit 1), và $b$ bit thấp chọn tùy ý sao cho đủ $c - daGap$ bit 1: có $\binom{b}{c - daGap}$ cách. Vậy:

$$\text{thứ tự}(x) = 1 + \sum_{\text{bit } b \text{ của } x \text{ bằng } 1} \binom{b}{c - daGap_b}.$$

2. Dựng số thứ $r$ (với $r = \text{thứ tự}(x) + k$): đi từ bit 49 xuống bit 0, đang cần đặt thêm $can$ bit 1. Số các số có bit $b$ bằng 0 (và $can$ bit 1 nằm hết ở $b$ bit thấp) là $\binom{b}{can}$. Nếu $r \le \binom{b}{can}$ thì số cần tìm có bit $b = 0$; ngược lại nó có bit $b = 1$, ta bỏ qua cả nhóm bit 0: $r \mathrel{-}= \binom{b}{can}$, $can \mathrel{-}= 1$.

Nếu $r > \binom{50}{c}$ thì số cần tìm $\ge 2^{50} > 10^{15}$ → in $-1$; dựng xong mà $y > 10^{15}$ cũng in $-1$.

Em nhập $x$, $k$ (bản thu nhỏ: chỉ dùng 12 bit) rồi bấm Tiếp để xem hai bước trên; dòng dưới cùng liệt kê dãy các số có $c$ bit 1 để em đối chiếu:

x = k =

Ví dụ nhanh:

Cách 1Tăng x từng đơn vị (chưa đủ)

Cách nghĩ ngay theo định nghĩa: lặp $k$ lần, mỗi lần tăng $x$ cho tới khi gặp số có đúng $c$ bit 1 (__builtin_popcountll đếm số bit 1 của số long long).

C++▶ Chạy tay từng dòng codeCách 1: mỗi lần nhảy, tăng x từng đơn vị cho tới khi số bit 1 bằng c.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Vấn đề: khoảng cách giữa hai số liên tiếp có cùng số bit 1 có thể rất xa. Ví dụ $\text{Next}(2^{40}) = 2^{41}$ – phải tăng $2^{40} \approx 10^{12}$ lần! Chỉ cần một truy vấn kiểu này là quá thời gian.

Không gian$O(1)$

Thời gianmỗi truy vấn tỉ lệ với $\text{Next}^k(x) - x$, có thể tới $10^{15}$

Kết quả chạy thật: Bản C++ đúng 3/20 test, quá thời gian test 2, 4–5, 7–20 (các test đúng chạy lâu nhất 0.027s). Gần như mất hết, kể cả subtask 1 – vì $k$ nhỏ nhưng $x$ lớn tới $10^{15}$.

Cách 2Mẹo bit Gosper – O(k) mỗi truy vấn (Subtask 1)

Có một mẹo bit kinh điển (gọi là Gosper's hack) tính $\text{Next}(x)$ trong $O(1)$. Nhìn $x$ ở dạng nhị phân, xét khối bit 1 thấp nhất, ví dụ $x = 1011\mathbf{1100}_2$:

1. c = x & -x lấy bit 1 thấp nhất: $c = 100_2$.
2. r = x + c: cộng vào làm khối bit 1 thấp nhất "tràn" lên – bit 0 ngay trên khối thành 1, cả khối thành 0: $r = 1100\,0000_2$.
3. Ta mất $(\text{độ dài khối}) - 1$ bit 1, phải đặt bù chúng vào cuối số (vị trí thấp nhất để số nhỏ nhất): r ^ x là khối đã đổi (dài hơn khối cũ 1 bit), dịch phải 2 rồi chia cho c để đưa về sát bit 0: ((r ^ x) >> 2) / c $= 1_2$.
4. Ghép lại: $\text{Next}(x)$ $= r \,|\,$ $1_2$ $= 1100\,0001_2$.

C++▶ Chạy tay từng dòng codeCách 2: mẹo bit Gosper tính Next(x) trong O(1), lặp k lần.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Vòng lặp dừng sớm khi $x$ đã vượt $10^{15}$ (đi tiếp chỉ càng lớn hơn). Mỗi truy vấn tốn $O(k)$: subtask 1 chỉ $10 \cdot 100$ phép – tức thì; nhưng $k = 10^{15}$ thì không thể.

Không gian$O(1)$

Thời gian$O(t \cdot k)$

Kết quả chạy thật: Bản C++ đúng 10/20 test, quá thời gian test 11–20 (các test đúng chạy lâu nhất 0.003s) → 50 điểm. Bản Python đúng 10/20 test, quá thời gian test 11–20 (các test đúng chạy lâu nhất 0.026s).

Cách 3Đếm tổ hợp – O(50) mỗi truy vấn (full)

Làm đúng như phần ý tưởng. Bảng tổ hợp $C[n][r]$ với $n \le 50$ tính bằng tam giác Pascal; $\binom{50}{25} \approx 1{,}26 \cdot 10^{14}$ vừa long long.

C++▶ Chạy tay từng dòng codeCách 3: tính thứ tự của x bằng tổ hợp, cộng k, dựng lại số thứ r (các bit 0 liên tiếp được gộp thành 1 bước).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. thuTu bắt đầu bằng 1 (tính cả chính $x$), mỗi bit 1 của $x$ ở vị trí $b$ cộng thêm $\binom{b}{c - daGap}$ – số các số nhỏ hơn $x$ "rẽ nhánh" tại bit $b$. Khi can > b thì không có cách nào (tổ hợp bằng 0) – điều kiện if(can <= b).
2. r = thuTu + k tối đa khoảng $1{,}26 \cdot 10^{14} + 10^{15}$ – vẫn vừa long long.
3. Nếu $r > \binom{50}{c}$: trong 50 bit không có đủ $r$ số có $c$ bit 1 → in $-1$ ngay.
4. Dựng xong $y < 2^{50}$ nhưng vẫn có thể lớn hơn $10^{15}$ (vì $2^{50} \approx 1{,}126 \cdot 10^{15}$) → kiểm tra lần cuối.

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

Thời gian$O(50^2 + 50 t)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.005s. Full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.042s (Python có sẵn math.comb).

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. Tăng x từng đơn vị tới khi đủ c bit 1	C++	3/20	0.027s	0%
2. Mẹo bit Gosper, lặp k lần	C++	10/20	0.003s	50%
	Python	10/20	0.026s	50%
3. Đếm tổ hợp: tính thứ tự rồi dựng số thứ r	C++	20/20	0.005s	100%
	Python	20/20	0.042s	100%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây, các test quá giờ bị dừng ở khoảng 4 giây). Kĩ thuật "đổi bài toán nhảy $k$ bước thành thứ tự + $k$, rồi dựng cấu hình theo thứ tự" rất hay gặp: số thứ $k$ có tính chất gì đó, hoán vị thứ $k$, xâu thứ $k$… Hai thao tác rank/unrank đều đi từ vị trí cao xuống thấp và đếm "số cách hoàn thành phần còn lại".

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 😇