Google codejam APAC 테스트 실습 라운드 : 괄호 순서

Question

나는 하루를 this problem 해결하는 데 보냈으며 큰 데이터 집합을 전달하는 솔루션을 찾을 수 없습니다.

문제

의 n은 서열이 N 구성 "("S 및 N ")"괄호들.

이제 모든 유효한 n 개의 괄호 시퀀스가 ​​있습니다. 사전 식 순서에서 k 번째로 작은 시퀀스를 찾습니다.

((())) 

(()()) 

(())() 

()(()) 

()()() 

주어 N과 K, 사전 편찬 위해 k 번째 최소 서열을 제공하는 알고리즘을 해주기

예를 들어, 여기에서 사전 순 모든 유효한 3 개 괄호 서열이다. 큰 데이터 세트에 대한

: 1 ≤ n ≤ 100 및 1 ≤ k ≤ 10^18

Answer 1

이 문제

• 우리 n 열린 괄호있는 경우 생성 될 수있는 유효한 괄호 dp[n][m] = 참조하자 동적 프로그래밍을 이용하여 해결 될 수있다 m 닫기 괄호
• 자료의 경우 : 기본 케이스를 사용하여 매트릭스
  dp[0][a] = 1 (a >=0)
• 채우기 :
  dp[n][m] = dp[n - 1][m] + (n < m ? dp[n][m - 1]:0);

그런 다음, 우리는 천천히 k 번째 괄호 구축 할 수 있습니다.

• A = N 열린 괄호 및 B = N 닫기 괄호 시작하여 현재의 결과는 개방 브래킷 사전 순 닫기 괄호 미만이라고

  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 
  

  빈 공지이며 그래서 우리는 항상 열린 괄호를 먼저 추가하려고합니다.

Answer 2

S= any valid sequence of parentheses from n(and n). 는 이제 유효한 시퀀스 S는 S=X+Y로 기록 될 수있는

• X=valid prefix 즉
• Y=valid suffixnumberof'(' >= numberof')' 즉 오른쪽에서 Y를 통과하면 왼쪽 경우에 어떤 시간의 어느 시점에서, 왼쪽에서 오른쪽으로 X를 통과하는 경우 시간의 점, X 및 Y의 S 많은 쌍에 대한 numberof'(' <= numberof')'

이 가능합니다.이 예

: ()(())

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

참고 때 X=empty_string 다음 N ( 유효 S 수와 N ) = N ( 유효 접미사 Y 수와 N )

이제 알고리즘은 다음과 같이 진행됩니다. X= empty_string으로 시작하여 재귀 적으로 커집니다. X까지 X=S. 시간의 시점에서 우리는 dp[a][b]= number of valid suffixes using a '(' and b ')' given X

nop=num_open_parenthesis_leftncp=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]; 
}` 

예를 취할 수 있습니다 보자 X 성장, 하나 추가하는 두 가지 옵션 '('또는 추가 ')'

이, N = 3 즉, 그러므로 3 (과 매우 X=empty_string 시작에서 이제 3 ) ,

dp[3][3] = 3 ( 등을 사용하여 올바른 순서 S 수 3 ) = 3