PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given N and K, find any permutation P such that P_i\bmod K \neq i\bmod K for all i, or claim that no such permutations exist.
EXPLANATION:
There are likely several constructions, here’s one.
The main idea behind the following construction is that i and i+1 will always have different remainders modulo K (unless K = 1).
Why?
By the definition of the mod operator, x\bmod m = y\bmod m if and only if m divides (x - y).
So, if i\bmod K = (i+1)\bmod K, K must divide (i+1 - i) = 1, which is only possible if K = 1.
So, we can try to pair up i with i+1 and vice versa, and if we’re successful, we’ll obtain a solution that’s independent of K.
If N is even, it’s easy to see that this is always possible, and we’ll obtain
as our permutation, which is valid as long as K\neq 1.
However, if N is odd, pairing up elements will leave one element unpaired which isn’t ideal.
To fix this, let’s look at N = 3.
Consider the permutation [3, 1, 2].
For i = 2 and i = 3, the difference between the index and value is 1, so they’ll be fine.
For i = 1, the difference between the index and the value is 2.
So, if K \gt 2 this is a valid permutation.
Once these three elements are fixed, we have N-3 elements left - but that’s an even number, so we can just do what we did for the even case and pair them up into (4, 5), (6, 7), (8, 9), \ldots
So, when N is odd and K \gt 2, we obtain
as a valid permutation.
The only cases we haven’t taken care of with the above constructions are K = 1 for all N, and K = 2 when N is odd.
K = 1 can be trivially seen to have no solution, since all numbers modulo 1 are just 0 and hence equal.
As for odd N with K = 2, there’s no solution as well.
To see why, note that taking numbers modulo 2 is essentially reducing them to their parity.
Since we want P_i\bmod 2\neq i\bmod 2, we want to place even values at odd indices and vice versa.
But when N is odd, \frac{N+1}{2} of the elements are odd, while only \frac{N-1}{2} of the positions are even. So, we’ll always end up having to place an odd element at an odd index, which isn’t allowed - meaning no solution exists.
Putting everything together, the final solution is:
- If K = 1, or N is odd and K = 2, no solution exists.
- Otherwise,
- If N is even, print [2, 1, 4, 3, 6, 5, \ldots].
- If N is odd, print [3, 1, 2, 5, 4, 7, 6, \ldots].
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
def get(n):
a = [0]*n
a[::2] = list(range(2, n+1, 2))
a[1::2] = list(range(1, n+1, 2))
return a
for _ in range(int(input())):
n, k = map(int, input().split())
if k == 1: print(-1)
elif k == 2 and n%2 == 1: print(-1)
else:
if n%2 == 0: ans = get(n)
else:
ans = get(n-3) + [n-1, n, n-2]
print(*ans)