No More Inversions (Codeforces 1473C)
Tags: Math, constructive algorithms

You have a sequence $$$a$$$ with $$$n$$$ elements $$$1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)$$$ ($$$k \le n < 2k$$$).Let's call as inversion in $$$a$$$ a pair of indices $$$i < j$$$ such that $$$a[i] > a[j]$$$.Suppose, you have some permutation $$$p$$$ of size $$$k$$$ and you build a sequence $$$b$$$ of size $$$n$$$ in the following manner: $$$b[i] = p[a[i]]$$$.Your goal is to find such permutation $$$p$$$ that the total number of inversions in $$$b$$$ doesn't exceed the total number of inversions in $$$a$$$, and $$$b$$$ is lexicographically maximum.Small reminder: the sequence of $$$k$$$ integers is called a permutation if it contains all integers from $$$1$$$ to $$$k$$$ exactly once.Another small reminder: a sequence $$$s$$$ is lexicographically smaller than another sequence $$$t$$$, if either $$$s$$$ is a prefix of $$$t$$$, or for the first $$$i$$$ such that $$$s_i \ne t_i$$$, $$$s_i < t_i$$$ holds (in the first position that these sequences are different, $$$s$$$ has smaller number than $$$t$$$).

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$k \le n < 2k$$$; $$$1 \le k \le 10^5$$$) — the length of the sequence $$$a$$$ and its maximum.It's guaranteed that the total sum of $$$k$$$ over test cases doesn't exceed $$$10^5$$$.

Output: For each test case, print $$$k$$$ integers — the permutation $$$p$$$ which maximizes $$$b$$$ lexicographically without increasing the total number of inversions.It can be proven that $$$p$$$ exists and is unique.

Note: In the first test case, the sequence $$$a = [1]$$$, there is only one permutation $$$p = [1]$$$.In the second test case, the sequence $$$a = [1, 2]$$$. There is no inversion in $$$a$$$, so there is only one permutation $$$p = [1, 2]$$$ which doesn't increase the number of inversions.In the third test case, $$$a = [1, 2, 1]$$$ and has $$$1$$$ inversion. If we use $$$p = [2, 1]$$$, then $$$b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2]$$$ and also has $$$1$$$ inversion.In the fourth test case, $$$a = [1, 2, 3, 2]$$$, and since $$$p = [1, 3, 2]$$$ then $$$b = [1, 3, 2, 3]$$$. Both $$$a$$$ and $$$b$$$ have $$$1$$$ inversion and $$$b$$$ is the lexicographically maximum.

Sample Inputs:
4
1 1
2 2
3 2
4 3

Sample Outputs:
1 
1 2 
2 1 
1 3 2

Solution (Python):
from collections import defaultdict
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def merge(a, b, l1, l2):
    ans = []
    i = j = 0
    while i < l1 and j < l2:
        if a[i] < b[j]:
            ans.append(a[i])
            i += 1
        else:
            ans.append(b[j])
            j += 1
    if i != l1:
        ans += a[i:]
    if j != l2:
        ans += b[j:]
    return ans

def msort(a, n):
    if n == 1:
        return a
    if n == 2:
        return [min(a), max(a)]
    return merge(msort(a[:n // 2], n // 2), msort(a[n // 2:n], n - n // 2), n // 2, n - n // 2)
import bisect

def solve():
    (n, k) = li()
    p = [i for i in range(1, k + 1)]
    inv = n - k + 1
    x = p[:k - inv]
    y = sorted(p[k - inv:], reverse=True)
    ans = x + y
    return ' '.join(map(str, ans))

def main():
    for _ in range(ii()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    p = list(range(1, k + 1))
    p[k - 1 - (n - k):] = p[k - 1 - (n - k):][::-1]
    print(' '.join((str(x) for x in p)))

Solution (Python):
t = int(input().strip())
for _ in range(t):
    (n, k) = map(int, input().strip().split())
    l = n - k
    T = list(range(1, k - l)) + list(range(k, k - l - 1, -1))
    print(' '.join(map(str, T)))