Sakurako and a Weird Permutation#409

Sakurako and a Weird Permutation (Editorial)

Author:

Bohdan Feysa

Task preparation:

Bohdan Feysa

Editorial:

Bohdan Feysa

Block : n\le 8:

In this block's solution, we will try to generate all possible permutation lists and check whether they are good for our permutation . Time complexity O(\binom{\frac{n\cdot(n-1)}{2}}{8}\cdot n). Which is less than 2.5\cdot 10^8.

Block : n\le 100:

For our permutation, we will create its cycle decomposition as follows:

  1. create its graph representation;

  2. compute for each vertex the set of those that are accessible from it in O(n^2);

  3. find the order of those numbers in a cycle.

Now that we have a cycle decomposition of our permutation, we take its transpositions and it is our answer. Time complexity O(n^2).

Block : n\le 10^5:

In this block's solution, we can use O(n\log{n}) time cycle decomposition of a permutation. When we have all cycles, we write out the edges of cycles and that is our answer. Because by using those permutations, we are creating an inverse of . And t[t^{-1}[i]]=i, and that is what we need to find.

Block : full solution:

We change our code to decompose a permutation into cycles in linear time. Then we write out the edges of a cycle, and that is our answer. Time complexity .