CF1381B Unmerge

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_1b_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) $ .

N/A

N/A

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.