Geek Answers Handbook

Dynamic programming: calculating the kth bracket

A sequence of n brackets consists of n "(" s and n ")" s.

A valid bracket sequence is defined as follows:

You can find a way to repeat erasing the adjacent pair of parentheses "()" until it becomes empty.

For example, "(())" is a valid parenthesis, you can erase a pair at the 2nd and 3rd position, and it will become "()", then you can make it empty. ") () (" is not valid brackets after deleting a pair at the 2nd and 3rd position, it becomes ") (" and you can no longer erase it.

Now we have all the valid parenthesized sequences. Find the kth smallest sequence in lexicographical order.

For example, here are all 3 valid brackets in lexicographical order:

((()))
(()())
(())()
()(())
()()()

Source: https://code.google.com/codejam/contest/4214486/dashboard#s=p3

Note. Competition is currently available and solutions are available for download.

I solved it for small input (k <10 6 ) using next_permutation (), which is available in C ++ STL. For this, I can not formulate a subparagraph. I tried to solve this using a Catalan number, but did not seem to achieve any success. I do not want to see solutions, because this does not help in training. Please help me in identifying problems with sub.

+4
source share
2 answers

N (.. 2 n).

N.

, countValid (N, depth), :

  • < 0 ( )

  • k < countValid (N-1, depth + 1) ( ( )

  • ) ( )

  • 1 N-1 + 1, ( -1, ) .

countValid (N, ) DP, M, :

  • , M [0,0] = 1, 0 ( )

  • M [0, 1... N] 0.

  • M [N, depth]

    • : M [N-1, -1]
    • : M [N-1, + 1]

    : M [N, ] = M [N-1, -1] + M [N-1, + 1]

+2

, , . aioobe, , :

3.1) ")", k = k - countValid (N-1, + 1)

. , , , , (N, ). , - , , . , .

java- k- , D, (N, ):

// get k-th element
int N = 2*n;
int d = 0;
String str = new String("");
while (N>0 && d >= 0) {
  // invalid elements (out of bounds or 0)
  if (d+1 > n || D[N-1][d+1] == 0) {
    str += ")"; d--;
  } else if (d-1 < 0 || D[N-1][d-1] == 0) {
    str += "("; d++;
  } else {
    if (k <= D[N-1][d+1]) {
      // first part of search-space
      str += "("; d++;
    } else {
      // second part of search-space
      str += ")";
      k -= D[N-1][d+1]; // substract number of excluded solutions
      d--;
    }
  }
  N--;
}

// For valid strings k should be 1
if (k != 1) str = "Doesn't Exist!";
0

More articles:


All Articles