Hướng dẫn giải của [VTT Q4 Contest 01] Bài 3: Dãy ngoặc [CLUMSY]
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cần đổi chiều ít dấu ngoặc nhất để chuỗi trở thành cân bằng. Nhận xét chung: duyệt một lượt với biến đếm số dấu ( đang chờ là đủ, không cần thử mọi cách.
Sub 1: Vét cạn — ~O(2^n \cdot n)~, dùng khi ~n \le 20~
Thử mọi tập vị trí được đổi chiều (mặt nạ bit), kiểm tra chuỗi sau đổi có cân bằng không rồi lấy số vị trí đổi nhỏ nhất. Nếu chỉ nộp sub này: đúng 3/16 test (các test lớn bị quá thời gian hoặc sai).
Sub 2: Tham lam — ~O(n)~
Gọi ~bal~ là số ( chưa được đóng. Gặp ( thì tăng ~bal~. Gặp ): nếu ~bal > 0~ thì đóng một dấu; nếu ~bal = 0~ thì buộc phải đổi dấu này thành ( (tốn 1 lần), khi đó ~bal = 1~. Cuối chuỗi còn ~bal~ dấu ( chưa đóng (luôn chẵn nếu chuỗi dài chẵn); đổi một nửa số đó thành ) nên cộng thêm ~bal / 2~. Nếu chỉ nộp sub này: đúng 16/16 test.
Chương trình hoàn chỉnh
main đọc chuỗi; nếu độ dài không quá 20 và chẵn thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
// Sub 1: vét cạn tập vị trí đổi chiều — O(2^n * n), dùng khi n <= 20
void sub1() {
int best = INT_MAX;
for (int mask = 0; mask < (1 << n); mask++) {
int bal = 0; bool ok = true;
for (int i = 0; i < n && ok; i++) {
bool open = (s[i] == '(');
if (mask >> i & 1) open = !open;
bal += open ? 1 : -1;
if (bal < 0) ok = false;
}
if (ok && bal == 0) best = min(best, __builtin_popcount(mask));
}
cout << best << "\n";
}
// Sub 2: tham lam — gặp ')' khi chưa có '(' chờ thì đổi thành '(';
// cuối cùng còn bal dấu '(' thừa, đổi một nửa trong số đó — O(n)
void sub2() {
int bal = 0, ans = 0;
for (char c : s) {
if (c == '(') bal++;
else if (bal > 0) bal--;
else { ans++; bal = 1; }
}
cout << ans + bal / 2 << "\n";
}
int main() {
freopen("CLUMSY.INP", "r", stdin);
freopen("CLUMSY.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> s;
n = s.size();
if (n <= 20 && n % 2 == 0) sub1();
else sub2();
}
Bình luận