PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: moonlight_cl25
Tester and Editorialist: iceknight1093
DIFFICULTY:
1158
PREREQUISITES:
None
PROBLEM:
Given N, find the lexicographically maximum permutation P of \{1, 2, \ldots, N\} such that \gcd(P_1, P_3, \ldots) \gt \gcd(P_2, P_4, \ldots); or claim that none exist.
EXPLANATION:
If N is even, the answer is just [N, N-1, \ldots, 3, 2, 1]; i.e, the numbers from 1 to N in descending order.
It’s easy to see that this satisfies the condition:
- \gcd(P_1, P_3, P_5, \ldots, P_{N-1}) = \gcd(N, N-2, N-4, \ldots, 4, 2) = 2, since all these numbers are even.
- \gcd(P_2, P_4, \ldots, P_N) = 1 since P_1 = 1.
- This is the lexicographically maximum permutation.
If N is odd, the answer is -1: no valid permutation exists.
Proof
We want \gcd(P_1, P_3, \ldots) \gt \gcd(P_2, P_4, \ldots); in particular \gcd(P_1, P_3, \ldots) \gt 1 must be true.
So, there should be some integer k\gt 1 that divides all integers placed at odd positions.
There are \left \lceil \frac{N}{2} \right\rceil odd positions, and the numbers placed there need to be distinct.
So, at the very least we need integers k, 2k, 3k, 4k, \ldots, k\cdot \left \lceil \frac{N}{2} \right\rceil to be \leq N.
However, this is not possible for k \gt 1, and we reach a contradiction.
So, no valid permutation exists.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
if n%2 == 1: print(-1)
else: print(*list(reversed(range(1, n+1))))