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:
create its graph representation;
compute for each vertex the set of those that are accessible from it in O(n^2);
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 .