PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: akshay_2512, divyesh_11
Tester & Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
You’re given a string S consisting of lowercase Latin characters.
Find a bracket sequence T of the same length as S such that:
- T is a regular bracket sequence
- If S_i = S_{i+1}, then T_i = T_{i+1}
EXPLANATION:
The condition S_i = S_{i+1} \implies T_i = T_{i+1} means that each contiguous block of equal characters in S must correspond to a contiguous block of either ( or ), of the same length, in T.
So, let’s find all the maximal contiguous blocks of equal characters in S.
Suppose there are k such blocks, and their lengths are L_1, L_2, \ldots, L_k in order.
For example, if S = \texttt{aabacccbbddd} then L = [2, 1, 1, 3, 2, 3].
Now, for each of these blocks, we need to decide whether it corresponds to ( or ).
There are 2^k possibilities, and since k can be as large as N, checking each one is out of the question.
Instead, note that T is a regular bracket sequence iff:
- Each prefix of T has a non-negative balance.
- T as a whole has balance 0.
Here, the balance of a bracket sequence equals the number of opening parentheses it contains, minus the number of its closing parentheses.
For example, the balance of \texttt{()} and \texttt{)(} are both 0, while \texttt{)(()(} has balance 3-2=1.
This allows us to only have to deal with prefixes; in particular, we only really care about the balance of each prefix.
This reduction lets us use dynamic programming.
Let \text{dp}[i][j] be a boolean value: True if there is a way to assign ( and ) to the first i blocks such that resulting balance is exactly j; and false otherwise.
Note that we only care about j \geq 0, since the balance cannot be allowed to go negative.
With this definition, transitions are in fact quite straightforward.
There are two choices for the i-th block: ( or ). Trying each one,
- If the i-th block is turned into
(, it will increase the balance by exactly A_i.
So, the part before it must have a balance of j - A_i, and we can check whether this is possible by looking at \text{dp}[i][j - A_i] - Similarly, if the i-th block is turned into
), we need to look at \text{dp}[i-1][j + A_i]. - So, we have \text{dp}[i][j] = \text{dp}[i-1][j - A_i] \mid \text{dp}[i-1][j + A_i], where \mid denotes the bitwise OR operator.
Of course, the final answer is Yes if \text{dp}[k][0] is True, and No otherwise; because the overall balance after all k blocks are assigned, should be 0.
If a solution exists, reconstructing it is not hard: move from the last block to the first, and each time the stored dp values will tell you which transition you took; and hence which type of bracket to assign to the current block.
There are upto \mathcal{O}(N^2) states and \mathcal{O}(1) transitions for each, for \mathcal{O}(N^2) time overall.
TIME COMPLEXITY
\mathcal{O}(N^2) per testcase.
CODE:
Author's code (C++)
// author : divyesh_11
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<int>> dp;
vector<ll> pre;
int helper(ll i, ll val, ll n, ll size, vector<ll> &a)
{
if (i >= n)
{
return val == 0;
}
if (dp[i][val] != -1)
{
return dp[i][val];
}
int ans1 = 0;
int ans2 = 0;
if (val >= a[i])
{
ans1 = helper(i + 1, val - a[i], n, size, a);
}
ll can = (size - pre[i] - val) / 2;
if (can >= a[i])
{
ans2 = helper(i + 1, val + a[i], n, size, a);
}
return dp[i][val] = (ans1 || ans2);
}
void solve()
{
ll n;
cin >> n;
string s;
cin >> s;
if (n & 1)
{
cout << "NO" << endl;
return;
}
vector<ll> a;
ll count = 1;
char c = s[0];
for (int i = 1; i < n; i++)
{
if (s[i] == c)
{
count++;
}
else
{
a.push_back(count);
count = 1;
c = s[i];
}
}
a.push_back(count);
ll size = a.size();
pre.clear();
pre.resize(size + 1, 0);
dp.clear();
dp.resize(size + 1, vector<int>(n + 1, -1));
pre[1] = a[0];
for (int i = 2; i <= size; i++)
{
pre[i] = pre[i - 1] + a[i - 1];
}
if (helper(0, 0, size, n, a))
{
cout << "yes" << endl;
ll curr = 0;
ll i = 0;
string ans;
while (i < size - 1)
{
if (dp[i + 1][curr + a[i]] == 1)
{
ll count = a[i];
while (count--)
{
ans.push_back('(');
}
curr += a[i];
}
else
{
ll count = a[i];
while (count--)
{
ans.push_back(')');
}
curr -= a[i];
}
i++;
}
while (a[i]--)
{
ans.push_back(')');
}
cout << ans << endl;
}
else
{
cout << "no" << endl;
}
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++)
{
solve();
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
lens = []
cur, L = 0, 0
for i in range(n):
if s[i] == s[L]: cur += 1
else:
lens.append(cur)
cur = 1
L = i
lens.append(cur)
dp = [ [False for _ in range(n+1)] for _ in lens ]
dp[0][lens[0]] = True
for i in range(1, len(lens)):
x = lens[i]
for j in range(n+1):
if j >= x: dp[i][j] |= dp[i-1][j-x]
if j+x <= n: dp[i][j] |= dp[i-1][j+x]
if dp[-1][0] == 0: print('No')
else:
print('Yes')
ans = ''
cur = 0
for i in reversed(range(len(lens))):
x = lens[i]
if cur >= x and dp[i-1][cur-x] == True:
cur -= x
ans += '('*x
else:
cur += x
ans += ')'*x
print(ans[::-1])