Min Cost Permutation (Easy Version) (Codeforces 1844F1)
Tags: Math, brute force

The only difference between this problem and the hard version is the constraints on $$$t$$$ and $$$n$$$.You are given an array of $$$n$$$ positive integers $$$a_1,\dots,a_n$$$, and a (possibly negative) integer $$$c$$$.Across all permutations $$$b_1,\dots,b_n$$$ of the array $$$a_1,\dots,a_n$$$, consider the minimum possible value of $$$$$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|.$$$$$$ Find the lexicographically smallest permutation $$$b$$$ of the array $$$a$$$ that achieves this minimum.A sequence $$$x$$$ is lexicographically smaller than a sequence $$$y$$$ if and only if one of the following holds: $$$x$$$ is a prefix of $$$y$$$, but $$$x \ne y$$$; in the first position where $$$x$$$ and $$$y$$$ differ, the sequence $$$x$$$ has a smaller element than the corresponding element in $$$y$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n \le 5 \cdot 10^3$$$, $$$-10^9 \le c \le 10^9$$$).The second line of each test case contains $$$n$$$ integers $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.

Output: For each test case, output $$$n$$$ integers $$$b_1,\dots,b_n$$$, the lexicographically smallest permutation of $$$a$$$ that achieves the minimum $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$.

Note: In the first test case, it can be proven that the minimum possible value of $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ is $$$27$$$, and the permutation $$$b = [9,3,1,4,5,1]$$$ is the lexicographically smallest permutation of $$$a$$$ that achieves this minimum: $$$|3-9-(-7)|+|1-3-(-7)|+|4-1-(-7)|+|5-4-(-7)|+|1-5-(-7)| = 1+5+10+8+3 = 27$$$.In the second test case, the minimum possible value of $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ is $$$0$$$, and $$$b = [1,3,5]$$$ is the lexicographically smallest permutation of $$$a$$$ that achieves this.In the third test case, there is only one permutation $$$b$$$.

Sample Inputs:
3
6 -7
3 1 4 1 5 9
3 2
1 3 5
1 2718
2818

Sample Outputs:
9 3 1 4 5 1
1 3 5
2818

Solution (Python):
import sys
MOD = 998244353
a = [0] * 50001
ans = [0] * 50001

def S():
    (n, c) = map(int, input().split())
    a = list(map(int, input().split()))
    a.append(0)
    b = [0] * (n + 1)
    for i in range(n):
        b[i + 1] = a[i]
    for i in range(1, n + 1):
        a[i] = b[i]
    if c >= 0:
        a[1:n + 1] = sorted(a[1:n + 1])
        print(*a[1:n + 1])
        return
    if n == 1:
        print(a[1])
        return
    Q = sorted(a[1:n + 1])
    ans[1] = Q[-1]
    ans[n] = Q[0]
    Q.pop()
    Q.append(2147483647)
    for i in range(2, n):
        flag = True
        for j in range(1, len(Q) - 1):
            if Q[j] >= ans[i - 1] + c and Q[j + 1] - Q[j - 1] <= -c:
                ans[i] = Q[j]
                del Q[j]
                flag = False
                break
        if flag:
            ans[i] = Q[-2]
            Q.pop()
            Q.pop()
            Q.append(2147483647)
    print(*ans[1:n + 1])
T = int(sys.stdin.readline())
for _ in range(T):
    S()

Solution (Python):
import sys
MOD = 998244353
a = [0] * 50001
ans = [0] * 50001

def S():
    (n, c) = map(int, input().split())
    a = list(map(int, input().split()))
    a.append(0)
    b = [0] * (n + 1)
    for i in range(n):
        b[i + 1] = a[i]
    for i in range(1, n + 1):
        a[i] = b[i]
    if c >= 0:
        a[1:n + 1] = sorted(a[1:n + 1])
        print(*a[1:n + 1])
        return
    if n == 1:
        print(a[1])
        return
    Q = sorted(a[1:n + 1])
    ans[1] = Q[-1]
    ans[n] = Q[0]
    Q.pop()
    Q.append(2147483647)
    for i in range(2, n):
        flag = True
        for j in range(1, len(Q) - 1):
            if Q[j] >= ans[i - 1] + c and Q[j + 1] - Q[j - 1] <= -c:
                ans[i] = Q[j]
                del Q[j]
                flag = False
                break
        if flag:
            ans[i] = Q[-2]
            Q.pop()
            Q.pop()
            Q.append(2147483647)
    print(*ans[1:n + 1])
T = int(sys.stdin.readline())
for _ in range(T):
    S()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
I = lambda : int(input())
R = lambda : list(map(int, input().split()))
P = lambda x, y='\n': print(x, end=y)
for _ in range(I()):
    (n, c) = R()
    a = sorted(R())
    if c >= 0:
        print(*a)
        continue
    (a, b, c) = (a[::-1], [0], -c)
    (s, f) = ([a[0]], [0] * n)
    for i in range(n - 2):
        if a[i] - a[i + 2] > c:
            b.append(i + 1)
    b.append(n - 1)
    for i in range(len(b) - 1):
        (x, y) = (b[i], b[i + 1])
        if x == y:
            continue
        a1 = [a[x]]
        f[x] = f[y] = 1
        for j in range(x, y):
            if a[j] + c < a1[-1]:
                a1.append(a[j - 1])
                f[j - 1] = 1
        a2 = [a[y]]
        for j in range(y, x, -1):
            if a2[-1] + c < a[j] and j <= y - 2:
                if not f[j + 1]:
                    a2.append(a[j + 1])
                    f[j + 1] = 1
                elif not f[j + 2]:
                    a2.append(a[j + 2])
                    f[j + 2] = 1
        s.pop()
        s += a1
        for j in range(y, x, -1):
            if not f[j]:
                s.append(a[j])
        a2 = a2[::-1]
        s += a2
    print(*s)