🔗 Link: https://lqdoj.edu.vn/problem/bracket

📌 Tags: Tutorial, DP, Segment Tree

👤 Writer: @SPyofgame

Cách tiếp cận dễ thấy:

Với một cách tiếp cận đơn giản mình có thể xét dp \(f[l][r]\) là số dãy ngoặc đúng lớn nhất đếm được xét trên xâu con \(s[l, r]\).

Để tính giá trị \(f[l][r]\) thì mình có các công thức như sau:

• (A) \(f[l][r] = 0\) khi \(l > r\).

Nó là như vậy vì dãy này là dãy rỗng.

Tất nhiên mình gán nó giá trị nào cũng được nhưng mình sẽ gán nó giá trị \(=0\) để tiện tính toán và đỡ phải xử lí trường hợp.

• (B) \(f[l][r] = f[l+1][r-1] + 2\) khi \(s[l] =\) '(' và \(s[r] =\) ')'.

Vì mình tạo được một cặp ngoặc đúng.

Nhưng việc tạo cặp ngoặc đúng này không làm ảnh hưởng tới kết quả, hay nói cách khác là không tồn tại cách tốt hơn mà bắt cặp 2 ngoặc này thành 2 cặp ngoặc khác.

• (C) \(f[l][r] = max(f[l+1][r], f[l][r-1])\) khi không thỏa \((A)\) và \((B)\).

Vì mình không thể tạo được một cặp ngoặc đúng, nên tồn tại ít nhất 1 trong hai thằng cần xóa đi để tạo dãy ngoặc dài nhất.

Vậy là mình xét 2 trường hợp, là xóa thằng trái, hoặc xóa thẳng phải, để tạo nên dãy ngoặc dài nhất là được.

Tới đây chúng ta thu được độ phức tạp là \(O(n^2 + q)\) vì việc tiền xử lí mất \(O(n^2)\) và \(q\) truy vấn có thể trả lời được trong \(O(1)\) vì kết quả không cần được tính lại.

Cũng tương tự, mình có thể tối ưu nếu ta đổi sang thuật toán \(Mo\) chia làm \(O(\sqrt{n})\) đoạn, đỡ phải lưu toàn bộ \(O(n^2)\) trạng thái.

Lúc này việc xử lí offline tốn mất \(O(n \sqrt{n})\) và mỗi truy vấn trả lời trong \(O(\sqrt{n})\) nên độ phức tạp là \(O(n \sqrt{n} + q \sqrt{n})\).

Cách tiếp cận tốt hơn:

Với một số bài liên quan tới dãy ngoặc đúng, khi đính \(f[l][r]\) ta có thể thử chia nó làm 2 phần là \(f[l][k]\) và \(f[k+1][r]\) với \(l \leq k < r\).

Tại sao phải làm như vậy, vì bằng cách này ta có thể có được những cách tối ưu khác như:

• Quy hoạch động chia để trị.

• Các kiểu tối ưu quy hoạch động.

• Dùng cấu trúc dữ liệu để tối ưu.

Trong bài này, thì ta có thể tính như sau:

• \(f[l][r] = f[l+1][r-1]\) với trường hợp \(s[l], s[r]\) tạo thành cặp ngoặc đúng.

• \(f[l][r] = max(f[l][k] + f[k+1][r] + cost(l, k, r) | k = l \rightarrow r - 1)\) với \(cost(l, k, r)\) là số cặp ngoặc đúng được thêm vô khi chia dãy tại vị trí \(k\).

Nhưng cách này sẽ là \(O(n^3)\) rất là chậm, tuy nhiên nó đưa mình tới một nhận xét khác:

• Bất kể là vị trí chia nào, luốn tôn tại một cách chọn lại các cặp ngoặc mở đóng ghép lại với nhau để đưa ra một kết quả tốt nhất.

• Hay nói cách khác là mọi vị trí chặt đều đưa ra cùng một kết quả.

Điều này đưa ta tới một thuật toán sử dụng Segment Tree.

• Xét tại nút thứ \([C]\) lưu trữ xâu \(s[l \dots r]\).

• Có nút con trái \([A]\) lưu trữ xâu \(s[l \dots m]\).

• Có nút con phải \([B]\) lưu trữ xâu \(s[m+1 \dots r]\).

• Với \(m\) là một vị trí ở giữa \([l, r]\)

Ta có \(F(C) = F(A) + F(B) + G(A, B)\), với:

• \(F(X)\) là độ dài dãy ngoặc đúng dài nhất của xâu \(X\)

• \(G(A, B)\) là độ dài số cặp ngoặc đúng được thêm vô khi ghép hai xâu \(A\) với \(B\)

Vậy lúc này, xét một nút con sẽ lưu 3 giá trị sau

• length là độ dài dãy ngoặc đúng dài nhất

• open là số ngoặc mở chưa được sử dụng

• close là số ngoặc đóng chưa được sử dụng

Lúc này ta sẽ có cách tính như sau:

• extra = G(A, B) = min(A.open, B.close) là số lượng cặp ngoặc đúng ghép được với nhau.

• C.length = A.length + B.length + 2 * extra là từ công thức \(F(C) = F(A) + F(B) + G(A, B)\).

• C.open = A.open + B.open - extra là vì mình có \(A.open + B.open\) ngoặc mở mà đã sử dụng \(extra\) cái.

• C.close = A.close + B.close - extra là vì mình có \(A.close + B.close\) ngoặc đóng mà đã sử dụng \(extra\) cái.

Vậy lúc này độ phức tạp chỉ còn \(O(n \log n)\) dựng cây, \(O(\log n)\) cho từng truy vấn và \(O(q \times \log n)\) tính các kết quả.

Code

• SPyofgame's solution

\(O((q + n) \log n)\) tổng cộng độ phức tạp cho bài này

\(O(n \log n)\) khởi tạo \(s[1..n]\)

\(O(\log n)\) sửa \(s[p]\) thành một dấu ngoặc khác

\(O(\log n)\) truy vấn trên \(s[l, r]\)

Bonus

• 1) Bạn có tìm ra được thuật toán trong \(O(n \log n)\) dựng cây mà không quá \(O(q \times log^* n)\) truy vấn không ?

• 2) Bạn có tìm ra được thuật toán tuyến tính \(O(n + q)\) cho bài này không ?

• 3) Nếu có truy vấn lật từng kí tự trong đoạn xâu \(s[l, r]\) thành dấu ngoặc còn lại thì bạn có giải được không ?

• 4) Nếu có truy vấn di chuyển xâu \(s[l, r]\) lên đầu thì bạn có giải được không ?

• 5) Nếu mỗi dấu ngoặc có một giá trị, và bạn yêu cầu tìm dãy ngoặc đúng có tổng lớn nhất thì bạn có làm được không ?