Dãy ngoặc đúng (Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng C2)

Nguồn: Tin học trẻ 2024 Độ khó: Khó Dãy ngoặc Tổng tiền tố Thuật toán Mo Ngăn xếp

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng C2 (bài Dãy ngoặc đúng). Đề 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).

Dãy ngoặc đúng được định nghĩa: xâu rỗng là dãy ngoặc đúng; nếu $A$ đúng thì $(A)$ đúng; nếu $A$ và $B$ đúng thì $AB$ đúng.

Cho xâu $S$ độ dài $N$ chỉ gồm ( và ), các kí tự đánh số $1..N$. Có $Q$ truy vấn, mỗi truy vấn cho $l \le r$: hãy đếm số cặp $(u, v)$ với $l \le u \le v \le r$ sao cho xâu con $S[u..v]$ là một dãy ngoặc đúng.

Dữ liệu vào:

Dòng 1: xâu $S$ ($1 \le |S| \le 10^5$).
Dòng 2: số nguyên dương $Q$ ($Q \le 10^5$).
$Q$ dòng tiếp theo: mỗi dòng hai số $l, r$ ($1 \le l \le r \le |S|$).

Kết quả: với mỗi truy vấn in trên một dòng số xâu con là dãy ngoặc đúng.

Subtask:

Subtask 1 (20%): $Q \le 50$, $|S| \le 100$;
Subtask 2 (20%): $Q \le 100$, $|S| \le 1000$;
Subtask 3 (40%): $Q \le 1000$;
Subtask 4 (20%): không có ràng buộc gì thêm.

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

Ví dụ – input

()()(())(
5
1 2
2 3
1 6
6 9
1 9

Ví dụ – output

Giải thích: $S$ = ()()(())(. Truy vấn $(1, 6)$ = ()()(( có 3 xâu con đúng: () ở vị trí 1–2, () ở 3–4 và ()() ở 1–4. Truy vấn $(1, 9)$ có 7 xâu: ba xâu trên, thêm () ở 6–7, (()) ở 5–8, ()(()) ở 3–8 và ()()(()) ở 1–8.

Lời mở đầu

Bài cuối của Bảng C2. Đếm xâu con ngoặc đúng của cả xâu thì là bài quen thuộc (ngăn xếp, $O(n)$). Cái khó là $10^5$ truy vấn đoạn. Mình đi từ duyệt trâu $O(Qn^2)$, qua ngăn xếp cho từng truy vấn $O(Qn)$ (80 điểm), rồi biến bài toán thành "đếm cặp cùng nhóm trong đoạn" để dùng thuật toán Mo (full).

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ộ test25 test Cách 1O(Qn²) – 40đ Cách 2O(Qn) – 80đ Ý tưởngnhóm cùng mức Cách 3Mo – 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 đề: 25 test (test 1 là ví dụ của đề). Xâu có nhiều kiểu: ngẫu nhiên, dãy ngoặc đúng ngẫu nhiên, ()()()... (rất nhiều xâu con đúng), ((( ... ))) lồng sâu, các khối đúng ngắn ghép lại, )))...((( (không có xâu con đúng nào).

Nhóm	Test	$\|S\|$ lớn nhất	$Q$ lớn nhất	Mọi truy vấn là cả xâu	Mọi đáp án = 0	Đáp án lớn nhất
Subtask 1	1–5	100	50	không có	test 4	1.275
Subtask 2	6–10	1.000	100	test 8	không có	125.250
Subtask 3	11–19	100.000	1.000	test 18	test 17	1.250.025.000
Subtask 4	20–25	100.000	100.000	test 25	không có	1.250.025.000

Với xâu ()()...() dài $10^5$, truy vấn cả xâu có đáp án $\binom{50001}{2}$ $= 1\,250\,025\,000$ – vượt int, phải dùng long long.

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

Lời giải cuối cùng trong bài 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 $O(Qn^2)$ C++	Cách 1 Python	Cách 2 $O(Qn)$ C++	Cách 2 Python	Cách 3 Mo C++
Subtask 1 (20%)	$Q \le 50$, $\|S\| \le 100$	1–5	5/5	5/5	5/5	5/5	5/5
Subtask 2 (20%)	$Q \le 100$, $\|S\| \le 1000$	6–10	5/5	4/5	5/5	5/5	5/5
Subtask 3 (40%)	$Q \le 1000$	11–19	0/9	0/9	9/9	0/9	9/9
Subtask 4 (20%)	không ràng buộc thêm	20–25	0/6	0/6	0/6	0/6	6/6

Cách 1Duyệt mọi xâu con – O(Q·n²) (Subtask 1, 2)

Với mỗi điểm đầu $u$, đi $v$ sang phải và giữ bal = số ( trừ số ). Xâu $[u, v]$ đúng khi bal == 0 và chưa lần nào bal < 0. Khi bal < 0 thì dừng luôn – thêm kí tự nào cũng không cứu được.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi điểm đầu u, đi v sang phải và giữ bal (xanh = xâu đúng, đỏ = thừa ")").

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

Dữ liệu mẫu:

Không gian$O(n)$

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

Kết quả chạy thật: Bản C++ đúng 10/25 test, quá thời gian test 11–25 (các test đúng chạy lâu nhất 0.022s). Bản Python đúng 9/25 test, quá thời gian test 8, 11–25 (các test đúng chạy lâu nhất 0.315s). Bản C++ ăn subtask 1, 2 (40 điểm).

Cách 2Ngăn xếp cho từng truy vấn – O(Q·n) (Subtask 1, 2, 3)

Gọi $e[i]$ = số xâu con đúng kết thúc tại $i$ (trong đoạn đang xét). Duyệt $i$ từ $l$ tới $r$ với ngăn xếp các vị trí ( chưa ghép:

Gặp (: đẩy $i$ vào ngăn xếp, $e[i] = 0$.
Gặp ) và ngăn xếp có $j$ ở đỉnh: $S[j..i]$ là một khối đúng "nguyên", và mọi xâu đúng kết thúc tại $j - 1$ ghép thêm khối này cũng đúng: $e[i] = e[j-1] + 1$.
Gặp ) mà ngăn xếp rỗng: không xâu nào kết thúc ở đây.

Đáp án truy vấn $= \sum e[i]$.

C++▶ Chạy tay từng dòng codeCách 2: ngăn xếp các "(" chưa ghép; e[i] = số xâu đúng kết thúc tại i = e[j − 1] + 1.

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

Dữ liệu mẫu:

Không gian$O(n)$

Thời gian$O(Q \cdot n)$

Kết quả chạy thật: Bản C++ đúng 19/25 test, quá thời gian test 20–25 (các test đúng chạy lâu nhất 0.219s). Bản Python đúng 10/25 test, quá thời gian test 11–25 (các test đúng chạy lâu nhất 0.027s). Bản C++ được 80 điểm (subtask 1, 2, 3): $Q = 1000$ và $n = 10^5$ là $10^8$ bước đơn giản, chạy khoảng 0,2 giây; nhưng $Q = 10^5$ thì $10^{10}$ – quá xa.

Ý tưởngTổng tiền tố và các nhóm cùng mức

Đặt $P_0 = 0$, $P_i = P_{i-1} \pm 1$ (cộng 1 với (, trừ 1 với )). Vẽ $P$ thành một "dãy núi":

Nhận xét 1

Xâu $S[u..v]$ đúng $\iff$ $P_{u-1} = P_v$ và mọi $P_t$ với $u - 1 \le t \le v$ đều $\ge P_v$ (đường núi không xuống thấp hơn hai đầu).

Nhận xét 2 – gom nhóm

Chia các chỉ số $0..n$ thành nhóm: hai chỉ số cùng nhóm nếu cùng độ cao $P$ và giữa chúng núi không xuống thấp hơn. Khi đó $[u, v]$ đúng $\iff$ $u - 1$ và $v$ cùng nhóm. Hơn nữa, nếu $u-1$ và $v$ cùng nằm trong $[l-1, r]$ thì điều kiện này chỉ phụ thuộc hai chỉ số, nên: $$\text{đáp án}(l, r) = \sum_{\text{nhóm}} \binom{k}{2}, \quad k = \text{số chỉ số của nhóm nằm trong } [l-1, r].$$

Tính nhóm trong $O(n)$: giữ mo[h] = nhóm "đang mở" ở độ cao $h$. Khi gặp ) (đi xuống từ $h$ tới $h-1$) thì nhóm ở độ cao $h$ đóng lại (lần sau lên lại độ cao $h$ là nhóm mới). Mỗi chỉ số nhận nhóm đang mở ở độ cao của nó (chưa có thì tạo mới).

Bài toán còn lại: "đếm số cặp cùng màu trong đoạn" – dạng kinh điển của thuật toán Mo: sắp xếp truy vấn theo khối $\sqrt{}$ của đầu trái, dịch hai đầu đoạn từng bước; thêm một chỉ số nhóm $g$ thì số cặp tăng cnt[g], bớt đi thì giảm cnt[g] - 1.

Em nhập xâu và một truy vấn rồi bấm Tiếp: các điểm của dãy núi $P$ được gán nhóm dần (cùng màu = cùng nhóm), bước cuối đếm $\binom{k}{2}$ trong đoạn $[l-1, r]$:

S = l = r =

Ví dụ nhanh:

Cách 3Gom nhóm + thuật toán Mo – O((n + Q)·√Q) (full)

C++▶ Chạy tay từng dòng codeCách 3: gom các chỉ số 0..n thành nhóm (cùng màu trên dãy núi P), rồi thuật toán Mo dịch đoạn [curL, curR] (khung vàng).

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

Dữ liệu mẫu:

Mảng mo đánh chỉ số theo $h + n + 1$ vì độ cao $h$ có thể âm (tới $-n$).
Kích thước khối B = (n + 1) / sqrt(q) cho tổng số bước dịch khoảng $(n+1)\sqrt{Q} \approx 3 \cdot 10^7$. Mẹo đổi chiều sắp xếp $R$ ở các khối lẻ ("zig-zag") giúp đầu phải không phải chạy ngược về đầu mỗi khối – nhanh thêm khoảng gấp đôi.
Thứ tự bốn vòng while: mở rộng trước, thu hẹp sau, để đoạn đang có không bao giờ "âm".
cur += cnt[g]++: chỉ số mới tạo cặp với cnt[g] chỉ số cùng nhóm đang có, rồi tăng đếm. Ngược lại cur -= --cnt[g].

Không gian$O(n + Q)$

Thời gian$O(Q \log Q + (n + Q)\sqrt{Q})$

Kết quả chạy thật: Bản C++ đúng 25/25 test, chạy lâu nhất 0.071s. Full điểm. (Mình không viết bản Python cho cách này vì $3 \cdot 10^7$ bước dịch trong Python mất hàng chục giây.)

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. Duyệt mọi xâu con $O(Qn^2)$	C++	10/25	0.022s	40%
	Python	9/25	0.315s	20%
2. Ngăn xếp cho từng truy vấn $O(Qn)$	C++	19/25	0.219s	80%
	Python	10/25	0.027s	40%
3. Gom nhóm + thuật toán Mo	C++	25/25	0.071s	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 0,5 giây). Lưu ý bài này khác bài "Dãy ngoặc đúng" kiểm tra một xâu ba loại ngoặc đã có trên CLUE. Bài học: với dãy ngoặc hãy nghĩ ngay tới tổng tiền tố (dãy núi); và khi truy vấn đoạn có thể thêm/bớt một phần tử ở hai đầu trong $O(1)$ thì thuật toán Mo gần như luôn dùng được.

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