Unmerge
Contest: Codeforces Round 658 (Div. 1)
Difficulty rating: 1800
Tags: 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 format:
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 format:
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".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
YES
NO
YES
YES
NO
NO

Editorial:
Consider the maximum element $$$2n$$$ of $$$p$$$. Assume without loss of generality that it comes from array $$$a$$$. Then the merge algorithm will exhaust array $$$b$$$ before it takes the element $$$2n$$$. Therefore, if $$$2n$$$ appears at index $$$i$$$ in $$$p$$$, the entire suffix of $$$p$$$ beginning at index $$$i$$$ must be a contiguous block in one of the arrays $$$a$$$ or $$$b$$$.
Then if we ignore this suffix of $$$p$$$, we should determine if the prefix of $$$p$$$ can be the merge of two arrays of certain sizes. We can repeat the same argument, as the maximum remaining element also corresponds to a contiguous block.
Taking this argument all the way, consider all indices $$$i$$$ where $$$p_i$$$ is greater than all elements that come before. This gives us all the lengths of the contiguous blocks, and we should determine if a subset of them add up to $$$n$$$. We've shown this condition is necessary. It is also sufficient because if we assign the blocks to $$$a$$$ and $$$b$$$ accordingly, the merge algorithm works correctly.
Now, this is just a subset-sum problem. The standard subset-sum DP approach takes $$$O(n^2)$$$ time, which is good enough.
It's also possible to do $$$O(n\sqrt n)$$$ by using the fact that sum of values is $$$2n$$$ (as they are the lengths of disjoint blocks), meaning there are only $$$O(\sqrt n)$$$ distinct values.