PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
PROBLEM:
You’re given a permutation P of \{1, 2, \ldots, N\}.
One operation is as follows:
- Choose a sequence S = [S_1, S_2, \ldots, S_{2K}] of even length, consisting of distinct integers between 1 and N.
- For each i = 1, 2, \ldots, K, swap the values at indices S_{2i} and S_{2i-1} of P.
Find a sequence of \leq \left\lceil \log N \right\rceil operations that sorts P.
EXPLANATION:
The key to solving this task is the knowledge that any permutation can be decomposed into disjoint cycles.
That is, if you create a graph with N vertices, and edges between i and P_i for each i, the resulting graph will look like several disjoint cycles.
To see why, note that if you start at some i and keep moving as:
i\to P_i\to P_{P_i} \to \ldots you must eventually reach some point you’ve reached before; but since it’s a permutation each vertex has exactly one incoming edge and so you must reach i.
If the concept is new to you, here’s a nice blog about permutations.
Decomposing a permutation into its cycles in \mathcal{O}(N) is quite easy: simply perform the process mentioned about (that is, start at some i and keep moving to P_i as long as you can).
Our objective is to end up with P_i = i for every i, which in terms of cycles means that every cycle must have length 1.
We’re allowed \left\lceil \log N \right\rceil moves, which usually suggests some sort of halving or doubling process.
And indeed, that is exactly what we’ll do!
Suppose we have the cycle (x_1, x_2, \ldots, x_M) (meaning P_{x_1} = x_2, P_{x_2} = x_3, \ldots, P_{x_M} = x_1)
Consider what happens if we swap the values at indices x_1 and x_2, x_3 and x_4, x_5 and x_6, and so on.
If M is even the final swapped pair is x_{M-1} and x_M; otherwise it’s x_{M-1} and x_{M-2}.
Initially, P_{x_1} = x_2 and P_{x_2} = x_3.
After swapping them, we’ll have P_{x_1} = x_3 and P_{x_2} = x_2.
Similarly, we’ll have P_{x_3} = x_5 and P_{x_4} = x_4 after the swap, and so on.
That is, everything at an even index gets fixed, while the odd indices will now form the new cycle (x_1, x_3, x_5, \ldots)
So, we’ve managed to halve the length of this cycle using one operation (specifically, we’ve gone from length M to length \left\lceil \frac{M}{2} \right\rceil since if M is odd the last element is untouched).
However, notice that this is completely independent of the other cycles!
So, the above halving can be performed simultaneously on every cycle of P.
This halves all their lengths, so repeating this process \left\lceil \log N\right\rceil times will ensure that every cycle has length 1, which is what we want!
This gives us a rather easy-to-implement solution. While P is not sorted, repeat the following:
- Find all cycles in P in linear time.
- For each cycle, swap adjacent pairs of elements as we did above, hence halving all their lengths.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (Python)
def find(p):
n = len(p)
mark = [0]*n
what = []
for i in range(n):
x = p[i]-1
if i == x: continue
if mark[x]: continue
y = i
while mark[y] == 0 and mark[x] == 0:
what.append(y)
what.append(x)
mark[x] = mark[y] = 1
y = p[x]-1
x = p[y]-1
return what
def move(p, op):
k = len(op)
for i in range(0, k, 2):
x, y = op[i], op[i+1]
p[x], p[y] = p[y], p[x]
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
ans = []
while True:
op = find(p)
if len(op) == 0: break
ans.append(op)
move(p, op)
print(len(ans))
for op in ans:
for i in range(len(op)): op[i] += 1
print(len(op), *op)