House Planning (Codeforces 1735E)
Tags: Greedy, graph matchings

There are $$$n$$$ houses in your city arranged on an axis at points $$$h_1, h_2, \ldots, h_n$$$. You want to build a new house for yourself and consider two options where to place it: points $$$p_1$$$ and $$$p_2$$$.As you like visiting friends, you have calculated in advance the distances from both options to all existing houses. More formally, you have calculated two arrays $$$d_1$$$, $$$d_2$$$: $$$d_{i, j} = \left|p_i - h_j\right|$$$, where $$$|x|$$$ defines the absolute value of $$$x$$$.After a long time of inactivity you have forgotten the locations of the houses $$$h$$$ and the options $$$p_1$$$, $$$p_2$$$. But your diary still keeps two arrays — $$$d_1$$$, $$$d_2$$$, whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of $$$d_1$$$ and $$$d_2$$$ may correspond to different houses. Pay attention, that values from one array could not get to another, in other words, all values in the array $$$d_1$$$ correspond the distances from $$$p_1$$$ to the houses, and in the array $$$d_2$$$  — from $$$p_2$$$ to the houses.Also pay attention, that the locations of the houses $$$h_i$$$ and the considered options $$$p_j$$$ could match. For example, the next locations are correct: $$$h = \{1, 0, 3, 3\}$$$, $$$p = \{1, 1\}$$$, that could correspond to already shuffled $$$d_1 = \{0, 2, 1, 2\}$$$, $$$d_2 = \{2, 2, 1, 0\}$$$.Check whether there are locations of houses $$$h$$$ and considered points $$$p_1$$$, $$$p_2$$$, for which the founded arrays of distances would be correct. If it is possible, find appropriate locations of houses and considered options. 

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the length of arrays $$$d_1$$$, $$$d_2$$$.The next two lines contain $$$n$$$ integers each: arrays $$$d_1$$$ and $$$d_2$$$ ($$$0 \le d_{i, j} \le 10^9$$$) respectively.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^3$$$.

Output: For each test case, output a single line "NO" if there is no answer.Otherwise output three lines. The first line must contain "YES". In the second line, print $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$. In the third line print two integers $$$p_1$$$, $$$p_2$$$.It must be satisfied that $$$0 \le h_i, p_1, p_2 \le 2 \cdot 10^9$$$. We can show that if there is an answer, then there is one satisfying these constraints.If there are several answers, output any of them.

Note: In the image below you can see the sample solutions. Planned houses are shown in bright colours: pink and purple. Existing houses are dim. In test case $$$1$$$, the first planned house is located at point $$$0$$$, the second at point $$$10$$$. The existing house is located at point $$$5$$$ and is at a distance of $$$5$$$ from both planned houses.   It can be shown that there is no answer for test case $$$2$$$.   In test case $$$3$$$, the planned houses are located at points $$$33$$$ and $$$69$$$.   Note that in test case $$$4$$$, both plans are located at point $$$1$$$, where one of the existing houses is located at the same time. It is a correct placement.   

Sample Inputs:
4
1
5
5
2
10 12
5 20
2
10 33
26 69
4
0 2 1 2
2 2 1 0

Sample Outputs:
YES
5 
0 10
NO
YES
0 43 
33 69
YES
1 0 3 3
1 1

Solution (Python):
import sys
input = sys.stdin.readline
MAX = 10 ** 9

def read_int():
    return int(input())

def read_ints():
    return map(int, input().split())

def read_int_list():
    return [int(i) for i in input().split()]

def read_string():
    return input().strip()

def print_answer(p1, p2, h):
    x = min(p1, p2, min(h))
    if x < 0:
        x = -x
    print('YES')
    print(' '.join([str(x + y) for y in h]))
    print(str(p1 + x) + ' ' + str(p2 + x))

def check(p, d, d2, n):
    h = []
    for i in range(n):
        x = d2[i]
        l1 = p + x
        l2 = p - x
        if l1 in d and d[l1] > 0:
            h.append(l1)
            d[l1] -= 1
        elif l2 >= 0 and l2 in d and (d[l2] > 0):
            h.append(l2)
            d[l2] -= 1
        elif l2 < 0 and -l2 in d and (d[-l2] > 0):
            h.append(l2)
            d[-l2] -= 1
        else:
            return (False, 0)
    return (True, h)

def solve(n, d1, d2):
    d = dict()
    for x in d1:
        if x not in d:
            d[x] = 0
        d[x] += 1
    e = min(d2)
    d2.sort()
    d2.reverse()
    for x in d:
        (valid, h) = check(x + e, d.copy(), d2, n)
        if valid:
            print_answer(0, x + e, h)
            return
        (valid, h) = check(abs(x - e), d.copy(), d2, n)
        if valid:
            print_answer(0, abs(x - e), h)
            return
    print('NO')
t = read_int()
for _ in range(t):
    n = read_int()
    d1 = read_int_list()
    d2 = read_int_list()
    solve(n, d1, d2)

Solution (Python):
def solve(d, n, d1, d2):
    jj = [-1] * n
    ii = [-1] * n
    xx = [-1] * n
    i1 = n - 1
    i2 = n - 1
    j1 = n - 1
    j2 = n - 1
    while 1:
        while i2 >= 0 and jj[i2] != -1:
            i2 -= 1
        while j2 >= 0 and ii[j2] != -1:
            j2 -= 1
        if j2 < 0 and j2 < 0:
            break
        if j2 < 0 or d1[i2] > d2[j2]:
            if d1[i2] <= d:
                break
            while j1 >= 0 and (ii[j1] != -1 or d1[i2] - d2[j1] < d):
                j1 -= 1
            if j1 < 0 or d1[i2] - d2[j1] != d:
                return 0
            jj[i2] = j1
            ii[j1] = i2
        else:
            if d2[j2] <= d:
                break
            while i1 >= 0 and (jj[i1] != -1 or d2[j2] - d1[i1] < d):
                i1 -= 1
            if i1 < 0 or d2[j2] - d1[i1] != d:
                return 0
            jj[i1] = j2
            ii[j2] = i1
    a = 0
    b = n - 1
    while 1:
        while a < n and jj[a] != -1:
            a += 1
        if a == n:
            break
        while b >= 0 and ii[b] != -1:
            b -= 1
        if d1[a] + d2[b] != d:
            return 0
        jj[a] = b
        ii[b] = a
    x = 0
    for a in range(n):
        xx[a] = -d1[a] if d2[jj[a]] - d1[a] == d else d1[a]
        x = min(x, xx[a])
    print('YES')
    for i in range(n):
        print(f'{xx[i] - x}', end=' ')
    print('')
    print(f'{0 - x} {d - x}')
    return 1
for _ in range(int(input())):
    n = int(input())
    d1 = sorted(list(map(int, input().split())))
    d2 = sorted(list(map(int, input().split())))
    yes = 0
    for i in range(n):
        if i == 0 or d2[i] != d2[i - 1]:
            if solve(abs(d1[0] - d2[i]), n, d1, d2) or solve(d1[0] + d2[i], n, d1, d2):
                yes = 1
                break
    if yes == 0:
        print('NO')

Solution (Python):
import random

class TreapMultiSet(object):
    root = 0
    size = 0

    def __init__(self, data=None):
        if data:
            data = sorted(data)
            self.root = treap_builder(data)
            self.size = len(data)

    def add(self, key):
        self.root = treap_insert(self.root, key)
        self.size += 1

    def remove(self, key):
        self.root = treap_erase(self.root, key)
        self.size -= 1

    def discard(self, key):
        try:
            self.remove(key)
        except KeyError:
            pass

    def ceiling(self, key):
        x = treap_ceiling(self.root, key)
        return treap_keys[x] if x else None

    def higher(self, key):
        x = treap_higher(self.root, key)
        return treap_keys[x] if x else None

    def floor(self, key):
        x = treap_floor(self.root, key)
        return treap_keys[x] if x else None

    def lower(self, key):
        x = treap_lower(self.root, key)
        return treap_keys[x] if x else None

    def max(self):
        return treap_keys[treap_max(self.root)]

    def min(self):
        return treap_keys[treap_min(self.root)]

    def __len__(self):
        return self.size

    def __nonzero__(self):
        return bool(self.root)
    __bool__ = __nonzero__

    def __contains__(self, key):
        return self.floor(key) == key

    def __repr__(self):
        return 'TreapMultiSet({})'.format(list(self))

    def __iter__(self):
        if not self.root:
            return iter([])
        out = []
        stack = [self.root]
        while stack:
            node = stack.pop()
            if node > 0:
                if right_child[node]:
                    stack.append(right_child[node])
                stack.append(~node)
                if left_child[node]:
                    stack.append(left_child[node])
            else:
                out.append(treap_keys[~node])
        return iter(out)

class TreapSet(TreapMultiSet):

    def add(self, key):
        (self.root, duplicate) = treap_insert_unique(self.root, key)
        if not duplicate:
            self.size += 1

    def __repr__(self):
        return 'TreapSet({})'.format(list(self))

class TreapHashSet(TreapMultiSet):

    def __init__(self, data=None):
        if data:
            self.keys = set(data)
            super(TreapHashSet, self).__init__(self.keys)
        else:
            self.keys = set()

    def add(self, key):
        if key not in self.keys:
            self.keys.add(key)
            super(TreapHashSet, self).add(key)

    def remove(self, key):
        self.keys.remove(key)
        super(TreapHashSet, self).remove(key)

    def discard(self, key):
        if key in self.keys:
            self.remove(key)

    def __contains__(self, key):
        return key in self.keys

    def __repr__(self):
        return 'TreapHashSet({})'.format(list(self))

class TreapHashMap(TreapMultiSet):

    def __init__(self, data=None):
        if data:
            self.map = dict(data)
            super(TreapHashMap, self).__init__(self.map.keys())
        else:
            self.map = {}

    def __setitem__(self, key, value):
        if key not in self.map:
            super(TreapHashMap, self).add(key)
        self.map[key] = value

    def __getitem__(self, key):
        return self.map[key]

    def add(self, key):
        raise TypeError('add on TreapHashMap')

    def get(self, key, default=None):
        return self.map.get(key, default=default)

    def remove(self, key):
        self.map.pop(key)
        super(TreapHashMap, self).remove(key)

    def discard(self, key):
        if key in self.map:
            self.remove(key)

    def __contains__(self, key):
        return key in self.map

    def __repr__(self):
        return 'TreapHashMap({})'.format(list(self))
left_child = [0]
right_child = [0]
treap_keys = [0]
treap_prior = [0.0]

def treap_builder(sorted_data):
    """"""

    def build(begin, end):
        if begin == end:
            return 0
        mid = (begin + end) // 2
        root = treap_create_node(sorted_data[mid])
        left_child[root] = build(begin, mid)
        right_child[root] = build(mid + 1, end)
        ind = root
        while True:
            lc = left_child[ind]
            rc = right_child[ind]
            if lc and treap_prior[lc] > treap_prior[ind]:
                if rc and treap_prior[rc] > treap_prior[lc]:
                    (treap_prior[ind], treap_prior[rc]) = (treap_prior[rc], treap_prior[ind])
                    ind = rc
                else:
                    (treap_prior[ind], treap_prior[lc]) = (treap_prior[lc], treap_prior[ind])
                    ind = lc
            elif rc and treap_prior[rc] > treap_prior[ind]:
                (treap_prior[ind], treap_prior[rc]) = (treap_prior[rc], treap_prior[ind])
                ind = rc
            else:
                break
        return root
    return build(0, len(sorted_data))

def treap_create_node(key):
    treap_keys.append(key)
    treap_prior.append(random.random())
    left_child.append(0)
    right_child.append(0)
    return len(treap_keys) - 1

def treap_split(root, key):
    left_pos = right_pos = 0
    while root:
        if key < treap_keys[root]:
            left_child[right_pos] = right_pos = root
            root = left_child[root]
        else:
            right_child[left_pos] = left_pos = root
            root = right_child[root]
    (left, right) = (right_child[0], left_child[0])
    right_child[left_pos] = left_child[right_pos] = right_child[0] = left_child[0] = 0
    return (left, right)

def treap_merge(left, right):
    (where, pos) = (left_child, 0)
    while left and right:
        if treap_prior[left] > treap_prior[right]:
            where[pos] = pos = left
            where = right_child
            left = right_child[left]
        else:
            where[pos] = pos = right
            where = left_child
            right = left_child[right]
    where[pos] = left or right
    node = left_child[0]
    left_child[0] = 0
    return node

def treap_insert(root, key):
    if not root:
        return treap_create_node(key)
    (left, right) = treap_split(root, key)
    return treap_merge(treap_merge(left, treap_create_node(key)), right)

def treap_insert_unique(root, key):
    if not root:
        return (treap_create_node(key), False)
    (left, right) = treap_split(root, key)
    if left and treap_keys[left] == key:
        return (treap_merge(left, right), True)
    return (treap_merge(treap_merge(left, treap_create_node(key)), right), False)

def treap_erase(root, key):
    if not root:
        raise KeyError(key)
    if treap_keys[root] == key:
        return treap_merge(left_child[root], right_child[root])
    node = root
    while root and treap_keys[root] != key:
        parent = root
        root = left_child[root] if key < treap_keys[root] else right_child[root]
    if not root:
        raise KeyError(key)
    if root == left_child[parent]:
        left_child[parent] = treap_merge(left_child[root], right_child[root])
    else:
        right_child[parent] = treap_merge(left_child[root], right_child[root])
    return node

def treap_ceiling(root, key):
    while root and treap_keys[root] < key:
        root = right_child[root]
    if not root:
        return 0
    min_node = root
    min_key = treap_keys[root]
    while root:
        if treap_keys[root] < key:
            root = right_child[root]
        else:
            if treap_keys[root] < min_key:
                min_key = treap_keys[root]
                min_node = root
            root = left_child[root]
    return min_node

def treap_higher(root, key):
    while root and treap_keys[root] <= key:
        root = right_child[root]
    if not root:
        return 0
    min_node = root
    min_key = treap_keys[root]
    while root:
        if treap_keys[root] <= key:
            root = right_child[root]
        else:
            if treap_keys[root] < min_key:
                min_key = treap_keys[root]
                min_node = root
            root = left_child[root]
    return min_node

def treap_floor(root, key):
    while root and treap_keys[root] > key:
        root = left_child[root]
    if not root:
        return 0
    max_node = root
    max_key = treap_keys[root]
    while root:
        if treap_keys[root] > key:
            root = left_child[root]
        else:
            if treap_keys[root] > max_key:
                max_key = treap_keys[root]
                max_node = root
            root = right_child[root]
    return max_node

def treap_lower(root, key):
    while root and treap_keys[root] >= key:
        root = left_child[root]
    if not root:
        return 0
    max_node = root
    max_key = treap_keys[root]
    while root:
        if treap_keys[root] >= key:
            root = left_child[root]
        else:
            if treap_keys[root] > max_key:
                max_key = treap_keys[root]
                max_node = root
            root = right_child[root]
    return max_node

def treap_min(root):
    if not root:
        raise ValueError('min on empty treap')
    while left_child[root]:
        root = left_child[root]
    return root

def treap_max(root):
    if not root:
        raise ValueError('max on empty treap')
    while right_child[root]:
        root = right_child[root]
    return root
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    d1 = list(map(int, input().split()))
    d2 = list(map(int, input().split()))
    d1.sort()
    d2.sort()
    poss = set()
    v0 = d1[0]
    for v in d2:
        poss.add(v + v0)
        poss.add(abs(v - v0))
    index = list(range(~(n - 1), n))
    assert len(index) == 2 * n

    def mag(i):
        if i >= 0:
            return d1[i]
        else:
            return d2[~i]
    index.sort(key=lambda x: -mag(x))
    pp = list(poss)
    random.shuffle(pp)
    for d in pp:
        good = True
        out = []
        a1 = TreapMultiSet()
        a2 = TreapMultiSet()
        for v in d1:
            a1.add(v)
        for v in d2:
            a2.add(v)
        for i in index:
            if i >= 0:
                j = i
                if d1[j] <= d:
                    break
                if d1[j] in a1:
                    if d1[j] - d in a2:
                        a1.remove(d1[j])
                        a2.remove(d1[j] - d)
                        out.append(d1[j])
                    else:
                        good = False
                        break
            else:
                j = ~i
                if d2[j] <= d:
                    break
                if d2[j] in a2:
                    if d2[j] - d in a1:
                        a2.remove(d2[j])
                        a1.remove(d2[j] - d)
                        out.append(d - d2[j])
                    else:
                        good = False
                        break
        for v in a1:
            if d - v in a2:
                a2.remove(d - v)
                out.append(v)
            else:
                good = False
        if good:
            diff = min(out + [0])
            print('YES')
            print(' '.join(map(lambda x: str(x - diff), out)))
            print(0 - diff, d - diff)
            break
    else:
        print('NO')