You are not logged in. Please login at www.codechef.com to post your questions!

×

CLOST - Editorial

1
2

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 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 + ')' )
}

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

This question is marked "community wiki".

asked 25 Aug '15, 01:15

prateekg603's gravatar image

5★prateekg603
20421223
accept rate: 0%

edited 04 Sep '15, 23:04

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 30 Aug '15, 14:40

MASTER_KRISHNA%40123's gravatar image

4★MASTER_KRISHNA@123
212
accept rate: 0%

edited 30 Aug '15, 14:41

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

link

answered 30 Aug '15, 14:31

s1d_3's gravatar image

5★s1d_3
165413
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<k;i++) { cin>>x>>y; for(int j = x;j<=y;j+=2) { a[j] = '('; a[j+1] = ')'; } } cout<<a<<endl; }

(31 Aug '15, 22:52) muthukkaruppan2★

here is test case like 1 8 1 0 1

it contain only () and other character are only null character ...how the you can print n character string in output...I think that's It gave WA?..

(05 Sep '15, 01:13) rcsldav20175★

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.

link

answered 30 Aug '15, 14:33

sparkyyyy's gravatar image

4★sparkyyyy
111
accept rate: 0%

edited 30 Aug '15, 14:35

Your code outputs "(())" for that test case!

(31 Aug '15, 15:07) rushilpaul4★

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

link

answered 30 Aug '15, 14:42

saurabh_29's gravatar image

4★saurabh_29
714
accept rate: 0%

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

link

answered 30 Aug '15, 16:53

sameer_85's gravatar image

3★sameer_85
111
accept rate: 0%

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

link

answered 30 Aug '15, 14:40

anmol137dh08's gravatar image

6★anmol137dh08
32019
accept rate: 14%

edited 30 Aug '15, 14:43

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★

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

link

answered 30 Aug '15, 14:45

sunitswn91's gravatar image

2★sunitswn91
11
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★

@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

link

answered 30 Aug '15, 14:51

lakshaybansal's gravatar image

2★lakshaybansal
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

link

answered 30 Aug '15, 15:15

mjnsawan's gravatar image

3★mjnsawan
241
accept rate: 50%

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

link

answered 30 Aug '15, 15:15

dragonemperor's gravatar image

3★dragonemperor
89321135
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) dragonemperor3★

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

link

answered 30 Aug '15, 15:17

mail2mangu1993%40gmail.com's gravatar image

3★mail2mangu1993@gm...
1
accept rate: 0%

edited 30 Aug '15, 15:23

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.

link

answered 30 Aug '15, 15:32

sharad07's gravatar image

4★sharad07
20711
accept rate: 3%

Weak Test cases.. My wrong solution got passed.

link

answered 30 Aug '15, 15:48

ankurverma1994's gravatar image

4★ankurverma1994
415114
accept rate: 8%

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

link

answered 30 Aug '15, 16:52

moovon's gravatar image

4★moovon
1
accept rate: 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.

link

answered 30 Aug '15, 17:20

vinayawsm's gravatar image

4★vinayawsm
1.9k21430
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.

link

answered 30 Aug '15, 18:38

ryan_x's gravatar image

2★ryan_x
1
accept rate: 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?

link

answered 30 Aug '15, 19:57

mrityunjaypm's gravatar image

2★mrityunjaypm
1
accept rate: 0%

That is an O(klogk + n*k) solution.

(31 Aug '15, 14:45) rushilpaul4★

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

link

answered 30 Aug '15, 20:24

retrograd's gravatar image

6★retrograd
1503
accept rate: 12%

edited 30 Aug '15, 20:28

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.

link

answered 31 Aug '15, 11:22

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

while(t--) { char a[2001]; int n,k,x,y; cin>>n>>k; a[n] = '\0'; for(int i=0;i<k;i++) { cin>>x>>y; a[x] = '('; a[y] = ')'; bool isSet = 0; for(int j = x+1;j<y;j++,isSet = !isSet) { if(!isSet) a[j] = '('; else a[j] = ')'; } } cout<<a<<endl; }

Why my solution fails can anyone give testcase on where it fails ??

link

answered 31 Aug '15, 14:14

muthukkaruppan's gravatar image

2★muthukkaruppan
1
accept rate: 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

link

answered 31 Aug '15, 14:46

abhid95's gravatar image

2★abhid95
11
accept rate: 0%

edited 31 Aug '15, 14:48

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

include<iostream>

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;

}

Link https://www.codechef.com/viewsolution/7966515

link

answered 31 Aug '15, 18:47

shubham_30's gravatar image

2★shubham_30
1
accept rate: 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

link

answered 31 Aug '15, 20:05

sandeep9's gravatar image

3★sandeep9
4782827
accept rate: 4%

In the column "Breaking down the partially intersecting constraints into simpler form:" what if length of the segment [c,b] is odd?

link

answered 31 Aug '15, 20:58

prudvinit's gravatar image

3★prudvinit
10318
accept rate: 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...

link

answered 31 Aug '15, 22:57

jain_mj's gravatar image

3★jain_mj
372119
accept rate: 25%

edited 04 Sep '15, 23:05

admin's gravatar image

0★admin ♦♦
19.8k350498541

my solution: http://ideone.com/HfRB24 Time complexity:O(N*K)

link

answered 12 Dec '15, 05:11

code_vegeta123's gravatar image

3★code_vegeta123
11
accept rate: 0%

edited 12 Dec '15, 05:16

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]=')'

link

answered 08 Oct '16, 00:54

iro_code's gravatar image

5★iro_code
273
accept rate: 33%

can anyone tell me why am i getting sigsev error.. https://www.codechef.com/viewsolution/15954212

link

answered 25 Oct '17, 14:46

ankur2611's gravatar image

3★ankur2611
202
accept rate: 0%

leave it...i got it

(25 Oct '17, 15:08) ankur26113★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,875
×2,658
×2,220
×1,024
×801
×113

question asked: 25 Aug '15, 01:15

question was seen: 5,323 times

last updated: 25 Oct '17, 15:08