I’ve spent a lot of time trying to solve this problem and exceed the time limit. I’ll explain my approach and it would be helpful if someone could please explain a better way of (1) how to find the cycle lengths and (2) how to find the LCM of the cycle lengths.
My solution: http://www.codechef.com/viewsolution/4335406
-
I take the permutation input as String[] then loop through and parse it into an int[], at the same time adding each position to an ArrayList that keeps track of positions I need to find cycle length of.
-
To find cycle lengths I use an ArrayList and while it is not empty, I use a helper method that increments each time the length is found to be longer in a cycle. I remove positions that have been looked at from ArrayList, and in a different ArrayList I store cycle lengths (but no duplicates if two cycle lengths are equal)
-
To find LCM, I use a method that takes the ArrayList of cycle lengths as params. I turn the int LCM into BigInteger and compare it with next value in list one at a time.
I understand how my program works, and it works for all my tests cases, but how can I make finding the cycles more efficient? Am I doing something wrong with BigInteger? I’ve seen some posts about using prime factorization, and I’m struggling to understand this approach too. I’d like to know how I can make this code more efficient.
Thanks!
[Solved]
Finding the cycle lengths as explained in the editorial fixed the time problem. For anyone interest in a Java solution using BigInteger, see my solution: http://www.codechef.com/viewsolution/4335574