Kevin and Permutation (Codeforces 1754B)
Tags: Greedy, constructive algorithms

For his birthday, Kevin received the set of pairwise distinct numbers $$$1, 2, 3, \ldots, n$$$ as a gift.He is going to arrange these numbers in a way such that the minimum absolute difference between two consecutive numbers be maximum possible. More formally, if he arranges numbers in order $$$p_1, p_2, \ldots, p_n$$$, he wants to maximize the value $$$$$$\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert,$$$$$$ where $$$|x|$$$ denotes the absolute value of $$$x$$$.Help Kevin to do that.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Description of the test cases follows.The only line of each test case contains an integer $$$n$$$ ($$$2 \le n \leq 1\,000$$$) — the size of the set.

Output: For each test case print a single line containing $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) describing the arrangement that maximizes the minimum absolute difference of consecutive elements. Formally, you have to print a permutation $$$p$$$ which maximizes the value $$$\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert$$$.If there are multiple optimal solutions, print any of them.

Note: In the first test case the minimum absolute difference of consecutive elements equals $$$\min \{\lvert 4 - 2 \rvert, \lvert 1 - 4 \rvert, \lvert 3 - 1 \rvert \} = \min \{2, 3, 2\} = 2$$$. It's easy to prove that this answer is optimal.In the second test case each permutation of numbers $$$1, 2, 3$$$ is an optimal answer. The minimum absolute difference of consecutive elements equals to $$$1$$$.

Sample Inputs:
2
4
3

Sample Outputs:
2 4 1 3
1 2 3

Solution (Python):
import math

def solve():
    n = int(input())
    a1 = [i for i in range(1, math.ceil(n / 2) + 1)]
    a2 = [i for i in range(math.ceil(n / 2) + 1, n + 1)]
    i = 0
    j = 0
    if len(a1) == len(a2):
        (a1, a2) = (a2, a1)
    arr = []
    for k in range(n):
        if k % 2 == 0:
            arr.append(a1[i])
            i += 1
        else:
            arr.append(a2[j])
            j += 1
    print(' '.join(map(str, arr)))
t = int(input())
while t:
    t -= 1
    solve()

Solution (Python):
n = int(input())
for j in range(n):
    a = int(input())
    ans = ''
    first = a // 2
    last = a
    if a <= 3:
        for i in range(a):
            ans += str(i + 1) + ' '
        print(ans[:-1])
    elif a % 2 == 0:
        for i in range(first, 0, -1):
            ans += str(i) + ' ' + str(last) + ' '
            last -= 1
        print(ans[:-1])
    elif a % 2 != 0:
        last = a - 1
        for i in range(first, 0, -1):
            ans += str(i) + ' ' + str(last) + ' '
            last -= 1
        print(f'{a} {ans}')

Solution (Python):
from math import floor, ceil
tc = int(input())
while tc > 0:
    setSize = int(input())
    halfSize = setSize / 2
    up = floor(halfSize)
    down = ceil(halfSize)
    a = [down]
    if setSize % 2 == 0:
        down += 1
    for i in range(1, setSize):
        if i % 2 == 0:
            a.append(a[-1] - down)
        else:
            a.append(a[-1] + up)
    print(' '.join(map(str, a)))
    tc -= 1