Google codejam APAC Thực hành thử nghiệm vòng: Dấu ngoặc đơn Đặt hàng

Question

Tôi đã dành một ngày để giải quyết this problem và không thể tìm thấy giải pháp để chuyển tập dữ liệu lớn.

Sự cố

Chuỗi dấu ngoặc đơn n bao gồm n "(" s và n ")" s.

Bây giờ, chúng tôi có tất cả các chuỗi ngoặc đơn n hợp lệ. Tìm chuỗi nhỏ nhất thứ k trong từ điển đơn đặt hàng.

Ví dụ, đây là tất cả các chuỗi giá trị 3 ngoặc trong thứ tự từ điển:

((())) 

(()()) 

(())() 

()(()) 

()()() 

Với n và k, hãy viết một thuật toán để cung cấp cho các chuỗi nhỏ nhất thứ k trong hoặc null trật tự.

Đối với tập hợp dữ liệu lớn: 1 ≤ n ≤ 100 và 1 ≤ k ≤ 10^18

Answer 1

Vấn đề này có thể được giải quyết bằng cách sử dụng lập trình năng động

• Hãy dp[n][m] = số dấu ngoặc đơn hợp lệ có thể được tạo ra nếu chúng ta có n dấu ngoặc mở và m dấu ngoặc đơn.
• trường hợp cơ sở:
  dp[0][a] = 1 (a >=0)
• Fill trong ma trận bằng cách sử dụng trường hợp cơ sở:
  dp[n][m] = dp[n - 1][m] + (n < m ? dp[n][m - 1]:0);

Sau đó, chúng ta có thể dần dần xây dựng thứ k ngoặc đơn.

• Bắt đầu với a = n mở ngoặc và ngoặc b = n gần và kết quả hiện thời trống rỗng

  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 
  

  ý rằng khung mở là ít hơn khung gần trong thứ tự từ điển, vì vậy chúng tôi luôn cố gắng thêm khung mở đầu tiên.

Answer 2

Hãy để S= any valid sequence of parentheses from n(and n). Bây giờ bất kỳ chuỗi S có giá trị có thể được viết như S=X+Y nơi

• X=valid prefix tức là nếu đi qua X từ trái sang phải, tại bất kỳ thời điểm, numberof'(' >= numberof')'
• Y=valid suffix tức là nếu đi qua Y từ phải sang trái, bất cứ lúc nào thời điểm, numberof'(' <= numberof')'

Đối với bất kỳ S nhiều cặp X và Y là có thể.

Ví dụ của chúng tôi: ()(())

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

Lưu ý rằng khi X=empty_string, sau đó số hợp lệ S từ n ( và n ) = số hậu tố hợp lệ Y từ n ( và n )

Bây giờ, Thuật toán giống như sau: Chúng tôi sẽ bắt đầu với X= empty_string và phát triển đệ quy X cho đến X=S. Tại bất kỳ thời điểm chúng tôi có hai lựa chọn để phát triển X, hoặc nối thêm '(' hoặc nối thêm ')'

Hãy 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]; 
}` 

Hãy lấy một ví dụ, n = 3 tức là 3 ( và 3 ) Ngay bây giờ ngay từ đầu X=empty_string, do đó

dp[3][3] = số thứ tự hợp lệ S sử dụng 3 ( và 3 ) = số hậu tố hợp lệ Y từ 3 ( và 3 )