PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: harsh_h
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, find a permutation P of the integers 1 to N such that
P_i \geq \left( P_{i-1} - P_{i+1}\right)^2 for every 1 \lt i \lt N.
EXPLANATION:
The final construction is very simple, but I’ll try to motivate the process of reaching there.
Intuitively, if P_i is small we’re a lot more constrained by its neighbors.
Looking at some small values, we see that:
- If P_i = 1 is placed in the middle of the permutation, the only possible way it can be \geq the square of the difference of its neighbors, is if said square is itself 1.
- In fact, the same applies to P_i = 2 and P_i = 3, since the next smallest square after 1 is 4.
Now, since we have three values that require their adjacent elements to have a difference of 1, and at most two of them can be placed on the borders (i.e at indices 1 and N, which don’t require the check), we definitely need at least one instance of P_{i-1} and P_{i+1} differing by 1.
(Note that N = 1 and N = 2 are edge cases here, but any permutation works for those so they can be safely ignored.)
But then if we’re creating one set of alternate elements with a difference of 1, why not try to do that for every pair of alternate elements?
After all, if every alternate difference is 1, the condition P_i \geq (P_{i-1} - P_{i+1})^2 will definitely be satisfied for every i.
This idea then gives rise to a construction:
- First, place the integers 1, 2, 3, \ldots in the odd positions in order.
- Then, place the integers N, N-1, N-2, \ldots in the even positions, again in order.
This results in the permutation
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
ans = [0]*n
l, r = 1, n
for i in range(n):
if i%2 == 0:
ans[i] = l
l += 1
else:
ans[i] = r
r -= 1
print(*ans)