Google codejam APAC Practice: parentheses

Question

I spent one day solving this problem and could not find a solution to transfer a large data set.

Problem

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

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:

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

Given n and k, write an algorithm to give the kth smallest sequence in lexicographic order.

For a large dataset: 1 ≤ n ≤ 100 and 1 ≤ k ≤ 10^18

Answer 1

This problem can be solved with dynamic programming.

• Let dp[n][m] = the number of valid parentheses that can be created if we have n open brackets and m close the brackets.
• Base unit:
  dp[0][a] = 1 (a >=0)
• Fill in the matrix using the base register:
  dp[n][m] = dp[n - 1][m] + (n < m ? dp[n][m - 1]:0 );

Then we can slowly build the kth parentheses.

• Start with a = n open brackets and b = n close the brackets , and the current result is empty

   while(k is not 0): If number dp[a][b] >= k: If (dp[a - 1][b] >= k) is true: * Append an open bracket '(' to the current result * Decrease a Else: //k is the number of previous smaller lexicographical parentheses * Adjust value of k: `k -= dp[a -1][b]`, * Append a close bracket ')' * Decrease b Else k is invalid 

  Note that the open bracket is smaller than the closed bracket in lexicographical order, so we always try to add an open bracket first.

Answer 2

Let S= any valid sequence of parentheses from n( and n) . Now any real sequence S can be written as S=X+Y , where

• X=valid prefix i.e. if the intersection X is from left to right, at any given time, numberof'(' >= numberof')'
• Y=valid suffix i.e. if the intersection Y is from right to left, at any given time, numberof'(' <= numberof')'

For any S , many pairs of X and Y possible.

In our example: ()(())

 `()(())` =`empty_string + ()(())` = `( + )(())` = `() + (())` = `()( + ())` = `()(( + ))` = `()(() + )` = `()(()) + empty_string` 

Note that for X=empty_string number of valid S of n ( and n ) = the number of valid suffix Y of n ( and n )

Now the algorithm is as follows: We start with X= empty_string and grow X recursively to X=S At any given time, we have two options for growing X , either add '(' or append ')'

Let dp[a][b]= number of valid suffixes using a '(' and b ')' given X

nop=num_open_parenthesis_left ncp=num_closed_parenthesis_left

 `calculate(nop,ncp) { if dp[nop][ncp] is not known { i1=calculate(nop-1,ncp); // Case 1: X= X + "(" i2=((nop<ncp)?calculate(nop,ncp-1):0); /*Case 2: X=X+ ")" if nop>=ncp, then after exhausting 1 ')' nop>ncp, therefore there can be no valid suffix*/ dp[nop][ncp]=i1+i2; } return dp[nop][ncp]; }` 

Take an example, n = 3, i.e. 3 ( and 3 ) Now at the very beginning X=empty_string , therefore

dp[3][3] = number of valid sequence S using 3 ( and 3 ) = number of valid suffixes Y of 3 ( and 3 )