[Solved] Solving SGARDEN - Java Approach

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

  1. 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.

  2. 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)

  3. 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

You can have a look at this editorial :

http://discuss.codechef.com/questions/47240/sgarden-editorial

1 Like
//