Unmerge (Codeforces 1382D)
Tags: DP, dp

Let $$$a$$$ and $$$b$$$ be two arrays of lengths $$$n$$$ and $$$m$$$, respectively, with no elements in common. We can define a new array $$$\mathrm{merge}(a,b)$$$ of length $$$n+m$$$ recursively as follows:  If one of the arrays is empty, the result is the other array. That is, $$$\mathrm{merge}(\emptyset,b)=b$$$ and $$$\mathrm{merge}(a,\emptyset)=a$$$. In particular, $$$\mathrm{merge}(\emptyset,\emptyset)=\emptyset$$$.  If both arrays are non-empty, and $$$a_1<b_1$$$, then $$$\mathrm{merge}(a,b)=[a_1]+\mathrm{merge}([a_2,\ldots,a_n],b)$$$. That is, we delete the first element $$$a_1$$$ of $$$a$$$, merge the remaining arrays, then add $$$a_1$$$ to the beginning of the result.  If both arrays are non-empty, and $$$a_1>b_1$$$, then $$$\mathrm{merge}(a,b)=[b_1]+\mathrm{merge}(a,[b_2,\ldots,b_m])$$$. That is, we delete the first element $$$b_1$$$ of $$$b$$$, merge the remaining arrays, then add $$$b_1$$$ to the beginning of the result. This algorithm has the nice property that if $$$a$$$ and $$$b$$$ are sorted, then $$$\mathrm{merge}(a,b)$$$ will also be sorted. For example, it is used as a subroutine in merge-sort. For this problem, however, we will consider the same procedure acting on non-sorted arrays as well. For example, if $$$a=[3,1]$$$ and $$$b=[2,4]$$$, then $$$\mathrm{merge}(a,b)=[2,3,1,4]$$$.A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).There is a permutation $$$p$$$ of length $$$2n$$$. Determine if there exist two arrays $$$a$$$ and $$$b$$$, each of length $$$n$$$ and with no elements in common, so that $$$p=\mathrm{merge}(a,b)$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$)  — the number of test cases. Next $$$2t$$$ lines contain descriptions of test cases. The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2000$$$).The second line of each test case contains $$$2n$$$ integers $$$p_1,\ldots,p_{2n}$$$ ($$$1\le p_i\le 2n$$$). It is guaranteed that $$$p$$$ is a permutation.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2000$$$.

Output: For each test case, output "YES" if there exist arrays $$$a$$$, $$$b$$$, each of length $$$n$$$ and with no common elements, so that $$$p=\mathrm{merge}(a,b)$$$. Otherwise, output "NO".

Note: In the first test case, $$$[2,3,1,4]=\mathrm{merge}([3,1],[2,4])$$$.In the second test case, we can show that $$$[3,1,2,4]$$$ is not the merge of two arrays of length $$$2$$$.In the third test case, $$$[3,2,6,1,5,7,8,4]=\mathrm{merge}([3,2,8,4],[6,1,5,7])$$$.In the fourth test case, $$$[1,2,3,4,5,6]=\mathrm{merge}([1,3,6],[2,4,5])$$$, for example.

Sample Inputs:
6
2
2 3 1 4
2
3 1 2 4
4
3 2 6 1 5 7 8 4
3
1 2 3 4 5 6
4
6 1 3 7 4 5 8 2
6
4 3 2 5 1 11 9 12 8 6 10 7

Sample Outputs:
YES
NO
YES
YES
NO
NO

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = list(map(int, input().split()))
    a = []
    index = 0
    c = 0
    for i in range(2 * n - 1):
        if s[index] < s[i + 1]:
            a.append(i + 1 - index)
            index = i + 1
    m = {0}
    for item in a:
        nm = [w + item for w in m if w + item <= n]
        m = m.union(nm)
        if n in m:
            c = 1
            print('YES')
            break
    if c == 0:
        print('NO')

Solution (Python):
def main():
    n = int(input())
    p = [int(e) for e in input().split()]
    prev = 0
    items = [0]
    for i in range(1, 2 * n):
        if p[i] > p[prev]:
            items.append(i - prev)
            prev = i
    weights = {0}
    for item in items:
        new_weights = [weight + item for weight in weights if weight + item <= n]
        weights = weights.union(new_weights)
        if n in weights:
            print('YES')
            return
    print('NO')
for _ in range(int(input())):
    main()

Solution (Python):
def main():
    n = int(input())
    p = [int(e) for e in input().split()]
    prev = 0
    items = []
    for i in range(1, 2 * n):
        if p[i] > p[prev]:
            items.append(i - prev)
            prev = i
    weights = {0}
    for item in items:
        new_weights = [weight + item for weight in weights if weight + item <= n]
        weights = weights.union(new_weights)
        if n in weights:
            print('YES')
            return
    print('NO')
for _ in range(int(input())):
    main()