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)
Đề bài
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.
()()(())(
5
1 2
2 3
1 6
6 9
1 91
0
3
1
7Giả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).
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 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.
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.
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]$.
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":
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]$:
Cách 3Gom nhóm + thuật toán Mo – O((n + Q)·√Q) (full)
- 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ớicnt[g]chỉ số cùng nhóm đang có, rồi tăng đếm. Ngược lạicur -= --cnt[g].
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% |