PROBLEM LINK
Author: Amit Pandey
Tester: Pushkar Mishra
Editorialist: Prateek Gupta
Russian Translator: Vitalij Kozhukhivskij
Vietnamese Translator: Khanh Xuan Nguyen
Mandarian Translator: Gedi Zheng
Contest Admin: Praveen Dhinwa and Pushkar Mishra
DIFFICULTY:
Medium
PREREQUISITES:
Greedy, Dynamic Programming, Sorting
PROBLEM:
Given some constraints on the string which tell us, what all substrings should be balanced. A balanced expression is one in which for each opening bracket, there is a closing bracket which comes after it and for each closing bracket, there is an opening bracket which comes before it. Print the string of given length N which consists of characters ‘(’ and ‘)’ provided that all the constraints are satisfied. If there are multiple such strings, print any of them.
EXPLANATION
Solution for Subtask 1:
For a given length N, and character set consisting of ‘(’ and ‘)’, we can only form 2N distinct substrings. So, we can form all such strings and check whether any of these satisfy the given constraints. If it satisfies all the K constraints, it is one of the possible answers. However, there can be multiple such strings.
string ans;
bool flag = false
bool valid(string str)
{
int open = 0
for ( int i = 0; i < str.size(); i++ ) {
open += (str[i] == '(');
open -= (str[i] == ')');
if ( open < 0 ) return false
}
return (open == 0)
}
void f(int idx, string str) {
if ( flag ) return
if ( idx is N ) {
if ( valid(str) ) {
ans = str
flag = true
}
return
}
f(idx+1, str + '(' )
f(idx+1, str + ')' )
}
Solution for Subtask 2:
Small Observation
There is a nice observation you may make. All the constraints saying substring S[X..Y] is balanced would obviously want S[X] to be ‘(’ and S[Y] to be ‘)’. So, before forming the string, it’s necessary to place these characters which are dominated by given constraints. Finally, we place the characters at left over positions such that given constraints are satisfied.
Breaking down the partially intersecting constraints into simpler form:
In order to satisfy the constraints, we have to breakdown the strings such that none of the pair of strings are partially intersecting. Basically, we need to have a set of segments such that each pair of segment has either no intersection or is contained within the other. For eg: Let us say, we have pair of two balanced segments of the form [a,b] and [c,d] in the list of constraints such that a < c < b < d, then it is logical to say that segments [a,c-1], [c,b] and [b+1,d] should be balanced too. Lets look at the pseudo code to understand this.
while ( true ) {
pair <int,int> first, second, third;
for ( it1 = ss.begin(); it1 != ss.end(); it1++ ) {
it2 = ss.upper_bound(make_pair(it1->first+1,-1));
while ( it2 != ss.end() && it2->first < it1->second ) {
if ( it2->second > it1->second ) {
first = make_pair(it1->first,it2->first-1);
second = make_pair(it2->first, it1->second);
third = make_pair(it1->second+1, it2->second);
goto p1;
}
it2++;
}
}
break;
p1: { }
//removing two segments [a,b] and [c,d] which were partially overlapping
ss.erase(it1), ss.erase(it2);
//inserting three new segments [a,c-1], [c,b] and [b+1,d] into the set
ss.insert(first), ss.insert(second), ss.insert(third);
}
Hence, we have modelled the constraints suited to our requirements. So, segments which are inside another segments can be balanced first and then the outer segments. Same thing can be done for all kinds of independent segments having more segments within them.
Balancing the segments in order:
There should be some definite order to be followed while balancing each segment. Since, there is a possibility that we might end up balancing some segments which in turn does not balance the other segments. This can be avoided if we balance the segments sorted in ascending order of their size.
How to balance each segment:
Each segment may be empty or might have some inner segments balanced already. This can be called as another subproblem where you are given a string filled with some opening and closing brackets. You have to fill all the empty spaces such that given string can be called as balanced at the end. This can indeed be solved by Dynamic Programming. Lets maintain a state F(i, j) which denotes if there is a way to balance a given string such that you are at a position i and there are j open brackets left to be balanced. Looking at the pseudo code will give you more details about the implementation.
F(i,j) {
if ( j < 0 ) return false
if ( reached end of string ) return (j == 0)
bool ans = false
if ( s[i] is empty space ) {
ans = ans | f(i+1, j+1)
ans = ans | f(i+1, j-1)
}
else ans = ans | f(i+1, j + ((s[i] == '(') ? 1 : -1))
return ans
}
At each index i, you have two possibilities if you encounter an empty space, either you place an opening bracket or a closing one whereas if the bracket is already placed, you have no choice but to migrate to the next state. As the given constraints are valid, f(i,0) will return true for each segment. Printing the final string can be done recursively after implementing the above recurrence.
void go(int i, int j)
{
if ( reached end of string ) return;
if ( s[i] is empty space ) {
if ( f(i+1, j-1) ) go(i+1, j-1), s[i] = '('
else go(i+1, j+1), s[i] = ')'
}
else go(i+1, j + ((s[i] == '(') ? 1 : -1))
}
The above go(i,0) function checks if there is one possible answer while migration to the state, it ignores the other as we can print any possible string. Balancing each string in this way leads to a complexity of \mathcal{O}({N^2}) DP. For detailed implementation of the above approach, look at the editorialist’s solution.
COMPLEXITY
For subtask 1, a solution of complexity \mathcal{O}({2^N * N}{K}) per each test case shall pass.
For subtask 2, the solution described above suffices. Since K segments can be broken into a maximum of \mathcal{O}(K^2) segments while resolving partial overlaps, therefore, the net complexity is \mathcal{O}(NK^2).
