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?

Illustration

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.

Task

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.

Input

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.

Output

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.

Example

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 

hide comments
angrajkarn: 2021-09-03 13:01:02

Just memoize man :)

karikaalan0207: 2020-10-02 17:52:30

recursion and mem ! kanni screams !!

Last edit: 2020-10-02 17:54:28
owaisrcoem: 2020-07-19 06:47:27

Recursive solution of java is giving TLE , try analysing dp table and build a bottom up solution , got Ac after 10 wrong attempts of recursive solution : (

kushagra_2: 2020-04-18 19:33:24

AC in one go ... recursion + Memo rocks !!

maskmanlucifer: 2020-04-05 07:44:44

nice problem AC in one go.

black_shroud: 2020-03-26 14:50:37

has a very beautiful solution with iterative dp

coolio_1: 2020-02-23 14:10:27

AC in 1 go! Rec + memoisation.

dkkv0000: 2020-01-14 14:55:14

beautiful problem

lonewolf098: 2019-09-19 06:54:42

recur with memo and take care of the corner cases!

sky_scraper: 2019-05-30 17:33:46

Really nice problem , dont forget the memoization part


Added by:adrian
Date:2004-06-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:III Polish Collegiate Team Programming Contest (AMPPZ), 1998