algorithm - Google codejam APAC Test practice round: Parentheses Order -

i spent 1 day solving this problem , couldn't find solution pass large dataset.

problem

an n parentheses sequence consists of n "("s , n ")"s.

now, have valid n parentheses sequences. find k-th smallest sequence in lexicographical order.

for example, here valid 3 parentheses sequences in lexicographical order:

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

given n , k, write algorithm give k-th smallest sequence in lexicographical order.

for large data set: 1 ≤ n ≤ 100 , 1 ≤ k ≤ 10^18

this problem can solved using dynamic programming

• let dp[n][m] = number of valid parentheses can created if have n open brackets , m close brackets.
• base case:
  dp[0][a] = 1 (a >=0)
• fill in matrix using base case:
  dp[n][m] = dp[n - 1][m] + (n < m ? dp[n][m - 1]:0 );

then, can build kth parentheses.

• start a = n open brackets , b = n close brackets , current result empty

  while(k not 0):      if number dp[a][b] >= k:              if (dp[a - 1][b] >= k) true:                * append open bracket '(' current result                * decrease              else:                //k number of previous smaller lexicographical parentheses                * adjust value of k: `k -= dp[a -1][b]`,                * append close bracket ')'                 * decrease b      else k invalid 

  notice open bracket less close bracket in lexicographical order, try add open bracket first.