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.
A group is valid if there is one length- regular bracket sequence that avoids every string in that group. So first solve the easier question: can one regular bracket sequence avoid all given strings?
That one-group check is an automaton DP. Build an Aho-Corasick automaton over all forbidden strings, then generate a regular bracket sequence while tracking (position, balance, automaton state) and never entering a state where a forbidden string has appeared.
The only string that makes the whole task impossible is (). Every non-empty regular bracket sequence contains () — look at the first closing bracket. The character before it must be an opening bracket.
If the one-group DP fails and () is absent, the answer is exactly . Use the two special regular sequences ()()()... and ((...)).
Split strings by whether they contain equal adjacent characters. Strings containing (( or )) are avoided by ()()()...; the remaining alternating strings are avoided by ((...)), since () is excluded and the nested sequence has no )(.
We only need three possible answers: , , or . That sounds suspiciously too clean for a 2700, but here it is.
When Is It Impossible?
The string () is fatal.
Every regular bracket sequence of positive even length contains (). Proof: take the first ) in the sequence. Since the prefix balance cannot go negative, there is at least one ( before it. Since this is the first ), the character immediately before it must be (. So () appears.
Therefore, if some input string is exactly (), that string cannot belong to any group. No witness regular bracket sequence can avoid it. Answer: -1.
No other string causes total impossibility, as we will construct a solution with at most two groups.
Trying One Group
For answer , we need one regular bracket sequence of length that avoids every given string.
This is a standard Aho-Corasick + DP check.
Build an Aho-Corasick automaton over all . A state tells us the longest suffix of the currently built string that is also a prefix of some forbidden string. Mark a state as bad if reaching it means some forbidden string has appeared as a suffix. This includes suffix-link inherited matches.
Now run DP over:
where:
Start with .
From a reachable state, try appending ( or ):
( increases balance by ,) decreases balance by ,At the end, we need and .
If such a state exists, reconstruct the sequence using parent pointers and output all strings in one group. Done.
If One Group Fails
Now assume:
(),Then the answer is exactly .
Use these two fixed regular bracket sequences:
and
Now split every input string by whether it has two equal adjacent characters.
If a string contains (( or )), put it with witness . The sequence alternates forever, so it contains neither (( nor )). Therefore that string cannot be a substring of .
Otherwise, the string is alternating. Put it with witness .
Why does avoid it?
The nested sequence consists of some ( characters followed by some ) characters. So it has:
)(,( to ).An alternating string of length at least must contain either )( or multiple changes, so it cannot appear in . The only alternating string of length that could appear in is (), but we already handled that as impossible. The other one, )(, never appears in .
So both groups are valid.
Since the one-group DP failed, answer is impossible. Since the two fixed groups work, the minimum is .
Complexity
The automaton has at most
states.
The DP has states and two transitions per state, easily fine for .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Aho {
struct Node {
int nxt[2];
int link;
bool bad;
Node() : link(0), bad(false) {
nxt[0] = nxt[1] = -1;
}
};
vector<Node> t;
Aho() { t.emplace_back(); }
void add(const string& s) {
int v = 0;
for (char ch : s) {
int c = (ch == ')');
if (t[v].nxt[c] == -1) {
t[v].nxt[c] = (int)t.size();
t.emplace_back();
}
v = t[v].nxt[c];
}
t[v].bad = true;
}
void build() {
queue<int> q;
for (int c = 0; c < 2; c++) {
int u = t[0].nxt[c];
if (u == -1) t[0].nxt[c] = 0;
else q.push(u);
}
while (!q.empty()) {
int v = q.front();
q.pop();
t[v].bad = t[v].bad || t[t[v].link].bad;
for (int c = 0; c < 2; c++) {
int u = t[v].nxt[c];
if (u == -1) {
t[v].nxt[c] = t[t[v].link].nxt[c];
} else {
t[u].link = t[t[v].link].nxt[c];
q.push(u);
}
}
}
}
};
int main() {
setIO();
int n, k;
cin >> n >> k;
vector<string> s(n);
for (auto& x : s) cin >> x;
for (const string& x : s) {
if (x == "()") {
cout << -1 << '\n';
return 0;
}
}
Aho aho;
for (const string& x : s) aho.add(x);
aho.build();
int states = (int)aho.t.size();
vector dp(k + 1, vector(states, vector<char>(k + 1, 0)));
vector par(k + 1, vector(states, vector<pair<int, int>>(k + 1, {-1, -1})));
dp[0][0][0] = true;
for (int pos = 0; pos < k; pos++) {
for (int v = 0; v < states; v++) {
for (int bal = 0; bal <= k; bal++) {
if (!dp[pos][v][bal]) continue;
for (int c = 0; c < 2; c++) {
int nbal = bal + (c == 0 ? 1 : -1);
if (nbal < 0 || nbal > k) continue;
int u = aho.t[v].nxt[c];
if (aho.t[u].bad) continue;
if (!dp[pos + 1][u][nbal]) {
dp[pos + 1][u][nbal] = true;
par[pos + 1][u][nbal] = {v, c};
}
}
}
}
}
int endState = -1;
for (int v = 0; v < states; v++) {
if (dp[k][v][0]) {
endState = v;
break;
}
}
if (endState != -1) {
string ans;
int v = endState, bal = 0;
for (int pos = k; pos > 0; pos--) {
auto [pv, c] = par[pos][v][bal];
ans.push_back(c == 0 ? '(' : ')');
bal -= (c == 0 ? 1 : -1);
v = pv;
}
reverse(ans.begin(), ans.end());
cout << 1 << '\n';
cout << ans << '\n';
cout << n << '\n';
for (int i = 1; i <= n; i++) cout << i << " \n"[i == n];
return 0;
}
string repeated, nested;
for (int i = 0; i < k / 2; i++) repeated += "()";
nested = string(k / 2, '(') + string(k / 2, ')');
vector<int> groupRepeated, groupNested;
for (int i = 0; i < n; i++) {
bool hasEqualAdjacent = false;
for (int j = 0; j + 1 < (int)s[i].size(); j++) {
hasEqualAdjacent |= (s[i][j] == s[i][j + 1]);
}
if (hasEqualAdjacent) groupRepeated.push_back(i + 1);
else groupNested.push_back(i + 1);
}
auto printGroup = [](const string& w, const vector<int>& ids) {
cout << w << '\n';
cout << ids.size() << '\n';
for (int i = 0; i < (int)ids.size(); i++) {
if (i) cout << ' ';
cout << ids[i];
}
cout << '\n';
};
cout << 2 << '\n';
printGroup(repeated, groupRepeated);
printGroup(nested, groupNested);
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Aho {
struct Node {
int nxt[2];
int link;
bool bad;
Node() : link(0), bad(false) {
nxt[0] = nxt[1] = -1;
}
};
vector<Node> t;
Aho() { t.emplace_back(); }
void add(const string& s) {
int v = 0;
for (char ch : s) {
int c = (ch == ')');
if (t[v].nxt[c] == -1) {
t[v].nxt[c] = (int)t.size();
t.emplace_back();
}
v = t[v].nxt[c];
}
t[v].bad = true;
}
void build() {
queue<int> q;
for (int c = 0; c < 2; c++) {
int u = t[0].nxt[c];
if (u == -1) t[0].nxt[c] = 0;
else q.push(u);
}
while (!q.empty()) {
int v = q.front();
q.pop();
t[v].bad = t[v].bad || t[t[v].link].bad;
for (int c = 0; c < 2; c++) {
int u = t[v].nxt[c];
if (u == -1) {
t[v].nxt[c] = t[t[v].link].nxt[c];
} else {
t[u].link = t[t[v].link].nxt[c];
q.push(u);
}
}
}
}
};
int main() {
setIO();
int n, k;
cin >> n >> k;
vector<string> s(n);
for (auto& x : s) cin >> x;
for (const string& x : s) {
if (x == "()") {
cout << -1 << '\n';
return 0;
}
}
Aho aho;
for (const string& x : s) aho.add(x);
aho.build();
int states = (int)aho.t.size();
vector dp(k + 1, vector(states, vector<char>(k + 1, 0)));
vector par(k + 1, vector(states, vector<pair<int, int>>(k + 1, {-1, -1})));
dp[0][0][0] = true;
for (int pos = 0; pos < k; pos++) {
for (int v = 0; v < states; v++) {
for (int bal = 0; bal <= k; bal++) {
if (!dp[pos][v][bal]) continue;
for (int c = 0; c < 2; c++) {
int nbal = bal + (c == 0 ? 1 : -1);
if (nbal < 0 || nbal > k) continue;
int u = aho.t[v].nxt[c];
if (aho.t[u].bad) continue;
if (!dp[pos + 1][u][nbal]) {
dp[pos + 1][u][nbal] = true;
par[pos + 1][u][nbal] = {v, c};
}
}
}
}
}
int endState = -1;
for (int v = 0; v < states; v++) {
if (dp[k][v][0]) {
endState = v;
break;
}
}
if (endState != -1) {
string ans;
int v = endState, bal = 0;
for (int pos = k; pos > 0; pos--) {
auto [pv, c] = par[pos][v][bal];
ans.push_back(c == 0 ? '(' : ')');
bal -= (c == 0 ? 1 : -1);
v = pv;
}
reverse(ans.begin(), ans.end());
cout << 1 << '\n';
cout << ans << '\n';
cout << n << '\n';
for (int i = 1; i <= n; i++) cout << i << " \n"[i == n];
return 0;
}
string repeated, nested;
for (int i = 0; i < k / 2; i++) repeated += "()";
nested = string(k / 2, '(') + string(k / 2, ')');
vector<int> groupRepeated, groupNested;
for (int i = 0; i < n; i++) {
bool hasEqualAdjacent = false;
for (int j = 0; j + 1 < (int)s[i].size(); j++) {
hasEqualAdjacent |= (s[i][j] == s[i][j + 1]);
}
if (hasEqualAdjacent) groupRepeated.push_back(i + 1);
else groupNested.push_back(i + 1);
}
auto printGroup = [](const string& w, const vector<int>& ids) {
cout << w << '\n';
cout << ids.size() << '\n';
for (int i = 0; i < (int)ids.size(); i++) {
if (i) cout << ' ';
cout << ids[i];
}
cout << '\n';
};
cout << 2 << '\n';
printGroup(repeated, groupRepeated);
printGroup(nested, groupNested);
return 0;
}