I participated in the codeforces educational round 4 and I liked problem E (Square Root of Permutation) that involves finding square root of a given permutation. The solution requires representing the permutation as a graph then decomposing this graph into cycles. Checking certain properties of these cycles such as the number of even cycles with the same length is the key point to finding a solution.
The idea of considering a permutation as a graph and mapping operations on the permutation to operations in the corresponding graph is very new and interesting to me. I tried to search in Google and Codeforces about other problems and explanations related to this concept but I was not able to find relevant stuff other than: Wikipedia article and a codechef problem. I wonder whether you can share some resources about this topic that you might have met during practice or suggest better keywords for finding relevant resources.
The idea of decomposing a permutation into disjoint cycles comes from group theory. You may learn more about this topic by studying group theory and abstract algebra (more specifically, symmetric groups https://en.wikipedia.org/wiki/Symmetric_group ). In the past all the groups that were studied were considered to be a subgroup of some symmetric group. Later another more abstract definition of a group was given and proved to be equivalent.
I like the textbook "Modern Algebra" by Dummit and Foote on this topic, but other better resources may exist.
Here is an excellent explanation of the cycle notation for permutations: http://people.math.sfu.ca/~jtmulhol/math302/notes/4-Permutations-CycleForm.pdf
Here is an interactive website on permutations and cycles: http://nrich.maths.org/2789 . I found this one particularly fun since it illustrates permutations and cycles in an intuitive way.
none of the pages exists!
A nice problem I encountered recently in an AtCoder contest, which might help anyone visiting this blog.
thanks found this trick of grouping into disjoint cycle very helpful
Another good problem .
Also this is a harder version of the problem https://kilonova.ro/problems/3952