×

# CLOST - Editorial

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

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

For a given length $N$, and character set consisting of '(' and ')', we can only form 2$N$ 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 + ')' )
}


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)$.

# SOLUTIONS

Tester

This question is marked "community wiki".

20421223
accept rate: 0%

19.8k350498541

 2 For the input case: 1 8 4 0 7 2 3 4 5 1 6 output should be ((()())) but for some solutions even (()()()) output is taken as right....i guess that there is some problem with the test cases... answered 30 Aug '15, 14:40 21●2 accept rate: 0%
 1 Nice Solution. I tried a greedy approach. I place the brackets first when the input queries come in, and then place the other brackets by simply checking the bracket before. Can you tell me a test case where this code can fail? I tried a number of test cases over the last 2+ hours, and all seem to pass. I am getting a wrong answer on submission. Some help would be great. https://www.codechef.com/viewsolution/7958616 answered 30 Aug '15, 14:31 5★s1d_3 165●4●13 accept rate: 20% Why you are putting a ')' at the end and '(' at the beginning. It is given that only the queries are always balanced but no description about the string(original string) it can be balanced/unbalanced. (30 Aug '15, 17:26) flappy4★ That's true, but then it doesn't matter what I am giving at the end anyway. In case there was a query involving the ends, they would have been '(' for the start and ')' for the end anyway. And if there wasn't, then it doesn't matter what I am giving here. Can you/anybody help me with a test case for which this could fail? (30 Aug '15, 18:59) s1d_35★ @s1d_3: Your solution gives wrong answer for the following test case: 1 8 3 0 5 1 2 4 7 Your solution gives : (()(()() which is wrong. One correct answer could be : (())()() (31 Aug '15, 02:13) snk9674★ Y this code fails ?? while(t--) { char a[2001]; int n,k,x,y; cin>>n>>k; a[n] = '\0'; for(int i=0;i>x>>y; for(int j = x;j<=y;j+=2) { a[j] = '('; a[j+1] = ')'; } } cout<
 1 My code outputs "()()" for test case: 1 4 2 1 2 0 3 which, if I understood the problem, is incorrect. But it got accepted anyway, so I believe the test cases may have been weak. answered 30 Aug '15, 14:33 11●1 accept rate: 0% Your code outputs "(())" for that test case! (31 Aug '15, 15:07)
 1 The solution given here is quite complicated , my code complexity is O(n*k) , just sort the different segments in ascending order based on differnce (or their length) ,and balance them in the same order . Those who are left unalloted , allot them any value u want to bcoz that dosen't change ur answer . here is my solution https://www.codechef.com/viewsolution/7957011 answered 30 Aug '15, 14:42 71●4 accept rate: 0%
 1 I have solbed it using semaphore like logic in O(n) time Please Check here https://www.codechef.com/viewsolution/7963748 Please let me know whats wrong or can u please share test cases answered 30 Aug '15, 16:53 11●1 accept rate: 0%
 0 What's wrong with my solution? I am getting WA in subtask#1 test case#2 only :( https://www.codechef.com/viewsolution/7959488 answered 30 Aug '15, 14:40 320●1●9 accept rate: 14% Your solution gives wrong answer for the following test case: 1 8 2 3 4 0 7 Your solution gives : ()()()() which is wrong. One correct answer could be : ()(())() (31 Aug '15, 02:38) snk9674★
 0 I had the same issue as @s1d_3. Can somebody point some test cases which fail for that code? answered 30 Aug '15, 14:45 1●1 accept rate: 0% Your solution also gives wrong answer for the test case I mentioned above in reply to @s1d_3. (31 Aug '15, 02:23) snk9674★
 0 @s1d_3 Exactly a similar problem. Couldn't find a test case where greedy should fail. Alloted ( to the left place and ) to the right indices for all k. Then filled the remaining places wity alternate ( and). Just 1 test case passed though. :( https://www.codechef.com/viewsolution/7956764 answered 30 Aug '15, 14:51 1 accept rate: 0% Your solution also gives wrong answer for the test case I mentioned above in reply to @s1d_3. (31 Aug '15, 02:29) snk9674★

# include <bits stdc++.h="">

using namespace std; char a[2001]; void complete(long st,long end,long size) { long b[size],j=0;

 for(long i=st+1;i<end;i++)
{
if(a[i]!='(' && a[i]!=')')
{
b[j]=i;
j++;
}
}

for(long i=0,k=j-1;i<k;i++,k--)
{
a[b[i]]='(';
a[b[k]]=')';
}


}

void completefinish(long st,long end,long size) { long b[size],j=0;

 for(long i=st;i<end;i++)
{
if(a[i]!='(' && a[i]!=')')
{
b[j]=i;
j++;
}
}

for(long i=0,k=j-1;i<k;i++,k--)
{
a[b[i]]='(';
a[b[k]]=')';
}


}

int main() { int t; cin>>t; while(t--) { long long n,q,size,m=LLONG_MIN; cin>>n>>q; size=2q; long l[size]; for(long i=0;i<2q;i=i+2) { cin>>l[i]>>l[i+1]; a[l[i]]='('; a[l[i+1]]=')'; } long j=0,k; for(long i=0;i<q;i=i+2) {
complete(l[i],l[i+1],(l[i+1]-l[i])); }

    completefinish(0,n,n);

for(long i=0;i<n;i++)
cout<<a[i];

cout<<endl;

}
return 0;


}

not geting why getting wrong anstion can anyone tell

3★mjnsawan
241
accept rate: 50%

 0 The question asks to print any of the output. How does an online compiler checks every output? answered 30 Aug '15, 15:15 893●2●11●35 accept rate: 10% 1 They need not check every output. Compiler can run the input queries on this number, and check if they are all balanced. (30 Aug '15, 18:12) s1d_35★ thanks. I always used the method ./a.out < input > output and used diff command to check. I assumed online compilers also did that (30 Aug '15, 19:19)
 0 Please tell us what is First and fifth test case or what is wrong with my approach its basically O(N) solution i guesslink text answered 30 Aug '15, 15:17 1 accept rate: 0%
 0 Since there could be multiple possible answers for this problem...the tester's algorithm only checks if the segment between 'x' and 'y' (exclusive) is balanced or not.Hence lot of incorrect solutions got accepted. I don't claim this to be correct but I suppose this may be. answered 30 Aug '15, 15:32 4★sharad07 207●11 accept rate: 3%
 0 Weak Test cases.. My wrong solution got passed. answered 30 Aug '15, 15:48 415●1●14 accept rate: 8%
 0 SORT THE RANGES in terms of their of difference. and they apply the ranges on the decreasing order. For sorting the range with key "difference of the range", you may use a vector pair pair in c++. answered 30 Aug '15, 16:52 4★moovon 1 accept rate: 0%
 0 Can I know the solution of this test case, 8 3 1 6 0 3 4 7  I ran on few accepted solutions and found the solution is ()()()(). Now how can the sub-string with x = 1 and y = 6 is balanced for such a solution? Resulting sub-string is )()()( which is not balanced. answered 30 Aug '15, 17:20 1.9k●2●14●30 accept rate: 24% I think the test case is invalid. No correct arrangement can be made satisfying the test case. Would be surprised if you come up with a correct answer for the test case. :) (31 Aug '15, 02:44) snk9674★

# include<stdio.h>

int main() { int t; scanf("%d", &t); while(t--) { int n, k; scanf("%d %d", &n, &k); int i, x[k], y[k], j; char s[n]; for(i=0;i<k;i++) scanf("%d %d", &x[i], &y[i]); for(i=0;i<n;i++) s[i]=')'; int c1, c2; for(i=0;i<k;i++) { s[x[i]]='(' ; s[y[i]]=')' ; c1=1; for(j=x[i]+1; j<y[i]; j++ ) { if( s[j]=='(' ) c1++; else c1--; if(c1<0) { s[j]='('; c1+=2; } } } for(i=0;i<n;i++) printf("%c", s[i]); printf("\n"); } return 0; } The logic is very simple, solution in O(n*k) for the worst case.

2★ryan_x
1
accept rate: 0%

 0 someone has done it in o(k) complaxity by just sorting all given k values according to starting range value. https://www.codechef.com/viewsolution/7956165. can anyone explain that how this solution in correct mathematically? answered 30 Aug '15, 19:57 1 accept rate: 0% That is an O(klogk + n*k) solution. (31 Aug '15, 14:45)
 0 Interesting! I just sorted the queries by start index (breaking ties by end index) and for each constraint I just alternated "(" and ")" from segm.begin to segm.end, overwriting any previous changes. Complexity is O(N * K), although I'm sure it can become O(N + K*log(N)) with some sort of segment trees. Funny story. It got AC. Not sure why. Here is my solution: link answered 30 Aug '15, 20:24 150●3 accept rate: 12%
 0 Hi guys, I agree test cases for this problem were week. :( and I apologize for the same. I missed one case which lead to pass incorrect solutions, but it would not be fair to re-judge the problem. So, I will add that test case in the practice section, where you can check you solution. answered 31 Aug '15, 11:22 259●1●15●22 accept rate: 0%
 0 while(t--) { char a[2001]; int n,k,x,y; cin>>n>>k; a[n] = '\0'; for(int i=0;i>x>>y; a[x] = '('; a[y] = ')'; bool isSet = 0; for(int j = x+1;j
 0 Input 1 10 4 3 6 2 9 4 5 8 9 Output should be ((((()))() but those codes like https://www.codechef.com/viewsolution/7962854 and many others giving output as ((()()()() are also accepted, which is wrong. So please rejudge answered 31 Aug '15, 14:46 2★abhid95 1●1 accept rate: 0%

What is the problem with this code? Only the first substask is passing. Please can u provide the test cases.

# include<cstring>

using namespace std; int main() { long long int t,n,k,i,x,y; cin>>t; while(t--) { cin>>n>>k; char arr[n]; for(i=0;i<n-1;i+=2) {="" arr[i]="(" ;="" arr[i+1]=")" ;="" }="" cout<<endl;="" cin="">>x>>y; // arr[x]='('; // arr[y]=')'; // low=x; // high=y; //k=k-1; while(k--) { cin>>x>>y; for(i=x;i<y;i+=2) { //if(arr[i]=='(') // break; //else { arr[i]='('; arr[i+1]=')'; }

        }

//arr[x]='(';
//arr[y]=')';
//if(x<low)
// low=x;
// if(y>high)
//high=y;

}
/* c=0;
//cout<<high<<" "<<low<<endl;
mid=((high-low)+1)/2;
//cout<<mid<<endl;
for(i=0;i<low;i++)
arr[i]='(';
for(i=low;i<=high;i++)
{
if(arr[i]=='0' && c < mid)
{
arr[i]='(';
c++;
}
else if(arr[i]=='(')
c++;
else if(arr[i]==')')
c--;
else
{ arr[i]=')';
c--;
}

}
for(i=high+1;i<n;i++)
arr[i]=')';
//cout<<arr<<endl;*/
for(i=0;i<n;i++)
cout<<arr[i];
cout<<endl;
}
return 0;


}

1
accept rate: 0%

 0 I have never got so may wrong answers for a question as in this one.Still unable to find a test case where this fails.Please someone find a test case for me..I have matched with all the test cases of this page and all those cases works fine in my code..Link to my code: https://www.codechef.com/viewsolution/7951755 answered 31 Aug '15, 20:05 3★sandeep9 478●2●8●27 accept rate: 4%
 0 In the column "Breaking down the partially intersecting constraints into simpler form:" what if length of the segment [c,b] is odd? answered 31 Aug '15, 20:58 103●1●8 accept rate: 0%
 0 I have to re-post it, but still the question in practice is still accepting the incorrect solutions and it gave wrong answer to my correct solution, that's totally disappointing from the codechef.... Codechef should also not include this contest for calculating the rating coz it has an erroneous problem which gave many users including me WA during the contest and the actual in-correct solution were passed giving them AC.... one way for codechef to improve and make up for their error... answered 31 Aug '15, 22:57 3★jain_mj 372●1●1●9 accept rate: 25% 0★admin ♦♦ 19.8k●350●498●541
 0 my solution: http://ideone.com/HfRB24 Time complexity:O(N*K) answered 12 Dec '15, 05:11 1●1 accept rate: 0%
 0 give a test case where this logic fails- make a string of length n as ()()...() -total n chars then if query is x,y it assigns String[x]='(' String[y]=')' answered 08 Oct '16, 00:54 5★iro_code 27●3 accept rate: 33%
 0 can anyone tell me why am i getting sigsev error.. https://www.codechef.com/viewsolution/15954212 answered 25 Oct '17, 14:46 20●2 accept rate: 0% leave it...i got it (25 Oct '17, 15:08)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,655
×2,212
×1,024
×801
×113

question asked: 25 Aug '15, 01:15

question was seen: 5,308 times

last updated: 25 Oct '17, 15:08