The problem wrong brackets asks you to find k_th lexographically incorrect bracket sequence.
Editorial uses dynamic programming method dp[i][j] = the number of strings (of length 2N that contain N open brackets and N closed brackets) that are not correct, but their prefix of length i is correct and it contains j more open brackets than closed ones.
but how can bracket sequence be correct when i is of odd length. since i can be odd how to make dp transistions on them. The editorial did almost same for both even and odd length i prefix. i didn't understood it. can someone please explain the approach.
Thanks !
Correct prefix here means that when we are travelling from the beginning to the end of the prefix, and keeping track of the number of '(' and ')' we have encountered , there no point where number of ')' exceeds number of '(' . Eg: ((()) , (())(, ()()(, are correct prefixes of odd length.
ok! it should have been written as semi balanced in the editorial!
so, now if we calculate dp[][] array, how to generate the sequence? any idea!
This is the solution given with the editorial which I believe you must have gone through. We have to find the lexicographically K-ranked incorrect bracket sequence. Firstly , it is obvious that given a string prefix of length x, all the strings of length 2n that can be obtained by placing a '(' in x+1-th position after the prefix would come lexicographically before all the strings that are formed by placing a ')' at that position with same prefix.
So at every point, we check if there are at least K possible strings with the given criteria formable if we append a '(' to our existing prefix. If yes we do so. If K different strings cannot be formed, then obviously we cannot find the K ranked string. So then we must append a ')' to our existing prefix . Now when we append a ')' , all those strings which could have been formed if we had appended a '(' would come lexicographically before it. So the "relative rank" of our answer string among all the strings possible now would be-
K — the total number of strings that could have been formed if we appended ')'
We keep on doing this till we actually get a position where the number of ')' in our current prefix exceeds the number of '('. The author of the solution has checked that situation using the variable- "extra", which stores the difference between the number of '(' and the number of ')'.
Once we reach this state, we satisfied the incorretness criteria of our bracket sequence. Now all permutations of the number of '(' and ')' which we can still append , would lead to valid strings(incorrect bracket sequences) . So , we need to find the permutation with a relative rank K among them. That is what is done by the author at the last portion of the code after breaking from the loop.