Phân tích

Xem clip hướng dẫn giải

Tóm tắt đề bài, bài toán yêu cầu tìm số lượng dãy ngoặc con đúng lớn nhất có thể, tạo được từ số lượng ngoặc đóng, mở đã cho. Một chuỗi ~S~ chỉ chứa kí tự (, ) được gọi là dãy ngoặc đúng nếu:

• Chuỗi rỗng, hoặc:
• Có dạng ~(S)~, với ~S~ là một dãy ngoặc đúng, hoặc:
• Có dạng ~S_1S_2~, với ~S_1, S_2~ là dãy ngoặc đúng.

Subtask 1

Ta có thể sinh ra tất cả hoán vị của chuỗi có ~L~ ngoặc mở ( và ~R~ ngoặc đóng ). Độ phức tạp thời gian cho việc sinh hoán vị sẽ là ~O(\frac{(L+R)!}{L! \times R!})~.

Để đếm số lượng chuỗi con là dãy ngoặc đúng của một chuỗi, chúng ta có thể dùng một biến đếm cơ bản: cộng ~1~ khi gặp ngoặc mở ( và giảm ~1~ khi gặp ngoặc đóng ). Khi duyệt qua một chuỗi, nếu giá trị của biến đếm bị âm, thì chuỗi không thể là một dãy ngoặc đúng vì tồn tại các ngoặc đóng ( không được bắt cặp với ngoặc mở ). Nếu biến đếm là ~0~ khi kết thúc chuỗi, và không bị âm trong suốt quá trình duyệt, thì ta xác định đây là một dãy ngoặc đúng. Chúng ta có thể kiểm tra cho tất cả các chuỗi con một cách hiệu quả bằng vòng lặp trong ~O(N^2)~ với ~N~ là độ dài chuỗi:

int CountBalancedSubstrings(String S) {
  int N = S.length();
  int balanced_substrings = 0;
  for (int i = 0; i < N; i++) {
    int counter = 0;
    for (int j = i; j < N; j++) {
      if (S[j] == '(')
        counter++;
      else
        counter--;
      if (counter < 0) break;
      if (counter == 0) balanced_substrings++;
    }
  }
  return balanced_substrings;
}

Tóm lại, ta có thể sinh ra tất cả các hoán vị của dãy ngoặc, đếm số lượng chuỗi con là dãy ngoặc đúng, và trả về số lượng lớn nhất với độ phức tạp là ~O(\frac{(L+R)!}{L! \times R!} \times (L+R)^2)~.

Subtask 2

Ta không thể sinh tất cả hoán vị vì sẽ bị vượt quá thời gian. Ta cũng không thể đếm số chuỗi con là dãy ngoặc đúng bằng thuật toán ~O(N^2)~ như mô tả ở trên vì ~N~ có thể lên đến ~10^5~.

Ta phải tìm một hướng tiếp cận tối ưu hơn để tìm số lượng chuỗi con là dãy ngoặc đúng lớn nhất. Ta có thể quan sát một số tính chất từ hàm CountBalancedSubstrings ở trên:

• Biến đếm không được âm khi duyệt qua chuỗi.
• Số lượng chuỗi con đúng sẽ tương đương với số lần biến đếm trở thành 0.

Điều này dẫn ta đến với một cách tiếp cận tối ưu hơn, bằng cách sắp xếp các dấu ngoặc thành dạng như sau ()()()().... Khi đó mỗi dấu ngoặc mở sẽ có thể bắt cặp với bất kì dấu ngoặc đóng nào (hoặc ngược lại) để xác định một chuỗi con là dãy ngoặc đúng. Vì vậy ta có thể tạo ra một chuỗi theo pattern trên với độ dài ~2N~, với ~N = \min (L, R)~, các kí tự dư ra sẽ không nằm trong bất kì dãy ngoặc con đúng nào.

Trong pattern này, ta thấy mỗi dấu ngoặc mở ( đầu tiên sẽ bắt cặp được với ~N~ dấu ngoặc đóng ) để xác định được một chuỗi con đúng. Tương tự với các dấu ngoặc mở còn lại, chúng sẽ bắt cặp được với các dấu ngoặc đóng nằm bên phải chúng trong pattern để tạo một chuỗi con đúng. Vì vậy số lượng chuỗi con khác rỗng là dãy ngoặc đúng sẽ là ~1+2+3+4+⋯+N=\frac{N×(N+1)}{2}~.

Vì vậy với mỗi test case, chúng ta có thể tìm ~N~, sau đó tìm số lượng lớn nhất của chuỗi con đúng với độ phức tạp thời gian và không gian là ~O(1)~.

Tải bộ test

Bạn hãy cố gắng tập sửa lỗi mà không nhìn vào dữ liệu test! Link tải.