PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, find two permutations A and B of length N such that \min_{i=1}^N |A_i - B_i| is maximized.
EXPLANATION:
The only thing that matters is the difference between A_i and B_i for each index i; that is, which elements are paired together.
So, for convenience, let’s set A = [1, 2, \ldots, N], and then decide B since that fixes the pairing.
Now, note that the minimum difference cannot be more than about \frac{N}{2}. Specifically,
- If N is even, the element \frac{N}{2} can attain a difference of at most \frac{N}{2} (which happens only when it’s paired with N).
- If N is odd, the element \frac{N+1}{2} can attain a difference of at most \frac{N-1}{2} (which happens when it’s paired with either 1 or N).
More succinctly, it can be seen that the minimum possible difference is at most \left\lfloor \frac{N}{2} \right\rfloor.
With this in mind, it’s not too hard to find a B such that |B_i - i| \geq \left\lfloor \frac{N}{2} \right\rfloor - simply rotate A.
That is, we obtain
For example, if N = 6 we obtain B = [4, 5, 6, 1, 2, 3], and if N = 9 we obtain
B = [5, 6, 7, 8, 9, 1, 2, 3, 4].
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print(*list(range(1, n+1)))
print(*list(range(n//2 + 1, n+1)), *list(range(1, n//2+1)))