Neutral Tonality (Codeforces 1894D)
Tags: Others, two pointers

You are given an array $$$a$$$ consisting of $$$n$$$ integers, as well as an array $$$b$$$ consisting of $$$m$$$ integers.Let $$$\text{LIS}(c)$$$ denote the length of the longest increasing subsequence of array $$$c$$$. For example, $$$\text{LIS}([2, \underline{1}, 1, \underline{3}])$$$ = $$$2$$$, $$$\text{LIS}([\underline{1}, \underline{7}, \underline{9}])$$$ = $$$3$$$, $$$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])$$$ = $$$3$$$.You need to insert the numbers $$$b_1, b_2, \ldots, b_m$$$ into the array $$$a$$$, at any positions, in any order. Let the resulting array be $$$c_1, c_2, \ldots, c_{n+m}$$$. You need to choose the positions for insertion in order to minimize $$$\text{LIS}(c)$$$.Formally, you need to find an array $$$c_1, c_2, \ldots, c_{n+m}$$$ that simultaneously satisfies the following conditions: The array $$$a_1, a_2, \ldots, a_n$$$ is a subsequence of the array $$$c_1, c_2, \ldots, c_{n+m}$$$. The array $$$c_1, c_2, \ldots, c_{n+m}$$$ consists of the numbers $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_m$$$, possibly rearranged. The value of $$$\text{LIS}(c)$$$ is the minimum possible among all suitable arrays $$$c$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n, m$$$ $$$(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$$$ — the length of array $$$a$$$ and the length of array $$$b$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — the elements of the array $$$a$$$.The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ $$$(1 \leq b_i \leq 10^9)$$$ — the elements of the array $$$b$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output $$$n + m$$$ numbers — the elements of the final array $$$c_1, c_2, \ldots, c_{n+m}$$$, obtained after the insertion, such that the value of $$$\text{LIS}(c)$$$ is minimized. If there are several answers, you can output any of them.

Note: In the first test case, $$$\text{LIS}(a) = \text{LIS}([6, 4]) = 1$$$. We can insert the number $$$5$$$ between $$$6$$$ and $$$4$$$, then $$$\text{LIS}(c) = \text{LIS}([6, 5, 4]) = 1$$$.In the second test case, $$$\text{LIS}([\underline{1}, 7, \underline{2}, \underline{4}, \underline{5}])$$$ = $$$4$$$. After the insertion, $$$c = [1, 1, 7, 7, 2, 2, 4, 4, 5, 5]$$$. It is easy to see that $$$\text{LIS}(c) = 4$$$. It can be shown that it is impossible to achieve $$$\text{LIS}(c)$$$ less than $$$4$$$.

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

Sample Outputs:
6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1

Solution (Python):
def insert_minimize_lis(a, b):
    b.sort(reverse=True)
    c = []
    (i, j) = (0, 0)
    while i < len(a) and j < len(b):
        if a[i] >= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    c.extend(a[i:])
    c.extend(b[j:])
    return ' '.join(map(str, c))
t = int(input())
while t:
    (n, m) = [int(x) for x in str(input()).split(' ')]
    a = [int(x) for x in str(input()).split(' ')]
    b = [int(x) for x in str(input()).split(' ')]
    print(insert_minimize_lis(a, b))
    t -= 1

Solution (Python):
def solve(arr_a, arr_b):
    sorted_b = sorted(arr_b, reverse=True)
    result = []
    (idx_a, idx_b) = (0, 0)
    while idx_a < len(arr_a) and idx_b < len(sorted_b):
        a = arr_a[idx_a]
        b = sorted_b[idx_b]
        if a >= b:
            result.append(a)
            idx_a += 1
        else:
            result.append(b)
            idx_b += 1
    while idx_a < len(arr_a):
        result.append(arr_a[idx_a])
        idx_a += 1
    while idx_b < len(sorted_b):
        result.append(sorted_b[idx_b])
        idx_b += 1
    return ' '.join([str(v) for v in result])
T = int(input())
for _ in range(T):
    (n, m) = [int(d) for d in str(input()).split()]
    arr_a = [int(d) for d in str(input()).split()]
    arr_b = [int(d) for d in str(input()).split()]
    print(solve(arr_a, arr_b))

Solution (Python):
def insert_minimize_lis(a, b):
    (max_a, min_a) = (max(a), min(a))
    b.sort(reverse=True)
    b_larger = [x for x in b if x > max_a]
    b_mid = [x for x in b if min_a <= x <= max_a]
    b_smaller = [x for x in b if x < min_a]
    c = b_larger
    (i, j) = (0, 0)
    while i < len(a) and j < len(b_mid):
        if a[i] > b_mid[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b_mid[j])
            j += 1
    c.extend(a[i:])
    c.extend(b_mid[j:])
    c.extend(b_smaller)
    return ' '.join(map(str, c))
t = int(input())
while t:
    (n, m) = [int(x) for x in str(input()).split(' ')]
    a = [int(x) for x in str(input()).split(' ')]
    b = [int(x) for x in str(input()).split(' ')]
    print(insert_minimize_lis(a, b))
    t -= 1