Koxia and Permutation (Codeforces 1770B)
Tags: Others, constructive algorithms

Reve has two integers $$$n$$$ and $$$k$$$.Let $$$p$$$ be a permutation$$$^\dagger$$$ of length $$$n$$$. Let $$$c$$$ be an array of length $$$n - k + 1$$$ such that $$$$$$c_i = \max(p_i, \dots, p_{i+k-1}) + \min(p_i, \dots, p_{i+k-1}).$$$$$$ Let the cost of the permutation $$$p$$$ be the maximum element of $$$c$$$.Koxia wants you to construct a permutation with the minimum possible cost.$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2000$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output $$$n$$$ integers $$$p_1,p_2,\dots,p_n$$$, which is a permutation with minimal cost. If there is more than one permutation with minimal cost, you may output any of them.

Note: In the first test case,  $$$c_1 = \max(p_1,p_2,p_3) + \min(p_1,p_2,p_3) = 5 + 1 = 6$$$.  $$$c_2 = \max(p_2,p_3,p_4) + \min(p_2,p_3,p_4) = 3 + 1 = 4$$$.  $$$c_3 = \max(p_3,p_4,p_5) + \min(p_3,p_4,p_5) = 4 + 2 = 6$$$. Therefore, the cost is $$$\max(6,4,6)=6$$$. It can be proven that this is the minimal cost.

Sample Inputs:
3
5 3
5 1
6 6

Sample Outputs:
5 1 2 3 4
1 2 3 4 5
3 2 4 1 6 5

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, k) = readInts()
    ans = []
    (f, b) = (1, n)
    for i in range(1, n + 1):
        if i % k:
            ans.append(b)
            b -= 1
        else:
            ans.append(f)
            f += 1
    return ' '.join([str(v) for v in ans])
for _ in range(int(input())):
    print(solve())

Solution (Python):
t = int(input())
out = []
for i in range(t):
    (n, k) = [int(j) for j in input().split()]
    a = []
    for j in range(n // 2):
        a.append(f'{n - j}')
        a.append(f'{j + 1}')
    if n % 2 != 0:
        a.append(f'{n // 2 + 1}')
    out.append(' '.join(a))
for i in out:
    print(i)

Solution (Python):
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
    nums = inlt()
    (n, k) = (nums[0], nums[1])
    inp_arr.append((n, k))

def findResult(n, k):
    result = [str(0)] * n
    if n % 2 != 0:
        result[int(n / 2)] = str(int(n / 2))
    m = int(n / 2) - 1 if n % 2 == 0 else int(n / 2)
    s = n
    for i in range(0, int(n / 2) + 1, 2):
        result[i] = str(s)
        s -= 2
    s = 1
    for i in range(1, int(n / 2), 2):
        result[i] = str(s)
        s += 2
    s = n - 1
    for i in range(n - 1, m, -2):
        result[i] = str(s)
        s -= 2
    s = 2
    for i in range(n - 2, m, -2):
        result[i] = str(s)
        s += 2
    return ' '.join(result)
result = [findResult(n, k) for (n, k) in inp_arr]
for m in result:
    print(m)