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 of \{1, 2, \ldots, N\} such that there are exactly K distinct values of P_i + i across all i.
EXPLANATION:
If you play around with a few permutations, you might notice the following extremes:
- P = [1, 2, 3, \ldots, N] results in the P_i + i values being 2, 4, 6, \ldots, 2N, all of which are distinct.
This gets us N distinct values. - P = [N, N-1, N-2, \ldots, 2, 1] results in all the P_i+i values being N+1.
This gets us 1 distinct value.
Using these, we’re able to solve K = 1 and K = N.
Let’s try to combine them to solve for all K in the middle.
Suppose we choose an integer x, then use the second (descending) pattern till x and the first (ascending) pattern afterwards, i.e.
Then, it can be seen that:
- For 1 \leq i \leq x, the value of P_i + i is always x+1.
- For i \gt x, the value of P_i + i is 2i.
2i cannot equal x+1 for i \gt x, so the total number of distinct values is 1 + (N-x), because the first x positions give us a single distinct value, and then each index after that gives us a new one.
We want K distinct values overall, meaning we want 1 + (N-x) = K, which occurs with x = N+1-K.
So, using the above construction with this value of K gives us a valid solution, i.e. one possible answer is
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
x = n+1-k
ans = list(reversed(range(1, x+1))) + list(range(x+1, n+1))
print(*ans)
