PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Testers: wuhudsm, satyam_343
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, find a permutation of \{1, 2, 3, \ldots, N\} such that P_1 + P_2 + \ldots + P_i is not divisible of i for every 1 \lt i \leq N.
EXPLANATION:
First, note that when N is odd, no valid permutation exists.
Why?
Let N = 2k+1.
No matter what permutation is, the prefix of length N will have the same sum; since it’s the sum of the first N natural numbers.
This sum is 1 + 2 + \ldots + N = \frac{N(N+1)}{2} = \frac{N\cdot (2k+2)}{2} = N\cdot (k+1), which is a multiple of N.
When N is even, there is in fact a rather simple construction, which you might notice by solving for small even values of N:
[2, 1, 4, 3, 6, 5, \ldots, N, N-1].
Why does this work?
Let’s look at even and odd indices separately.
For an even index, say 2i, the corresponding sum is 1 + 2 + \ldots + 2i = \frac{2i(2i+1)}{2} = i(2i+1). This is not divisible by 2i.
For an odd index, say 2i+1, the corresponding sum is 1 + 2 + \ldots + (2i-1) + 2i + (2i+2) = i(2i+1) + (2i+2).
This can be further simplified into (2i+1)(i+1) + 1, which isn’t divisible by (2i+1) (since it leaves a remainder of 1 when divided by 2i+1).
This way, both the odd and the even indices are satisfied, so we’re done.
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:
for i in range(1, n+1, 2): print(i+1, i, end = ' ')
print()