Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Don’t overthink the bracket-prefix condition yet. First ask: what does the operation never change, no matter what substring you pick?
The operation only moves characters around, so the counts of '(' and ')' stay the same. Any regular bracket sequence must satisfy total balance , i.e.
So if , the answer is instantly NO. The only interesting part is: if the counts are equal, can one operation always fix the string?
You may choose any substring. Yes, including the whole string . If you remove all of , the remaining string is empty. That should smell suspiciously powerful.
If , remove the entire string, then reinsert the characters to obtain which is a regular bracket sequence. So the answer is simply YES iff the number of '(' equals the number of ')'.
The operation looks fancy, but it does not change how many '(' and ')' the string contains.
A regular bracket sequence must have total balance , meaning
So if the counts are different, we are dead immediately. No amount of shuffling is going to magically create or delete brackets. That’s a clean NO.
Here’s the real punchline: you are allowed to choose any substring, including the entire string .
If we remove the whole string, the remaining string becomes empty.
Now suppose
Since the removed characters can be reinserted one by one at arbitrary positions, we can arrange them to form
that is, all opening brackets first, then all closing brackets.
This string is obviously a regular bracket sequence:
So if the counts are equal, the answer is always YES.
Yeah, that’s the whole trick. The scary operation turns out to be absurdly powerful; picking the whole string basically lets you rebuild a valid sequence from scratch.
The answer is:
YES if ;NO otherwise.Since the string contains only '(' and ')', this is equivalent to checking whether the total balance is .
Let be the number of '(' minus the number of ')'.
Any sequence obtainable after the operation has the same counts of brackets as the original string. But every regular bracket sequence has equal numbers of opening and closing brackets, so obtaining one is impossible.
Choose the whole string as the removed substring. The remaining string is empty. Reinsert the removed brackets to form , which is a regular bracket sequence. Hence it is possible.
Therefore the criterion is both necessary and sufficient.
For each test case, we just count the balance of the string.
time and
extra space.
Over all test cases, that is
which easily fits the limits.
Short problem, brutal trick. Classic.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int bal = 0;
for (char c : s) {
bal += (c == '(' ? 1 : -1);
}
cout << (bal == 0 ? "YES\n" : "NO\n");
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int bal = 0;
for (char c : s) {
bal += (c == '(' ? 1 : -1);
}
cout << (bal == 0 ? "YES\n" : "NO\n");
}
return 0;
}