CLOST - Editorial

PROBLEM LINK

Practice

Contest

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

SOLUTIONS

Tester

1 Like

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

1 Like

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.

1 Like

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…

2 Likes

What’s wrong with my solution?
I am getting WA in subtask#1 test case#2 only :frowning:
https://www.codechef.com/viewsolution/7959488

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

1 Like

I had the same issue as @s1d_3. Can somebody point some test cases which fail for that code?

@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. :frowning:
https://www.codechef.com/viewsolution/7956764

#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<2
q;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

The question asks to print any of the output. How does an online compiler checks every output?

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

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.

Weak Test cases… My wrong solution got passed.

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++.

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

1 Like

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.

#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.

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?

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

Hi guys, I agree test cases for this problem were week. :frowning: 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.