Shocking Arrangement (Codeforces 1798D)
Tags: Greedy, constructive algorithms

You are given an array $$$a_1, a_2, \ldots, a_n$$$ consisting of integers such that $$$a_1 + a_2 + \ldots + a_n = 0$$$.You have to rearrange the elements of the array $$$a$$$ so that the following condition is satisfied:$$$$$$\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert < \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n),$$$$$$ where $$$|x|$$$ denotes the absolute value of $$$x$$$.More formally, determine if there exists a permutation $$$p_1, p_2, \ldots, p_n$$$ that for the array $$$a_{p_1}, a_{p_2}, \ldots, a_{p_n}$$$, the condition above is satisfied, and find the corresponding array.Recall that the array $$$p_1, p_2, \ldots, p_n$$$ is called a permutation if for each integer $$$x$$$ from $$$1$$$ to $$$n$$$ there is exactly one $$$i$$$ from $$$1$$$ to $$$n$$$ such that $$$p_i = x$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50\,000$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 300\,000$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — elements of the array $$$a$$$. It is guaranteed that the sum of the array $$$a$$$ is zero, in other words: $$$a_1 + a_2 + \ldots + a_n = 0$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.

Output: For each test case, if it is impossible to rearrange the elements of the array $$$a$$$ in the required way, print "No" in a single line.If possible, print "Yes" in the first line, and then in a separate line $$$n$$$ numbers — elements $$$a_1, a_2, \ldots, a_n$$$ rearranged in a valid order ($$$a_{p_1}, a_{p_2}, \ldots, a_{p_n}$$$).If there are several possible answers, you can output any of them.

Note: In the first test case $$$\max(a_1, \ldots, a_n) - \min(a_1, \ldots, a_n) = 9$$$. Therefore, the elements can be rearranged as $$$[-5, -2, 3, 4]$$$. It is easy to see that for such an arrangement $$$\lvert a_l + \ldots + a_r \rvert$$$ is always not greater than $$$7$$$, and therefore less than $$$9$$$.In the second test case you can rearrange the elements of the array as $$$[-3, 2, -3, 2, 2]$$$. Then the maximum modulus of the sum will be reached on the subarray $$$[-3, 2, -3]$$$, and will be equal to $$$\lvert -3 + 2 + -3 \rvert = \lvert -4 \rvert = 4$$$, which is less than $$$5$$$.In the fourth test example, any rearrangement of the array $$$a$$$ will be suitable as an answer, including $$$[-1, 0, 1]$$$.

Sample Inputs:
7
4
3 4 -2 -5
5
2 2 2 -3 -3
8
-3 -3 1 1 1 1 1 1
3
0 1 -1
7
-3 4 3 4 -4 -4 0
1
0
7
-18 13 -18 -17 12 15 13

Sample Outputs:
Yes
-5 -2 3 4
Yes
-3 2 -3 2 2
Yes
1 1 1 -3 1 1 1 -3
Yes
-1 0 1
Yes
4 -4 4 -4 0 3 -3
No
Yes
13 12 -18 15 -18 13 -17

Solution (Python):
import sys
Y = lambda : sys.stdin.readline()
for _ in range(int(Y())):
    n = int(Y())
    arr = list(map(int, Y().split()))
    zeros = [x for x in arr if x == 0]
    positives = [x for x in arr if x > 0]
    negatives = [x for x in arr if x < 0]
    if len(positives) == 0 or len(negatives) == 0:
        print('NO')
        continue
    result = zeros
    current_sum = 0
    while positives or negatives:
        if current_sum <= 0 and positives:
            next_num = positives.pop()
        elif current_sum > 0 and negatives:
            next_num = negatives.pop()
        else:
            break
        result.append(next_num)
        current_sum += next_num
    print('YES')
    print(*result)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
import heapq

def solve(n, a):
    b = []
    a.sort()
    if a[0] == a[-1] == 0:
        return []
    (i, j) = (0, n - 1)
    curr = 0
    while i <= j:
        if curr <= 0:
            curr += a[j]
            b.append(a[j])
            j -= 1
        else:
            curr += a[i]
            b.append(a[i])
            i += 1
    return b
q = int(input())
for _ in range(q):
    n = int(input())
    a = list(map(int, input().split()))
    res2 = solve(n, a)
    if len(res2) == 0:
        print('No')
    else:
        print('Yes')
        print(*res2)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if max(a) == 0:
        print('No')
    else:
        print('Yes')
        prefix_sum = 0
        pos = []
        neg = []
        for x in a:
            if x >= 0:
                pos.append(x)
            else:
                neg.append(x)
        ans = []
        for _ in range(n):
            if prefix_sum <= 0:
                ans.append(pos[-1])
                pos.pop()
            else:
                ans.append(neg[-1])
                neg.pop()
            prefix_sum += ans[-1]
        print(' '.join(list(map(str, ans))))