Biểu thức ngoặc (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B)

Nguồn: Tin học trẻ 2024 Độ khó: Khá Quy hoạch động đếm Thứ tự từ điển Số lớn Dãy ngoặc

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B (bài Biểu thức ngoặc). 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).

Biểu thức ngoặc là xâu chỉ gồm 6 kí tự ( ) [ ] { }. Biểu thức ngoặc đúng và bậc của nó được định nghĩa như sau:

• Xâu rỗng là biểu thức ngoặc đúng, bậc $0$.
• Nếu $A$ đúng, bậc $k$ thì ($A$), [$A$], {$A$} đúng, bậc $k + 1$.
• Nếu $A$, $B$ đúng với bậc $k_1$, $k_2$ thì $AB$ (viết $B$ ngay sau $A$) đúng, bậc $\max(k_1, k_2)$.

Nói cách khác, bậc chính là độ sâu lồng nhau lớn nhất. Ví dụ ()[()] có bậc 2, {()[{}]} có bậc 3.

Với hai số $n, k$, liệt kê tất cả biểu thức ngoặc đúng độ dài $n$, bậc không vượt quá $k$, rồi sắp xếp theo thứ tự từ điển, trong đó thứ tự các kí tự là:

$$\texttt{(} < \texttt{)} < \texttt{[} < \texttt{]} < \texttt{\{} < \texttt{\}}$$

Yêu cầu: cho $n, k$ và một biểu thức ngoặc đúng $S$, hãy cho biết $S$ đứng ở vị trí thứ mấy trong danh sách (đánh số từ 1).

Dữ liệu vào:

• Dòng 1: hai số nguyên $n, k$ ($n \le 200$; $k \le 5$).
• Dòng 2: xâu $S$ độ dài $n$.

Dữ liệu đảm bảo $S$ là biểu thức ngoặc đúng có bậc không vượt quá $k$.

Kết quả: một số nguyên là thứ tự của $S$.

Subtask:

• Subtask 1 (40%): $n \le 10$;
• Subtask 2 (40%): $n \le 30$;
• Subtask 3 (20%): 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

2 1
[]

Ví dụ – output

2

Giải thích: các biểu thức đúng độ dài 2, bậc không quá 1, theo thứ tự từ điển là (), [], {}. Xâu [] đứng thứ 2.

Lưu ý: đáp án có thể rất lớn – với $n = 200$ đáp án dài tới hơn 100 chữ số, vượt xa long long. Đề không nói rõ nhưng vì $S$ là biểu thức đúng nên $n$ luôn chẵn; bộ test có $2 \le n \le 200$, $1 \le k \le 5$.

Lời mở đầu

Đây là dạng bài kinh điển "tìm thứ tự từ điển của một cấu hình" (rank). Cách nghĩ chung: thứ tự của $S$ = $1 +$ số cấu hình nhỏ hơn $S$; và mọi cấu hình nhỏ hơn $S$ đều có dạng "giống $S$ ở $i$ kí tự đầu, kí tự thứ $i + 1$ nhỏ hơn, phần còn lại tuỳ ý" – nên chỉ cần đếm số cách điền phần còn lại. Mình đi từ cách sinh lần lượt (40 điểm) → đếm bằng quy hoạch động (80 điểm) → thêm số lớn (100 điểm).

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đếm W[r][h]Cách 1sinh – 40đCách 2long long – 80đCách 3số lớn – 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ả $S$ đứng đầu danh sách (đáp án 1), đứng cuối danh sách, và $S$ có bậc đúng bằng $k$.

Nhóm	Test	Các giá trị $n$	Các giá trị $k$	Đáp án dài nhất	Test đáp án = 1	Test có bậc của $S$ đúng bằng $k$
Subtask 1	1–8	2, 6, 8, 10	1, 2, 3, 4, 5	5 chữ số	test 5	test 1–5, 7
Subtask 2	9–16	26, 28, 30	1, 2, 3, 4, 5	14 chữ số	test 15	test 10–11, 13–16
Subtask 3	17–20	198, 200	1, 3, 5	98 chữ số	không có	test 17, 19–20

Đã 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 sinh lần lượt	Cách 1 Python	Cách 2 đếm, long long	Cách 3 đếm, số lớn	Cách 3 Python
Subtask 1 (40%)	$n \le 10$	1–8	8/8	8/8	8/8	8/8	8/8
Subtask 2 (40%)	$n \le 30$	9–16	2/8	1/8	8/8	8/8	8/8
Subtask 3 (20%)	không ràng buộc thêm	17–20	0/4	0/4	0/4	4/4	4/4

Ý tưởngĐếm số cách hoàn thành một tiền tố

Khi đã viết xong một tiền tố, phần còn lại chỉ phụ thuộc vào số kí tự còn phải viết $r$ và số ngoặc đang mở $h$ (độ sâu hiện tại). Loại của các ngoặc đang mở không làm thay đổi số cách: mỗi lần đóng thì loại ngoặc đóng bị ép (phải khớp ngoặc mở gần nhất), còn mỗi lần mở có 3 lựa chọn. Gọi:

$$W[r][h] = \text{số cách viết } r \text{ kí tự còn lại khi đang mở } h \text{ ngoặc, kết thúc đúng và độ sâu không bao giờ vượt } k.$$

• $W[0][0] = 1$, $W[0][h] = 0$ với $h > 0$.
• $W[r][h]$ $= \underbrace{W[r-1][h-1]}_{\text{đóng (nếu } h > 0)}$ $+ \underbrace{3 \cdot W[r-1][h+1]}_{\text{mở (nếu } h < k)}$.

Rồi tính thứ tự: duyệt $i = 0..n-1$, giữ ngăn xếp các ngoặc đang mở theo $S$. Tại vị trí $i$, thử mọi kí tự $c$ nhỏ hơn $S[i]$ mà đặt được (ngoặc mở thì độ sâu mới $\le k$; ngoặc đóng thì phải khớp đỉnh ngăn xếp), mỗi kí tự như vậy cộng thêm $W[n - i - 1][h']$ với $h'$ là độ sâu mới. Sau đó đi tiếp theo đúng kí tự $S[i]$. Đáp án $= 1 + $ tổng đã cộng.

Em nhập $k$ và $S$ rồi bấm Tiếp để xem từng nhóm biểu thức nhỏ hơn $S$ được đếm (ô vàng trong bảng $W$ là số được cộng):

k = S =

Ví dụ nhanh:

Cách 1Sinh lần lượt theo thứ tự từ điển (Subtask 1)

Quay lui điền từng vị trí, thử các kí tự theo đúng thứ tự ( ) [ ] { } – khi đó các biểu thức được sinh ra đúng theo thứ tự từ điển. Đếm số biểu thức đã sinh, gặp $S$ thì in số đếm và dừng.

C++▶ Chạy tay từng dòng codeCách 1: quay lui sinh các biểu thức theo thứ tự từ điển, đếm tới khi gặp S.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Ngoặc mở chỉ đặt khi độ sâu mới $h + 1 \le k$ và còn đủ chỗ để đóng hết: $h + 1 \le$ số kí tự còn lại sau vị trí này $= con - 1$. Nhờ điều kiện này, mọi nhánh đều đi tới được một biểu thức đúng (không có nhánh "chết").
• Ngoặc đóng chỉ đặt khi khớp loại với đỉnh ngăn xếp.

Số biểu thức phải sinh có thể bằng chính đáp án: với $n = 10$ tối đa $3^5 \cdot 42 = 10\,206$ biểu thức – tức thì; với $n = 30$ thì tới cỡ $10^{14}$ – không thể.

Không gian$O(n)$

Thời gian$O(\text{đáp án} \cdot n)$

Kết quả chạy thật: Bản C++ đúng 10/20 test, quá thời gian test 9, 11–14, 16–20 (các test đúng chạy lâu nhất 0.328s). Ăn trọn subtask 1, và "ăn may" thêm 2 test của subtask 2: test 10 (bậc $k = 1$, đáp án chỉ khoảng 9 triệu) và test 15 (đáp án bằng 1 nên sinh biểu thức đầu tiên là gặp ngay). Bản Python đúng 9/20 test, quá thời gian test 9–14, 16–20 (các test đúng chạy lâu nhất 0.048s).

Cách 2Đếm bằng quy hoạch động – long long (Subtask 1, 2)

Làm đúng như phần ý tưởng với kiểu long long. Với $n \le 30$, số biểu thức không quá $3^{15} \cdot C_{15} \approx 1{,}4 \cdot 10^{14}$ ($C_{15}$ là số Catalan) nên vừa long long.

C++▶ Chạy tay từng dòng codeCách 2: lập bảng W[r][h] rồi cộng số cách hoàn thành của mọi tiền tố nhỏ hơn S (long long).

Dữ liệu vào (stdin) – sửa thoải mái6 2 [()]{}

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. W[r][h] với $h$ chỉ từ $0$ tới $k$ – điều kiện "độ sâu không vượt $k$" nằm ở chỗ chỉ cộng nhánh mở khi h < k.
2. Kí tự $c$ có mã chẵn (0, 2, 4) là ngoặc mở, mã lẻ là ngoặc đóng; loại ngoặc là c / 2.
3. Tại vị trí $i$ còn $r = n - i - 1$ kí tự phía sau; đặt ngoặc mở thì còn mở $h + 1$, đặt ngoặc đóng thì còn $h - 1$.

Không gian$O(n k)$

Thời gian$O(n k)$

Kết quả chạy thật: Bản C++ đúng 16/20 test, sai test 17–20 (các test đúng chạy lâu nhất 0.004s). Đúng 80 điểm: các test $n \approx 200$ bị tràn số nên in ra số sai.

Cách 3Thêm số lớn (full)

Thuật toán giữ nguyên, chỉ thay long long bằng số lớn tự cài. Ta chỉ cần hai phép: cộng hai số lớn và nhân số lớn với số nhỏ (nhân 3). Lưu số lớn dạng mảng các "chữ số" cơ số $10^9$, chữ số thấp đứng trước – cộng/nhân giống hệt cách làm tay, có biến nhớ nho.

C++▶ Chạy tay từng dòng codeCách 3: như cách 2 nhưng dùng số lớn cơ số 10^9 – khung này đi vào chi tiết hàm cong khi cộng vào ans.

Dữ liệu vào (stdin) – sửa thoải mái6 2 [()]{}

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Cơ số $10^9$: mỗi "chữ số" nhỏ hơn $10^9$ nên a[i] * 3 + nho và a[i] + b[i] + nho đều vừa long long.
• In ra: chữ số cao nhất in bình thường, các chữ số sau phải in đủ 9 chữ số (thêm số 0 đằng trước) – setw(9) << setfill('0').
• Bảng $W$ có $(n+1)(k+1) \le 201 \cdot 6$ số lớn, mỗi số khoảng 13 "chữ số" – rất nhỏ.

Với Python thì không cần tự cài: số nguyên Python tự động là số lớn, chỉ cần chép cách 2.

Không gian$O(n k \cdot L)$ với $L$ là số "chữ số" của số lớn

Thời gian$O(n k \cdot L)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.027s.

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. Sinh lần lượt theo thứ tự từ điển	C++	10/20	0.328s	40%
	Python	9/20	0.048s	40%
2. Đếm bằng quy hoạch động (long long)	C++	16/20	0.004s	80%
3. Đếm bằng quy hoạch động + số lớn	C++	20/20	0.004s	100%
	Python	20/20	0.027s	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). Công thức "thứ tự = 1 + tổng số cách hoàn thành của các tiền tố nhỏ hơn" dùng được cho rất nhiều bài: thứ tự hoán vị, thứ tự tổ hợp, thứ tự dãy nhị phân… Mấu chốt là tìm ra trạng thái nhỏ gọn quyết định số cách hoàn thành – ở đây là (số kí tự còn lại, độ sâu) chứ không phải toàn bộ ngăn xếp.

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 😇