Merge Not Sort (Codeforces 1906E)
Tags: Others, dp

You are currently researching the Merge Sort algorithm. Merge Sort is a sorting algorithm that is based on the principle of Divide and Conquer. It works by dividing an array into two subarrays of equal length, sorting each subarrays, then merging the sorted subarrays back together to form the final sorted array.You are particularly interested in the merging routine. Common merge implementation will combine two subarrays by iteratively comparing their first elements, and move the smaller one to a new merged array. More precisely, the merge algorithm can be presented by the following pseudocode.    Merge(A[1..N], B[1..N]):        C = []        i = 1        j = 1        while i <= N AND j <= N:            if A[i] < B[j]:                append A[i] to C                i = i + 1            else:                append B[j] to C                j = j + 1         while i <= N:            append A[i] to C            i = i + 1         while j <= N:            append B[j] to C            j = j + 1         return CDuring your research, you are keen to understand the behaviour of the merge algorithm when arrays $$$A$$$ and $$$B$$$ are not necessarily sorted. For example, if $$$A = [3, 1, 6]$$$ and $$$B = [4, 5, 2]$$$, then $$$\text{Merge}(A, B) = [3, 1, 4, 5, 2, 6]$$$.To further increase the understanding of the merge algorithm, you decided to work on the following problem. You are given an array $$$C$$$ of length $$$2 \cdot N$$$ such that it is a permutation of $$$1$$$ to $$$2 \cdot N$$$. Construct any two arrays $$$A$$$ and $$$B$$$ of the same length $$$N$$$, such that $$$\text{Merge}(A, B) = C$$$, or determine if it is impossible to do so.

Input: The first line consists of an integer $$$N$$$ ($$$1 \leq N \leq 1000$$$).The following line consists of $$$2 \cdot N$$$ integers $$$C_i$$$. The array $$$C$$$ is a permutation of $$$1$$$ to $$$2 \cdot N$$$.

Output: If it is impossible to construct two arrays $$$A$$$ and $$$B$$$ of length $$$N$$$ such that $$$\text{Merge}(A, B) = C$$$, then output -1.Otherwise, output the arrays $$$A$$$ and $$$B$$$ in two lines. The first line consists of $$$N$$$ integers $$$A_i$$$. The second line consists of $$$N$$$ integers $$$B_i$$$. If there are several possible answers, output any of them.

Note: Explanation for the sample input/output #1The solution $$$A = [3, 1, 4]$$$ and $$$B = [5, 2, 6]$$$ is also correct. Explanation for the sample input/output #2The solution $$$A = [1, 2, 3, 4]$$$ and $$$B = [5, 6, 7, 8]$$$ is also correct. 

Sample Inputs:
3
3 1 4 5 2 6

4
1 2 3 4 5 6 7 8

2
4 3 2 1

Sample Outputs:
3 1 6
4 5 2

2 3 5 7
1 4 6 8

-1

Solution (Python):
n = int(input())
c = list(map(int, input().split()))
cur_max = c[0]
length = 1
lens = []
starts = [0]
for (i, x) in enumerate(c[1:]):
    if x <= cur_max:
        length += 1
    else:
        cur_max = x
        lens.append(length)
        starts.append(i + 1)
        length = 1
lens.append(length)
dp = dict()
dp[0] = True
for (i, l) in enumerate(lens):
    for s in range(n, l - 1, -1):
        if s - l in dp and s not in dp:
            dp[s] = i
if n in dp:
    s = n
    indices = []
    while s > 0:
        seg_idx = dp[s]
        indices.append(seg_idx)
        s -= lens[seg_idx]
    for i in reversed(indices):
        for j in range(starts[i], starts[i] + lens[i]):
            print(c[j], end=' ')
    print()
    indices = set(indices)
    for (i, l) in enumerate(lens):
        if i not in indices:
            for j in range(starts[i], starts[i] + l):
                print(c[j], end=' ')
    print()
else:
    print(-1)

Solution (Python):
def subset_sum(nums, target):
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if nums[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
    if dp[n][target]:
        subset = []
        (i, j) = (n, target)
        while i > 0 and j > 0:
            if dp[i][j] and (not dp[i - 1][j]):
                subset.append(nums[i - 1])
                j -= nums[i - 1]
            i -= 1
        return subset[::-1]
    else:
        return None
n = int(input())
main = list(map(int, input().split()))
all_lst = []
curr_lst = []
size_lst = []
i = 0
while i < 2 * n:
    if len(curr_lst) == 0 or curr_lst[0] > main[i]:
        curr_lst.append(main[i])
    else:
        all_lst.append(curr_lst)
        size_lst.append(len(curr_lst))
        curr_lst = [main[i]]
    i += 1
if curr_lst:
    all_lst.append(curr_lst)
    size_lst.append(len(curr_lst))
lst = subset_sum(size_lst, n)
if lst:
    a = []
    b = []
    i = 0
    for j in range(len(all_lst)):
        if i < len(lst) and len(all_lst[j]) == lst[i]:
            a.extend(all_lst[j])
            i += 1
        else:
            b.extend(all_lst[j])
    print(' '.join(map(str, a)))
    print(' '.join(map(str, b)))
else:
    print(-1)

Solution (Python):
n = int(input())
m = list(map(int, input().split()))
groups = []
t = 0
tmp = []
while t < 2 * n:
    tmp.append(m[t])
    if t + 1 == 2 * n or m[t + 1] > tmp[0]:
        groups.append(tmp)
        tmp = []
    t += 1
dp = [0] * (n + 1)
dp[0] = -1
for i in range(1, len(groups) + 1):
    group = groups[i - 1]
    for j in range(len(dp)):
        if dp[j] != 0 and dp[j] != i and (j + len(group) <= n) and (dp[j + len(group)] == 0):
            dp[j + len(group)] = i
if dp[n] == 0:
    print(-1)
else:
    ans1 = []
    ans2 = []
    p = n
    while p:
        q = groups[dp[p] - 1]
        ans1.append(dp[p] - 1)
        p -= len(q)
    ans1 = ans1[::-1]
    for i in range(len(groups)):
        if i not in ans1:
            ans2.append(i)
    for ans in ans1:
        for item in groups[ans]:
            print(item, end=' ')
    print()
    for ans in ans2:
        for item in groups[ans]:
            print(item, end=' ')