Super-rocky Terrain#11842

Super-rocky Terrain (Editorial)

One of the possible arrangements is

1, 3, 2, 5, 4, \dots

i.e. in the sorted permutation swap positions $2 k$ and $2 k + 1$ for all $k = 1, \dots, ⌊(n - 1) /2 ⌋$ k=1,\dots,\lfloor(n-1)/2\rfloor. Time complexity $O (n)$ because we know all the elements since it's a permutation, so no sorting is needed.

The original harder version used an arbitrary array of $n$ numbers. To solve it, sort to obtain $b_{1}, \dots, b_{n}$ b_1,\dots,b_n; split into $s ma l l = {b_{1}, \dots, b_{⌈ n /2 ⌉}}$ small=\{b_1,\dots,b_{\lceil n/2\rceil}\} and $l a r g e = {b_{⌈ n /2 ⌉ + 1}, \dots, b_{n}}$ large=\{b_{\lceil n/2\rceil+1},\dots,b_n\}. Build $r es = {s ma l l_{last}, l a r g e_{last}, s ma l l_{last - 1}, \dots}$ res = \{small_{\text{last}},\,large_{\text{last}},\,small_{\text{last}-1},\dots\} and verify the zig-zag condition $r e s_{1} < r e s_{2} > r e s_{3} < r e s_{4} \dots$ \,res_1<res_2>res_3<res_4\dots Overall complexity $O (n lo g n)$ O(n\log n) due to the sort.

k = 1, \dots, ⌊(n - 1) /2 ⌋

b_{1}, \dots, b_{n}

s ma l l = {b_{1}, \dots, b_{⌈ n /2 ⌉}}

l a r g e = {b_{⌈ n /2 ⌉ + 1}, \dots, b_{n}}

r es = {s ma l l_{last}, l a r g e_{last}, s ma l l_{last - 1}, \dots}

r e s_{1} < r e s_{2} > r e s_{3} < r e s_{4} \dots

O (n lo g n)