Circular Local MiniMax (Codeforces 1685A)
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 os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
readint = lambda : int(sys.stdin.readline().rstrip('\r\n'))
readints = lambda : map(int, sys.stdin.readline().rstrip('\r\n').split())
readstr = lambda : sys.stdin.readline().rstrip('\r\n')
readstrs = lambda : map(str, sys.stdin.readline().rstrip('\r\n').split())
readarri = lambda : [int(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]
readarrs = lambda : [str(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]
mod = 998244353
MOD = int(1000000000.0) + 7

def solve():
    n = readint()
    a = sorted(readints())
    b = []
    if n & 1:
        print('NO')
    else:
        i = 0
        j = n // 2
        while j < n:
            b.append(a[i])
            b.append(a[j])
            i += 1
            j += 1
        flg = True
        for i in range(n - 1):
            if b[i - 1] < b[i] > b[i + 1] or b[i - 1] > b[i] < b[i + 1]:
                continue
            else:
                flg = False
                break
        if flg:
            if b[n - 2] < b[n - 1] > b[0] or b[n - 2] > b[n - 1] < b[0]:
                print('YES')
                print(' '.join(map(str, b)))
            else:
                print('NO')
        else:
            print('NO')

def main():
    t = 1
    t = readint()
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    a = list(map(int, inp().split()))
    if n % 2 == 1:
        print('NO')
        return
    a.sort()
    m = n // 2
    b = []
    for i in range(m):
        b.append(a[i])
        b.append(a[i + m])
    for i in range(1, n - 1):
        if not (b[i] < b[i + 1] and b[i] < b[i - 1] or (b[i] > b[i + 1] and b[i] > b[i - 1])):
            print('NO')
            return
    for i in (0, n - 1):
        if not (b[i] < b[(i + 1) % n] and b[i] < b[(i - 1) % n] or (b[i] > b[(i + 1) % n] and b[i] > b[(i - 1) % n])):
            print('NO')
            return
    print('YES')
    print(' '.join(map(str, b)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
import math
''
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    s = a[:math.ceil(n / 2)]
    b = a[math.ceil(n / 2):]
    ans = [0] * n
    ans[::2] = s
    ans[1::2] = b
    if n % 2 != 0:
        print('NO')
        continue
    for i in range(n - 1):
        if ans[i] == ans[i + 1]:
            print('NO')
            break
    else:
        print('YES')
        print(*ans)