Farmer John's Challenge (Codeforces 1942A)
Tags: Math, constructive algorithms

Trade Winds - Patrick Deng⠀Let's call an array $$$a$$$ sorted if $$$a_1 \leq a_2 \leq \ldots \leq a_{n - 1} \leq a_{n}$$$.You are given two of Farmer John's favorite integers, $$$n$$$ and $$$k$$$. He challenges you to find any array $$$a_1, a_2, \ldots, a_{n}$$$ satisfying the following requirements:  $$$1 \leq a_i \leq 10^9$$$ for each $$$1 \leq i \leq n$$$;  Out of the $$$n$$$ total cyclic shifts of $$$a$$$, exactly $$$k$$$ of them are sorted.$$$^\dagger$$$ If there is no such array $$$a$$$, output $$$-1$$$.$$$^\dagger$$$The $$$x$$$-th ($$$1 \leq x \leq n$$$) cyclic shift of the array $$$a$$$ is $$$a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}$$$. If $$$c_{x, i}$$$ denotes the $$$i$$$'th element of the $$$x$$$'th cyclic shift of $$$a$$$, exactly $$$k$$$ such $$$x$$$ should satisfy $$$c_{x,1} \leq c_{x,2} \leq \ldots \leq c_{x, n - 1} \leq c_{x, n}$$$.For example, the cyclic shifts for $$$a = [1, 2, 3, 3]$$$ are the following:  $$$x = 1$$$: $$$[1, 2, 3, 3]$$$ (sorted);  $$$x = 2$$$: $$$[2, 3, 3, 1]$$$ (not sorted);  $$$x = 3$$$: $$$[3, 3, 1, 2]$$$ (not sorted);  $$$x = 4$$$: $$$[3, 1, 2, 3]$$$ (not sorted). 

Input: The first line contains $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.Each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^3$$$) — the length of $$$a$$$ and the number of sorted cyclic shifts $$$a$$$ must have.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Output: For each test case, print a single line:   if there is a valid array $$$a$$$, output $$$n$$$ integers, representing $$$a_1, a_2, \ldots, a_{n}$$$;  otherwise, output $$$-1$$$. If there are multiple solutions, print any of them.

Note: In the first testcase, $$$a = [1, 1]$$$ satisfies $$$n = 2, k = 2$$$:The two cyclic shifts of $$$a$$$ are $$$[a_1, a_2]$$$ and $$$[a_2, a_1]$$$, which are both $$$[1, 1]$$$ and are sorted.In the second testcase, $$$a = [69\,420, 69, 420]$$$ satisfies $$$n = 3, k = 1$$$:The three cyclic shifts of $$$a$$$ are $$$[a_1, a_2, a_3]$$$, $$$[a_2, a_3, a_1]$$$, $$$[a_3, a_1, a_2]$$$, which are $$$[69\,420, 69, 420]$$$, $$$[69, 420, 69\,420]$$$, and $$$[420, 69\,420, 69]$$$, respectively. Only $$$[69, 420, 69\,420]$$$ is sorted.

Sample Inputs:
3
2 2
3 1
3 2

Sample Outputs:
1 1
69420 69 420
-1

Solution (Python):
test_case = int(input())

def solve():
    for _ in range(test_case):
        (n, cy) = [int(x) for x in input().split()]
        if n == cy:
            print(*[1] * n)
        elif cy < n and cy > 1:
            print(-1)
        else:
            print(*[ans for ans in range(1, n + 1)])
solve()

Solution (Python):
import math

def solve():
    (n, m) = map(int, input().split())
    if n == m:
        lst = [1] * n
        return ' '.join(map(str, lst))
    if m == 1:
        lst = []
        for i in range(1, n + 1):
            lst.append(i)
        return ' '.join(map(str, lst))
    else:
        return -1
t = int(input())
for i in range(t):
    res = solve()
    print(res)

Solution (Python):
def farmer():
    (n, k) = map(int, input().split())
    if k != 1 and k != n:
        print(-1)
        return
    if k == 1:
        for i in range(1, n + 1):
            print(i, end=' ')
        return
    for i in range(1, n + 1):
        print(1, end=' ')
for _ in range(int(input())):
    farmer()