Exactly what the topic says. I am getting TLE with my solution. I have looked over my solution and the tester’s solution and they do exactly the same thing (I didn’t copy). But for some reason mine is running slower even though it is in c++11. I even use std::unordered_map vs the std::map of the tester’s solution, so I am just stumped as to what could possibly be taking it so long.
If someone could take a look and tell me what I am doing wrong, that would be nice, thanks.
Suppose a permutation with single cycle N, your solution compute the cycle for every number, which is O(N^2) in total. tester’s solution ensure that each cycle is computed only once, keeping the time complexity at O(N).
But isn’t the point to calculate the cycle length for each number? Why is cycle only calculated once for each position? Is there a math explanation for this?
Every permutation can be partitioned into disjoint cycles, and every number in the same cycle has the same cycle length. So once find a cycle, recording the length for each number in the cycle is enough.