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
A very nice question....!!
how come answer for last 2nd case is 3. I can only count 2 ways.
nice dp :) My 150th
Nice Problem !
not my first dp,but hard for me.because there is a assume...the input s1,s2,s3..sn is the pos of [.so sad,my 100th.it is not ac by myself.
Nice DP problem. The sub-problem is difficult to think of. Also a non-DP but recursive approach can pass too.
Deepak Singh Tomar:
in some way,.. quite similar to MPILOT :)
Why n so small? It can be increased to 500 or so and answer can be (ans mod p)
@ Aradhya Makkar , easy for Croatians also :P
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
Much easier than BRCKTS :p