Skyline#12306

Skyline (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

We are given a permutation $p$ of ${1, 2, \dots, n}$ \{1,2,\dots,n\} and define

a_{i} = \frac{p _{i}}{i} .

a_i=\frac{p_i}{i}.

The required condition is

a_{1} < a_{2} > a_{3} < a_{4} > a_{5} < \dots

a_1<a_2>a_3<a_4>a_5<\dots

i.e. even indices are local maximums and odd indices are local minimums.

Instead of comparing neighbors directly, we enforce a stronger invariant:

for every even index $i$ , make
$a_{i} > 1,$
a_i>1,
for every odd index $i \geq 3$ i\ge3, make
$a_{i} < 1.$
a_i<1.

If this holds, the zig-zag condition is automatically satisfied.

So we only need a permutation that enforces these inequalities.

Construction

set
$p_{1} = 1,$
p_1=1,
so
$a_{1} = 1.$
a_1=1.
for every even index $i < n$ i<n, set
$p_{i} = i + 1, a_{i} = \frac{i + 1}{i} > 1.$
p_i=i+1, \qquad a_i=\frac{i+1}{i}>1.
for every odd index $i \geq 3$ i\ge3, set
$p_{i} = i - 1, a_{i} = \frac{i - 1}{i} < 1.$
p_i=i-1, \qquad a_i=\frac{i-1}{i}<1.
if $n$ is even, set
$p_{n} = n, a_{n} = 1.$
p_n=n, \qquad a_n=1.

This directly gives

p = [1, 3, 2, 5, 4, 7, 6, \dots]

p=[1,\,3,\,2,\,5,\,4,\,7,\,6,\,\dots]

(with $n$ at the end if $n$ is even).

A valid construction exists for all $n \geq 1$ n\ge1, so we never output $- 1$ .

Complexity $O (n)$ .

for _ in range(int(input())):
    n=int(input())
    p=[0]*n
    for i in range(n):p[i]=i+1
    for i in range(1,n-1,2):
        p[i],p[i+1]=p[i+1],p[i]
    a=[p[i]/(i+1) for i in range(n)]
    for i in range(1,n-1):
        if(i%2==0):
            assert(a[i-1]>a[i] and a[i]<a[i+1])
        else:
            assert(a[i-1]<a[i] and a[i]>a[i+1])
    print(*p)

Python