PROBLEM LINKAuthor: Amit Pandey 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 2: Small Observation Breaking down the partially intersecting constraints into simpler form:
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: How to balance each segment:
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.
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. COMPLEXITYFor 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
This question is marked "community wiki".
asked 25 Aug '15, 01:15

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

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. answered 30 Aug '15, 14:31
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)
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_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)
Y this code fails ??
(31 Aug '15, 22:52)
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)

My code outputs "()()" for test case:
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

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

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

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

@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
Your solution also gives wrong answer for the test case I mentioned above in reply to @s1d_3.
(31 Aug '15, 02:29)

include <bits stdc++.h="">using namespace std; char a[2001]; void complete(long st,long end,long size) { long b[size],j=0;
} void completefinish(long st,long end,long size) { long b[size],j=0;
} 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)
{
} not geting why getting wrong anstion can anyone tell answered 30 Aug '15, 15:15

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

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

Weak Test cases.. My wrong solution got passed. answered 30 Aug '15, 15:48

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

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. answered 30 Aug '15, 18:38

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

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

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

Why my solution fails can anyone give testcase on where it fails ?? answered 31 Aug '15, 14:14

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

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<n1;i+=2) {="" arr[i]="(" ;="" arr[i+1]=")" ;="" }="" cout<<endl;="" cin="">>x>>y; // arr[x]='('; // arr[y]=')'; // low=x; // high=y; //k=k1; while(k) { cin>>x>>y; for(i=x;i<y;i+=2) { //if(arr[i]=='(') // break; //else { arr[i]='('; arr[i+1]=')'; }
} answered 31 Aug '15, 18:47

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

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

I have to repost 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 incorrect solution were passed giving them AC.... one way for codechef to improve and make up for their error... answered 31 Aug '15, 22:57

my solution: http://ideone.com/HfRB24 Time complexity:O(N*K) answered 12 Dec '15, 05:11

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

can anyone tell me why am i getting sigsev error.. https://www.codechef.com/viewsolution/15954212 answered 25 Oct '17, 14:46
