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:
For a permutation P, define:
- f(P) to be the number of indices i such that P_i = i.
- g(P) to be the maximum value of f(Q) across all Q that are cyclic shifts of P.
Given N, find any permutation of length N that minimizes f(P).
EXPLANATION:
Since we’re dealing with cyclic shifts, all indices can be looked at modulo N - i.e. if we refer to index N+1 that’s the same as referring to index 1, and so on.
Observe that in the j-th cyclic shift, the element initially at position i will be at index (i+j).
In particular, this means the value P_i, which is initially at position i, will end up at index P_i in exactly the (i - P_i)-th cyclic shift.
Or, more simply: for each element, there is exactly one cyclic shift for which it will be a fixed point.
We have N cyclic shifts and N elements.
Our goal is to minimize the maximum of f (the count of fixed points) across all cyclic shifts. So, the absolute best case scenario we can hope for is to have each element be the fixed point of a different cyclic shift; which would make the maximum 1.
If you try to construct answers for small values of N, you might notice that you’re able to successfully obtain g(P) = 1 for N = 1 and N = 3, but not N = 2 and N = 4 (where the best you can do is g(P) = 2).
And indeed, it can be proved that for even N, it’s impossible for any permutation to have g(P) = 1, so the best we can do is g(P) = 2.
For odd N however, g(P) = 1 is attainable, as we’l construct below.
Proof
Suppose N is even, and we’re able to construct a permutation P for which all the (i - P_i) values are distinct.
Let d_i = i - P_i. Note that all computations here are being done modulo N.
Then,
- d_1 + d_2 + \ldots + d_N must equal (1 + 2 + \ldots + N) since we claimed that all the d_i values are distinct.
- On the other hand, d_i = i - P_i.
So, d_1 + \ldots + d_N must also equal (1 + 2 + \ldots + N) - (P_1 + P_2 + \ldots + P_N).
However, all the P_i are distinct (P is a permutation, after all), so (P_1 + P_2 + \ldots + P_N) = (1 + 2 + \ldots + N).
This means (1 + 2 + \ldots + N) - (P_1 + P_2 + \ldots + P_N) = 0.So, we obtain the fact that 1 + 2 + \ldots + N = 0 (modulo N).
This means \frac{N\cdot (N+1)}{2} must be a multiple of N.However, when N is even, \frac{N\cdot (N+1)}{2} cannot be a multiple of N, because \frac{N+1}{2} isn’t an integer!
So, for even N, it’s impossible for all the i - P_i values to be distinct.
All that remains is to construct a valid permutation.
There are likely several constructions, with one very simple one being
That is, just place all values in reverse order!
To see why this works: let’s understand what’s going on with the (i - P_i) values.
We have P_1 = N, so for i = 1, i - P_i = 1 - N = 1 (recall that we’re working modulo N, so 1-N is equivalent to 1).
Now, when moving from i = 1 to i = 2, the index increases by 1, while the value reduces by 1.
So, the value of i - P_i increases by 2, and becomes 3 - indeed, this can be seen as 2 - (N-1) = 3-N which is 3 modulo N.
In fact, this applies to every single index: when we move one step right, the value of (i - P_i) increases by exactly 2.
Since it starts as 1, this means it goes as 1, 3, 5, 7, \ldots as we progress along the array, i.e. along the odd numbers.
Now,
- When N is odd, the last odd number \lt N is N-2.
Once the (i - P_i) value reaches N-2, the next index it will become N (which is equivalent to 0 modulo N).
Once it hits 0, since the “increase by 2” part remains the same, it then goes through the values 2, 4, 6, \ldots till at the very end, it reaches N-1.
This way, the (i - P_i) values would have gone through every possible value in [0, N-1] exactly once, which is what we required for g(P) = 1 to hold. - When N is odd, the last odd number \lt N is N-1.
Once (i-P_i) reaches N-1, in the next index it will increase by 2 and become 1 instead.
This means it will once again just repeat going through 1, 3, 5, 7, \ldots for the second time.
In fact, it will go through all of 1, 3, 5, \ldots, N-1 exactly twice each - and this will give us g(P) =2 (since no (i - P_i) appears more than two times), which is optimal for even N.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
print(*reversed(range(1, n+1)))