Here is the link to the problem: 987E - Петя и перестановки

My solution is:

1. A constructive algorithm to count the number of steps from the identity permutation to the given input permutation. [PROVEN]

2. Compare the parity of the number of steps required with the parity of $$$3n$$$ and $$$7n+1$$$ and print Petr or Um_nik.

Now, I have used the following lemma: If one permutation $$$P1$$$ can be reached from another permutation $$$P2$$$ in even number of steps, then it is not possible to reach $$$P1$$$ from $$$P2$$$ in odd number of steps. Similarly, vice versa.

I can't prove this lemma, and I have tried:

• Induction
• Greedy proof techniques

and they don't seem to work. Any help will be appreciated! Thanks!