Editorial for Bedao Mini Contest 09 - BRACKET


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Xét dãy ngoặc ~T~ có độ dài ~m~, gọi ~f_i~ là số dấu ngoặc mở "dư" của dãy tạo bởi ~i~ phần tử đầu tiên của ~T~. Cụ thể:

  • ~f_0 = 0~.
  • Nếu ~T_i = '('~ thì ~f_i = f_{i-1} + 1~, ngược lại ~f_i = f_{i-1} - 1~ với mọi ~1 \leq i \leq m~.

~T~ là dãy ngoặc đúng khi thỏa mãn cả hai điều kiện:

  • ~min(f_0, f_1, f_2, ..., f_m) = 0~: số lượng dấu ngoặc mở "dư" không được âm tại bất kì tiền tố nào của ~T~.
  • ~f_m = 0~: cả dãy ngoặc không dư dấu ngoặc mở nào.

Nhận xét: nếu thêm một dấu ngoặc mở vào đầu dãy (giả sử dấu ngoặc này có chỉ số là ~-1~ và không ảnh hưởng gì đến các chỉ số của các dấu ngoặc khác) thì tất cả phần tử của mảng ~f~ sẽ tăng lên ~1~.

Một cách chèn các dấu ngoặc để ~T~ trở thành dãy ngoặc đúng như sau:

  • Đặt ~x = -min(f_0, f_1, f_2, ..., f_m)~ (~x \geq 0~).

  • Thêm ~x~ dấu ngoặc mở vào đầu dãy, lúc này ~f_m = f_m + x~.

  • Thêm ~f_m~ dấu ngoặc đóng


Comments

Please read the guidelines before commenting.


There are no comments at the moment.