PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: abhi_inav
Testers: tabr, iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given even N, print a permutation of length N such that all the values of P_i + P_{N+1-i} are distinct for 1 \leq i \leq \frac{N}{2}
EXPLANATION:
There are many different constructions that will work. For the most part, the simplest way to come up with a construction is to try to make the values of P_i + P_{N+1-i} sorted in some order.
For example, we can do the following:
- Set P_1 = 1 and P_N = 2
- Set P_2 = 3 and P_{N-1} = 4
- Set P_3 = 5 and P_{N-2} = 6
\vdots - Set P_i = 2i-1 and P_{N+1-i} = 2i
It’s easy to see that P_i + P_{N+1-i} = 4i-1, which is obviously distinct for each i.
The created permutation is [1, 3, 5, \ldots, N-1, N, N-2, N-4, \ldots, 6, 4, 2].
There are other constructions; for example, [1, 2, 3, \ldots, \frac{N}{2}, N, N-1, N-2, \ldots, \frac{N}{2}+2, \frac{N}{2}+1], which is what the code below implements.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print(*range(1, n//2+1), *reversed(range(n//2+1, n+1)))