Circular Local MiniMax (Codeforces 1686C)
Tags: Greedy, sortings

You are given $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Is it possible to arrange them on a circle so that each number is strictly greater than both its neighbors or strictly smaller than both its neighbors?In other words, check if there exists a rearrangement $$$b_1, b_2, \ldots, b_n$$$ of the integers $$$a_1, a_2, \ldots, a_n$$$ such that for each $$$i$$$ from $$$1$$$ to $$$n$$$ at least one of the following conditions holds: $$$b_{i-1} < b_i > b_{i+1}$$$ $$$b_{i-1} > b_i < b_{i+1}$$$To make sense of the previous formulas for $$$i=1$$$ and $$$i=n$$$, one shall define $$$b_0=b_n$$$ and $$$b_{n+1}=b_1$$$.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 3\cdot 10^4$$$)  — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 10^5$$$)  — the number of integers.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).The sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.

Output: For each test case, if it is not possible to arrange the numbers on the circle satisfying the conditions from the statement, output $$$\texttt{NO}$$$. You can output each letter in any case.Otherwise, output $$$\texttt{YES}$$$. In the second line, output $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$, which are a rearrangement of $$$a_1, a_2, \ldots, a_n$$$ and satisfy the conditions from the statement. If there are multiple valid ways to arrange the numbers, you can output any of them.

Note: It can be shown that there are no valid arrangements for the first and the third test cases.In the second test case, the arrangement $$$[1, 8, 4, 9]$$$ works. In this arrangement, $$$1$$$ and $$$4$$$ are both smaller than their neighbors, and $$$8, 9$$$ are larger.In the fourth test case, the arrangement $$$[1, 11, 1, 111, 1, 1111]$$$ works. In this arrangement, the three elements equal to $$$1$$$ are smaller than their neighbors, while all other elements are larger than their neighbors.

Sample Inputs:
4
3
1 1 2
4
1 9 8 4
4
2 0 2 2
6
1 1 1 11 111 1111

Sample Outputs:
NO
YES
1 8 4 9 
NO
YES
1 11 1 111 1 1111

Solution (Python):
import sys

def rall():
    return sys.stdin.readlines()

def rl():
    return sys.stdin.readline().strip()

def rl_types(types):
    str_list = [x for x in sys.stdin.readline().strip().split(' ')]
    return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
    sys.stdout.write(str(something) + '\n')

def pra(array):
    sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
    return array
if __name__ == '__main__':
    NT = int(rl())
    for ti in range(NT):
        n = int(rl())
        array = list(map(int, rl().split(' ')))
        possible = True
        if n % 2 == 1:
            possible = False
        else:
            array.sort()
            if array[n // 2 - 1] == array[n // 2]:
                m = array[n // 2]
                mcount = sum([1 if i == m else 0 for i in array])
                possible = mcount < n // 2
                order = []
                for (a, b) in zip(array[:n // 2], array[n // 2:]):
                    order.extend([a, b])
            else:
                order = []
                for (a, b) in zip(array[:n // 2], array[n // 2:]):
                    order.extend([a, b])
                pass
        if possible:
            pr('YES')
            pra(order)
        else:
            pr('NO')

Solution (Python):
import sys
import collections
ifs = sys.stdin
ofs = sys.stdout

def numbers_from_line(d=' '):
    return [int(s) for s in ifs.readline().strip().split(d) if len(s.strip()) > 0]

def solve(A):
    n = len(A)
    if n % 2 != 0:
        return None
    A = sorted(A)
    S = A[:n // 2]
    B = A[n // 2:]
    R = collections.deque([B.pop()])
    take_small = True
    while S or B:
        if take_small:
            if len(S) >= 2:
                a = S.pop()
                b = S.pop()
                if a < R[0] and R[-1] > b:
                    R.appendleft(a)
                    R.append(b)
                else:
                    return None
            else:
                a = S.pop()
                if a < R[0] and R[-1] > a:
                    R.append(a)
                else:
                    return None
        elif len(B) >= 2:
            a = B.pop()
            b = B.pop()
            if a > R[0] and R[-1] < b:
                R.appendleft(a)
                R.append(b)
            else:
                return None
        else:
            a = B.pop()
            if a > R[0] and R[-1] < a:
                R.append(a)
            else:
                return None
        take_small = not take_small
    return R
T = int(ifs.readline())
for __ in range(T):
    n = int(ifs.readline())
    A = numbers_from_line()
    a = solve(A)
    if a is None:
        ofs.write('NO')
    else:
        ofs.write('YES\n')
        ofs.write(' '.join(map(str, a)))
    ofs.write('\n')

Solution (Python):
import sys
import os
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
    sys.stderr = open('error.txt', 'w')
input = lambda : sys.stdin.readline()
for _ in range(int(input())):
    n = int(input())
    lst = list(map(int, input().split()))
    lst.sort()
    if n % 2 == 1:
        print('NO')
        continue
    z = []
    l = 0
    r = n // 2
    while r < n:
        if l == r:
            z.append(lst[l])
        else:
            z.append(lst[l])
            z.append(lst[r])
        l += 1
        r += 1
    ok = True
    for i in range(n - 1):
        if z[i] == z[i + 1]:
            ok = False
            break
    if ok:
        print('YES')
        print(*z)
    else:
        print('NO')