Can anyone help??
Also i didn’t quite understand the use of min_sum for every node here…can anyone explain??
IDK no IDK yes IDk no IDk
well, the logic zobayer is using is little confusing ( actually i am confused 
) but still you can use your own logic to solve this question.
just think what information you can store at a node ! …which can help in merging… well answer to this question can be…
there is a left child and right child
i keep no. of brackets open in left child which are not balanced … and i have no. of brackets closed in right child which are not opened and balanced
example
left child is… )(()()(
no. of opened brackets is 2 (traverse from right ) and closed unbalanced bracket is 1 (traverse from left)
and for right child string is ()())))(
no. of closed brackets which are not opened is 3 (traverse from left) and open brackets is 1 (traversed from right)
so if we merge these 2 child of a node…
resultant will have… one open bracket from right and closed bracket from left ( you can merge opened bracket of left child and closed bracket of right child … so after doing this… one closed bracket from right child will be spare and you can add this to parent node…)
)(()()(()())))(
so parent.leftclosed = leftchild.leftclosed + (rightchild.leftclosed - resultant)
parent.rightopen = rightchild.rightopen + (leftchild.rightopen - resultant)
resultant = min(leftchild.rightopen , rightchild.leftclosed)
so just implement segment tree to calculate all this… and you can easily figure out the case when it should be balanced 
1 Like
which runtime error?
This problem can be solved using stack too ,no?? Just the complexity for checking will be O(n) and updating also will be O(n),right??
but if you’ll use stack, you will get TLE , as n is around 30,000
and is this your code? i mean you are asking others to explain a function you wrote? 
and sorry i actually don’t code in java very much, so no idea about NZEC 
but can help with logic issue
No,i didn’t use stack, just wanted to know if its applicable.
No this isn’t my code. The ideone one I took is from some guy named zobayer.
this.
can you explain me the logic zobayer used here??
hey i didn’t understand your idea properly but nevertheless i got the gist of what you were saying…however i am still having problems with taking the input test cases… can you help me in that case??
as in? taking input testcases? talking about nzec ?
do one thing… i guess nzec is cause of input testcase… take t = 10, and run while loop 10 times , hopefully it might help
i tried that earlier, that too was giving NZEC
sorry, Java it is, not so good in debugging java code bugs but i can see that you got you code AC in c++
Do one thing, if possible loop till n and then read characters of bracket one by one… or use char array instead of string to read it in one go.
i read a comment on problem page for not using string in c++, maybe same is case with java
i can tell you the logic I used.
i am maintaining number of open and closed unbalanced brackets for each node.
So for ‘(’ open_unbalanced=1 and closed_unbalanced=0. And vice-versa for ‘)’
Now for the parent node
parent.number_of_closed_unbalanced=leftchild.number_of_closed_unbalanced;
parent.number_of_open_unbalanced=rightchild.number_of_open_unbalanced;
int unbala=rightchild.number_of_closed_unbalanced-leftchild.number_of_open_unbalanced;
if(unbala>0){
parent.number_of_closed_unbalanced+=unbala;
}
else parent.number_of_open_unbalanced+=Math.abs(unbala);
i got your logic… its correct … but you are getting NZEC right… not WA… then it is not related to logic or algorithm… right?
yes its not related to logic, its related to input taking . SPOJ is really bad for java coders, almost on all the segment tree problems i get TLE,whereas equivalent code in c++ will be AC.
btw can you look into this??
http://discuss.codechef.com/questions/59332/spoj-gss2-wa
btw GSS2 is a combination of DQUERY AND GSS1 on spoj
Hey i got this AC using BufferedReader… thanks btw 