Here is the link to the problem: 987E - Petr and Permutations
My solution is:
A constructive algorithm to count the number of steps from the identity permutation to the given input permutation. [PROVEN]
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!