Substr (Tin học trẻ toàn quốc 2024 – Vòng sơ khảo – Bảng B, C1, C2)

Nguồn: Tin học trẻ 2024 Độ khó: Khó Xâu Quy hoạch động đếm Thứ tự từ điển

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng sơ khảo – Bảng B, Bảng C1 và Bảng C2 (bài substr – substring, ở đây là "xâu con"). Đề 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).

Xâu $s$ gọi là xâu con của xâu $x$ nếu ta nhận được $s$ từ $x$ bằng cách giữ nguyên $x$ hoặc xoá đi một số kí tự của $x$ (các kí tự còn lại giữ nguyên thứ tự). Ví dụ bb là xâu con của bab, còn aa thì không.

Cho hai xâu $x$ và $y$. Ta liệt kê theo thứ tự từ điển tất cả các xâu đôi một khác nhau có độ dài $n$ mà là xâu con của $x$ nhưng không là xâu con của $y$. Ví dụ với $x =$ abab, $y =$ abb, $n = 2$ thì danh sách là aa, ba.

Yêu cầu: cho $x$, $y$ và $m$ xâu $s_1, s_2, \dots, s_m$ cùng độ dài $n$. Với mỗi $s_i$, tìm thứ tự (đánh số từ $1$) của $s_i$ trong danh sách trên.

Dữ liệu vào:

Dòng 1: ba số nguyên dương $m, n, k$ ($m, n \le 200$; $k \le 10^9$);
Dòng 2: xâu $x$; dòng 3: xâu $y$;
$m$ dòng tiếp theo, dòng thứ $i$ là xâu $s_i$ (độ dài đúng bằng $n$).

Các xâu dài không quá $200$ và chỉ gồm chữ cái thường a…z.

Kết quả: $m$ dòng. Gọi $p_i$ là thứ tự của $s_i$; dòng thứ $i$ ghi $p_i \bmod k$ (số dư khi chia $p_i$ cho $k$). Nếu $s_i$ không là xâu con của $x$, hoặc $s_i$ là xâu con của $y$, thì ghi $-1$.

Subtask:

Subtask 1 (10%): $|x|, |y| \le 16$ và $n = 1$;
Subtask 2 (50%): $|x|, |y| \le 16$;
Subtask 3 (40%): không có ràng buộc gì thêm.

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

3 2 100
abab
abb
aa
ab
ba

Ví dụ – output

1
-1
2

Giải thích: danh sách là aa, ba. Xâu aa đứng thứ $1$, ba đứng thứ $2$; còn ab là xâu con của $y =$ abb nên in $-1$.

Lời mở đầu

Đây là bài khó nhất đề sơ khảo 2024 và là đề chung cho cả ba bảng B, C1, C2. Với xâu dài 200, số xâu con có thể lên tới cỡ $2^{200}$ – không thể liệt kê, vì vậy đề mới bắt in thứ tự theo modulo $k$. Muốn "đếm mà không liệt kê", ta cần hai mảnh ghép: (1) cách đếm các xâu con khác nhau mà không bị trùng – dùng ô-tô-mát xâu con (khớp tham lam); (2) mẹo tìm thứ tự từ điển quen thuộc: thứ tự của $s$ = số xâu hợp lệ nhỏ hơn $s$, cộng 1. Mình đi từ cách chỉ làm $n = 1$ (10 điểm), sang vét cạn bitmask (60 điểm), rồi tới quy hoạch động đầy đủ.

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 Cách 1n = 1 – 10đ Cách 2bitmask – 60đ Ý tưởngkhớp tham lam Cách 3QHĐ – 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ệ subtask của đề: 20 test (test 1 là ví dụ của đề). Mỗi test có tới 200 câu hỏi.

Nhóm	Test	$\|x\|$ max	$\|y\|$ max	$n$	Số chữ cái khác nhau trong $x$	Các giá trị $k$	Số câu hỏi / số câu trả lời $-1$
Subtask 1	2–3	16	16	1–1	5, 13	3, 1.000.000.000	56 / 20
Subtask 2	1, 4–12	16	16	2–16	2, 3, 4, 6, 11	1, 7, 100, 1.000, 123.456.789, 999.999.937, 1.000.000.000	1.403 / 561
Subtask 3	13–20	200	200	30–200	2, 3, 4, 5, 26	2, 7, 998.244.353, 999.999.937, 999.999.999, 1.000.000.000	1.600 / 482

Test 9 có $n > |x|$ nên mọi câu trả lời là $-1$; test 10 có $x = y$ nên cũng toàn $-1$ (mọi xâu con của $x$ đều là xâu con của $y$).
Test 11 có $k = 1$ nên mọi thứ tự hợp lệ đều in ra $0$ – bẫy cho bạn nào quên lấy mod ở trường hợp "đếm được 0 xâu nhỏ hơn" (phải in $(0 + 1) \bmod 1 = 0$, không phải $1$).
Subtask 3 có test chữ cái ít ($2$–$5$ loại) để số xâu con khác nhau cực lớn, và test $n = 200 = |x|$ (chỉ còn đúng một xâu con là chính $x$).

Đã 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 C++	Cách 1 Python	Cách 2 C++	Cách 2 Python	Cách 3 C++	Cách 3 Python
Subtask 1 (10%)	$\|x\|, \|y\| \le 16$, $n = 1$	2–3	2/2	2/2	2/2	2/2	2/2	2/2
Subtask 2 (50%)	$\|x\|, \|y\| \le 16$	1, 4–12	2/10	2/10	10/10	10/10	10/10	10/10
Subtask 3 (40%)	không ràng buộc thêm	13–20	0/8	0/8	0/8	0/8	8/8	8/8

Cách 1Chỉ làm n = 1 (Subtask 1)

Khi $n = 1$, mỗi "xâu" chỉ là một chữ cái $c$. Chữ $c$ hợp lệ khi nó có trong $x$ và không có trong $y$. Thứ tự của $c$ = số chữ cái hợp lệ nhỏ hơn $c$, cộng 1.

C++▶ Chạy tay từng dòng codeCách 1 (n = 1): đếm số chữ cái hợp lệ nhỏ hơn c.

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

Dữ liệu mẫu:

Không gian$O(|x| + |y|)$

Thời gian$O(|x| + |y| + 26m)$

Kết quả chạy thật: Bản C++ đúng 4/20 test, sai test 1, 4–8, 11–20 (các test đúng chạy lâu nhất 0.003s). Ngoài test 2, 3 của subtask 1 thì cách này chỉ "đúng ké" test 9, 10 (hai test toàn $-1$) → 10 điểm.

Cách 2Liệt kê mọi xâu con bằng bitmask (Subtask 1, 2)

Với $|x| \le 16$, $x$ chỉ có $2^{16} = 65536$ cách chọn tập vị trí. Mỗi tập có đúng $n$ vị trí (bit 1) cho một xâu con độ dài $n$. Bỏ vào set<string> để vừa loại trùng vừa tự sắp theo thứ tự từ điển, chỉ giữ các xâu không là xâu con của $y$ (kiểm tra bằng khớp tham lam hai con trỏ). Mỗi câu hỏi tìm $s$ trong danh sách bằng lower_bound.

C++▶ Chạy tay từng dòng codeCách 2: duyệt mọi bitmask chọn n vị trí của x, lọc bằng isSub, tìm bằng lower_bound.

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

Dữ liệu mẫu:

Hàm isSub(s, t): duyệt $t$ từ trái sang, gặp kí tự trùng với kí tự đang chờ của $s$ thì tiến con trỏ $j$. Khớp càng sớm càng tốt không bao giờ thiệt, nên đây là cách kiểm tra đúng.
Thứ tự thật $p \le 2^{16}$ nên không tràn; chỉ cần in p % k.
Bản Python dùng itertools.combinations(range(len(x)), n) – sinh thẳng các tập đúng $n$ vị trí.

Không gian$O\big(\binom{|x|}{n} \cdot n\big)$

Thời gian$O(2^{|x|} \cdot (|x| + |y|) + m \cdot n \log)$

Kết quả chạy thật: Bản C++ đúng 12/20 test, sai test 13–20 (các test đúng chạy lâu nhất 0.008s) → 60 điểm. Bản Python đúng 12/20 test, sai test 13–20 (các test đúng chạy lâu nhất 0.045s). Các test subtask 3 có $|x| = 200$ nên chương trình dừng ngay (không thể duyệt $2^{200}$ tập).

Ý tưởngĐếm xâu con khác nhau bằng khớp tham lam

Mảnh ghép 1 – mỗi xâu con ứng với đúng một đường khớp tham lam. Gọi $nx[i][c]$ là vị trí đầu tiên $\ge i$ trong $x$ có kí tự $c$. Một xâu $s$ là xâu con của $x$ khi ta khớp lần lượt từng kí tự vào vị trí sớm nhất có thể: bắt đầu $i = 0$, đọc kí tự $c$ thì nhảy tới $i = nx[i][c] + 1$; nếu $nx[i][c]$ không tồn tại thì $s$ không phải xâu con. Vì đường khớp tham lam là duy nhất cho mỗi $s$, đếm các đường đi trên "ô-tô-mát" này chính là đếm các xâu con khác nhau – không lo đếm trùng như khi chọn tập vị trí.

Làm y hệt cho $y$ với trạng thái $j$, thêm một trạng thái đặc biệt DEAD $= |y| + 1$: "đã khớp hỏng, xâu không còn là xâu con của $y$" (DEAD đọc gì cũng vẫn DEAD). Một xâu hợp lệ là xâu đi hết mà vẫn sống bên $x$ và kết thúc ở DEAD bên $y$.

Mảnh ghép 2 – quy hoạch động đếm. Gọi

$$f[L][i][j] = \text{số xâu độ dài } L \text{ đi được từ trạng thái } (i, j) \text{ và kết thúc ở DEAD bên } y,$$

tức là số xâu độ dài $L$ là xâu con của $x[i..]$ nhưng không là xâu con của $y[j..]$. Ta có $f[0][i][j] = 1$ nếu $j = $ DEAD, ngược lại $0$, và

$$f[L][i][j] = \sum_{c:\ nx[i][c] \text{ tồn tại}} f[L-1]\big[nx[i][c] + 1\big]\big[\text{goY}(j, c)\big] \pmod k.$$

Mảnh ghép 3 – thứ tự từ điển. Thứ tự của $s$ = (số xâu hợp lệ nhỏ hơn $s$) + 1. Xâu $t < s$ thì có một vị trí $p$ đầu tiên khác nhau: $t$ giữ nguyên $s[0..p-1]$, ở vị trí $p$ đặt kí tự $c < s[p]$, phần sau tuỳ ý. Đi theo $s$ trên ô-tô-mát; tại mỗi vị trí $p$ (đang ở trạng thái $(i, j)$), với mọi $c < s[p]$ cộng thêm $f[n-p-1][nx[i][c]+1][\text{goY}(j, c)]$. Cuối cùng kiểm tra $s$ có hợp lệ không (sống bên $x$, DEAD bên $y$).

Em nhập $x$, $y$, $s$ ngắn rồi bấm Tiếp: mỗi bước là một kí tự $c < s[p]$ được thử, hình cho thấy kí tự đó khớp vào đâu trong $x$ và $y$, và đúng những xâu nào (in đậm trong danh sách) vừa được đếm:

x = y = s =

Ví dụ nhanh:

Cách 3Ô-tô-mát xâu con + QHĐ – O(n·|x|·|y|·26) (full)

C++▶ Chạy tay từng dòng codeCách 3: QHĐ f[L][i][j] trên ô-tô-mát xâu con của x và y, rồi đếm các xâu nhỏ hơn s.

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

Dữ liệu mẫu:

nx, ny tính từ phải sang trái: bảng ở vị trí $i$ chép từ vị trí $i + 1$ rồi sửa riêng kí tự $x[i]$. Hàm goY trả về trạng thái mới của $y$, trong đó DEAD luôn đi về DEAD.
if (lx - i < L) continue;: còn ít hơn $L$ kí tự thì không có xâu con độ dài $L$ – bỏ qua cho nhanh gấp đôi (mảng toàn cục sẵn bằng 0).
Mọi giá trị $f$ đều $< k \le 10^9$ nên vừa unsigned (4 byte); tổng 26 số $< 2{,}6 \cdot 10^{10}$ cần long long rồi mới lấy mod. Mảng $202 \times 202 \times 203$ số 4 byte $\approx 33$ MB.
1 % k và (cnt + 1) % k: nhờ vậy test $k = 1$ in ra $0$ đúng.
Đếm số dư rồi mới cộng 1 là đúng vì $(a + 1) \bmod k = ((a \bmod k) + 1) \bmod k$.

Không gian$O(n \cdot |x| \cdot |y|)$

Thời gian$O(26 \cdot n \cdot |x| \cdot |y| + 26 \cdot m \cdot n)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.175s. Full điểm. Số phép tính khoảng $200 \cdot 200 \cdot 200 \cdot 26 / 2 \approx 10^8$ phép cộng đơn giản.

Python: vòng lặp 4 tầng $10^8$ phép thì Python thuần cần cả phút. Mình viết lại bằng numpy: với mỗi $L$ và mỗi kí tự $c$, cả ma trận $f[L-1]$ được "bốc" theo hai mảng chỉ số np.ix_(nx[:, c], ny[:, c]) và cộng dồn – 26 phép trên ma trận thay cho 40 nghìn phép lẻ. Phần trả lời câu hỏi cũng cộng 26 ô một lúc. Bản Python + numpy đúng 20/20 test, chạy lâu nhất 0.681s. (Lưu ý: hệ thống chấm cần có cài numpy.)

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 = 1$	C++	4/20	0.003s	10%
	Python	4/20	0.022s	10%
2. Duyệt mọi xâu con của $x$ (bitmask)	C++	12/20	0.008s	60%
	Python	12/20	0.045s	60%
3. Ô-tô-mát xâu con + QHĐ đếm	C++	20/20	0.175s	100%
	Python + numpy	20/20	0.681s	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). Bài này gom ba kỹ thuật rất đáng nhớ: (1) ô-tô-mát xâu con $nx[i][c]$ – khớp tham lam để mỗi xâu con khác nhau được đếm đúng một lần; (2) trạng thái "đã chết" để đếm những xâu không là xâu con của $y$; (3) tìm thứ tự từ điển bằng cách đếm các xâu nhỏ hơn theo từng tiền tố chung – cùng khuôn với bài "tìm hoán vị/xâu thứ $k$".

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 😇

Lập Trình Thuật Toán