SQRBR - Square Brackets
You are given:
- a positive integer n,
- an integer k, 1<=k<=n,
- an increasing sequence of k integers 0 < s1 < s2 < ... < sk <= 2n.
What is the number of proper bracket expressions of length 2n with opening brackets appearing in positions s1, s2,...,sk?
Several proper bracket expressions:
An improper bracket expression:
There is exactly one proper expression of length 8 with opening brackets in positions 2, 5 and 7.
Write a program which for each data set from a sequence of several data sets:
- reads integers n, k and an increasing sequence of k integers from input,
- computes the number of proper bracket expressions of length 2n with opening brackets appearing at positions s1,s2,...,sk,
- writes the result to output.
The first line of the input file contains one integer d, 1 <= d <= 10, which is the number of data sets. The data sets follow. Each data set occupies two lines of the input file. The first line contains two integers n and k separated by single space, 1 <= n <= 19, 1 <= k <= n. The second line contains an increasing sequence of k integers from the interval [1;2n] separated by single spaces.
The i-th line of output should contain one integer - the number of proper bracket expressions of length 2n with opening brackets appearing at positions s1, s2,...,sk.
Sample input: 5 1 1 1 1 1 2 2 1 1 3 1 2 4 2 5 7 Sample output: 1 0 2 3 2
AC in 1 go! Rec + memoisation.
recur with memo and take care of the corner cases!
Really nice problem , dont forget the memoization part
If it is your first problem on bracket sequence topic you may want to read about standard problems on that topic. Otherwise, It would be hard for you to determine transition between states.
Solved without hint :) Motivated.Last edit: 2017-12-29 10:18:49
solved and Motivated :)
Try iterative DP, you will definitely enjoy.
easy recursion :)