Array and Peaks (Codeforces 1513A)
Tags: Others, implementation

A sequence of $$$n$$$ integers is called a permutation if it contains all integers from $$$1$$$ to $$$n$$$ exactly once.Given two integers $$$n$$$ and $$$k$$$, construct a permutation $$$a$$$ of numbers from $$$1$$$ to $$$n$$$ which has exactly $$$k$$$ peaks. An index $$$i$$$ of an array $$$a$$$ of size $$$n$$$ is said to be a peak if $$$1 < i < n$$$ and $$$a_i \gt a_{i-1}$$$ and $$$a_i \gt a_{i+1}$$$. If such permutation is not possible, then print $$$-1$$$.

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.Then $$$t$$$ lines follow, each containing two space-separated integers $$$n$$$ ($$$1 \leq n \leq 100$$$) and $$$k$$$ ($$$0 \leq k \leq n$$$) — the length of an array and the required number of peaks.

Output: Output $$$t$$$ lines. For each test case, if there is no permutation with given length and number of peaks, then print $$$-1$$$. Otherwise print a line containing $$$n$$$ space-separated integers which forms a permutation of numbers from $$$1$$$ to $$$n$$$ and contains exactly $$$k$$$ peaks. If there are multiple answers, print any.

Note: In the second test case of the example, we have array $$$a = [2,4,1,5,3]$$$. Here, indices $$$i=2$$$ and $$$i=4$$$ are the peaks of the array. This is because $$$(a_{2} \gt a_{1} $$$, $$$a_{2} \gt a_{3})$$$ and $$$(a_{4} \gt a_{3}$$$, $$$a_{4} \gt a_{5})$$$. 

Sample Inputs:
5
1 0
5 2
6 6
2 1
6 1

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

Solution (Python):
t = int(input())
for i in range(t):
    (n, k) = map(int, input().split())
    r = []
    if k > (n - 1) // 2:
        r = ['-1']
    else:
        r = [str(j) for j in range(1, n - k + 1)]
        for j in range(n - k + 1, n + 1):
            r.insert(-k, str(j))
            k -= 1
    print(' '.join(r))

Solution (Python):
l = int(input())
for i in range(l):
    (n, k) = map(int, input().split())
    t = k
    a = []
    for j in range(n):
        a.append(j + 1)
    if n % 2 == 0:
        kmax = n / 2 - 1
    else:
        kmax = int(n / 2)
    if k == 0:
        print(*a)
    elif k > kmax or n == 1 or n == 2:
        print(-1)
    else:
        for i in range(1, n, 2):
            if t > 0:
                (a[i], a[i + 1]) = (a[i + 1], a[i])
                t -= 1
            else:
                pass
        print(*a)

Solution (Python):
t = int(input())
for i in range(t):
    (n, k) = map(int, input().split())
    if k > (n - 1) // 2:
        print(-1)
    else:
        a = []
        for i in range(n):
            a.append(i + 1)
        if k == 0:
            result = ' '.join(map(str, a))
            print(result)
        else:
            for i in range(k):
                a[2 * i + 1] += 1
                a[2 * i + 2] -= 1
            result = ' '.join(map(str, a))
            print(result)