Dãy ngoặc đúng 2

Nguồn: CLUE OJ – Chương 20: Quay lui (Backtracking) Độ khó: Trung bình Quay lui Số Catalan

Đề bài

Người ta định nghĩa một dãy ngoặc đúng như sau:

• Xâu rỗng là một dãy ngoặc đúng.
• Nếu $A$ là dãy ngoặc đúng thì $(A)$ cũng là một dãy ngoặc đúng.
• Nếu $A$, $B$ là những dãy ngoặc đúng thì $AB$ cũng là dãy ngoặc đúng.

Những dãy ngoặc sau được xem là đúng: ()(()), ((())).

Những dãy ngoặc sau thì không: )(, ((()), )()(.

Nhiệm vụ của bạn trong bài tập này là liệt kê tất cả các dãy ngoặc đúng độ dài $n$.

Dữ liệu vào:

• Dòng thứ nhất là số nguyên dương $n$.

Kết quả:

• Dòng đầu tiên ghi số lượng dãy ngoặc đúng độ dài $n$.
• Các dòng tiếp theo mỗi dòng ghi một dãy ngoặc đúng độ dài $n$ theo thứ tự từ điển.

Ràng buộc: $1 \le n \le 27$.

Ví dụ – input

4

Ví dụ – output

2
(())
()()

Lời mở đầu

Bài này "họ hàng" rất gần với các bài Dãy nhị phân trong cùng contest: thay 0/1 bằng (/), và điều kiện bây giờ là "ngoặc đúng". Nếu sinh hết $2^n$ dãy rồi kiểm tra thì $n = 30$ sẽ có hơn 1 tỉ dãy – không kịp. Mình sẽ dùng hai bộ đếm (số ngoặc mở, số ngoặc đóng đã đặt) để cắt nhánh ngay từ đầu, sao cho mọi lá của cây quay lui đều là dãy đúng.

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ộ test30 testÝ tưởngmo, dongCách 1Sinh hết rồi lọcCách 2Cắt nhánh – AC

Bộ testBộ test chính thức có gì?

Bộ test có 30 test, mỗi test một số $n$: test 1 là $n = 4$ (test đề), test 2 là $n = 2$, test 3 là $n = 3$, test 4 là $n = 1$, các test 5 – 30 có $n$ bằng số thứ tự test. Một nửa số test có $n$ lẻ – khi đó đáp án chỉ là một dòng 0.

Test	$n$	Số test $n$ lẻ (đáp án 0)	Số dãy lớn nhất	File output lớn nhất
1 – 20	1 … 20	10	16.796	0,4 MB
21 – 27	21 … 27	4	742.900	20,8 MB
28 – 30	28 … 30	1	9.694.845	310,2 MB

Lưu ý: test vượt ràng buộc đề

Đề ghi $n \le 27$ nhưng test 28, 29, 30 có $n = 28, 29, 30$. Test 30 phải in $9\,694\,845$ dãy, file đáp án nặng khoảng 310 MB. Lưu hết các dãy vào bộ nhớ rồi mới in (để in số lượng trước) sẽ tốn hơn 300 MB – vượt giới hạn bộ nhớ 256 MB, nên ta phải tính trước số lượng rồi in thẳng.

Đề không chia subtask; mình chia 3 mức theo $n$:

Mức	Điều kiện	Các test	Cách 1 C++ sinh hết rồi lọc	Cách 1 Python	Cách 2 C++ cắt nhánh	Cách 2 Python
1	$n \le 20$	1 – 20	20/20	20/20	20/20	20/20
2	$21 \le n \le 27$	21 – 27	5/7	0/7	7/7	7/7
3	$28 \le n \le 30$ (vượt đề)	28 – 30	0/3	0/3	3/3	1/3

Ý tưởngHai bộ đếm: còn được mở không, có gì để đóng không

Một dãy ngoặc độ dài $n$ là đúng khi và chỉ khi: đọc từ trái sang phải, số ngoặc đóng không bao giờ vượt số ngoặc mở, và cuối cùng hai số bằng nhau (mỗi loại đúng $n/2$ cái). Từ đó, khi điền vị trí $i$ với mo ngoặc mở và dong ngoặc đóng đã đặt:

Quy tắc cắt nhánh

Được đặt ( khi mo < n/2 (chưa dùng hết ngoặc mở).
Được đặt ) khi dong < mo (còn ngoặc mở đang chờ được đóng).
Theo hai quy tắc này, đi tới vị trí cuối cùng thì luôn có mo = dong = n/2 → mọi lá đều là dãy ngoặc đúng.

Thứ tự từ điển: trong bảng mã ASCII, ( có mã 40, ) có mã 41, nên ( < ). Ở mỗi vị trí ta thử ( trước rồi mới ) là kết quả tự tăng dần – đúng như ví dụ: (()) đứng trước ()().

Số lượng: số dãy ngoặc đúng có $h = n/2$ cặp là số Catalan $C_h = \dfrac{1}{h+1}\binom{2h}{h}$: $C_1 = 1,$ $C_2$ $= 2,$ $C_3$ $= 5,$ $C_4$ $= 14,$ $\dots,$ $C_{15}$ $= 9\,694\,845$. Nếu $n$ lẻ thì không có dãy nào, in 0. Tính được số lượng trước nên ta in ngay dòng đầu, rồi vừa quay lui vừa in, không phải lưu gì.

Em nhập $n$, chọn có cắt nhánh (1) hoặc sinh hết rồi lọc (0), rồi bấm Tiếp để xem cây quay lui (nút đỏ ✗ là nhánh bị cắt, lá đỏ là dãy bị loại):

n Cắt nhánh? (1 = có, 0 = sinh hết rồi lọc)

Ví dụ nhanh:

Cách 1Sinh hết $2^n$ dãy rồi kiểm tra

Đi hết cây đầy đủ, mỗi lá kiểm tra bằng biến bal (số ngoặc mở đang chờ đóng): gặp ( tăng 1, gặp ) giảm 1, nếu có lúc âm hoặc cuối cùng khác 0 thì sai. Dãy đúng thì đếm và gom vào xâu res để in sau dòng số lượng.

C++▶ Chạy tay từng dòng codeCách 1: sinh đủ 2^n dãy ngoặc, đủ n ký tự mới gọi ok() kiểm tra.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n \cdot C_{n/2})$ cho xâu kết quả

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

Kết quả chạy thật: bản C++ đúng 25/30 test, quá thời gian ở test 26–30 – để ý cả test $n$ lẻ (27, 29) cũng TLE dù đáp án chỉ là 0, vì cách này vẫn cặm cụi sinh đủ $2^n$ dãy. Bản Python đúng 20/30 test, TLE từ test 21 trở đi.

Cách 2Quay lui cắt nhánh + đếm trước bằng số Catalan

C++▶ Chạy tay từng dòng codeCách 2: tính số Catalan trước, quay lui với 2 bộ đếm mo/dong, mọi lá đều đúng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. if(n % 2 == 1): $n$ lẻ thì in 0 và dừng luôn.
2. Vòng for tính $\binom{2h}{h}$ theo kiểu cat = cat * (h + k) / k: sau bước $k$, cat $= \binom{h+k}{k}$ nên phép chia luôn chia hết; cuối cùng chia cho $h + 1$ được số Catalan. Với $h = 15$ giá trị lớn nhất cỡ $1{,}5 \cdot 10^8$, long long thoải mái.
3. Trong Try: hai if độc lập (không phải else) vì có những vị trí đặt được cả hai loại ngoặc. Thứ tự ( trước, ) sau đảm bảo thứ tự từ điển.
4. Như bài Dãy nhị phân 1, dãy đang xây là mảng char có sẵn '\n' ở cuối, đủ $n$ ký tự thì fwrite cả dòng – in 310 MB vẫn nhanh.

Không gian$O(n)$

Thời gian$O(n \cdot C_{n/2})$

Kết quả chạy thật: bản C++ đúng 30/30 test, test nặng nhất ($n = 30$) chỉ mất 0,28 giây. Full điểm! 🎉 Bản Python (in theo từng khối 65 536 dòng) đúng 28/30 test, chỉ TLE ở test 28 và 30 – hai test vượt ràng buộc đề với 2,7 triệu và 9,7 triệu dòng.

Ghi chú của mình: cách sinh hết rồi lọc đúng 25/30 (C++), cách quay lui cắt nhánh đúng 30/30 (C++, tối đa 0,28 giây) và 28/30 (Python). Hai điểm cần nhớ: cắt nhánh bằng bộ đếm (mo < n/2, dong < mo) và khi đề bắt in số lượng trước mà output quá lớn thì tính số lượng bằng công thức (số Catalan) thay vì lưu hết kết quả.

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 😇