239 - Tempus et mobilius. Time and motion

[vanessa]

Hi all... what is the output for this

Code: Select all

354
1027
1400
2000
2500
3400
5321
6000
6700
7000

thx

[seedman]

354 balls cycle after 4616520 days.
1027 balls cycle after 10811920 days.
1400 balls cycle after 2520540 days.
2000 balls cycle after 489940 days.
2500 balls cycle after 349605 days.
3400 balls cycle after 3960198 days.
5321 balls cycle after 105969950976 days.
6000 balls cycle after 5925 days.
6700 balls cycle after 124080589096182 days.
7000 balls cycle after 207574488 days.

[brianfry713]

You only need to simulate the clock for 12 hours, from that you generate the permutation array.
Then keep applying the entire permutation array to all balls until all balls have cycled at least once. You only have to check them at the end of each day.
Then you have the cycle length of each ball and compute the LCM of that for all balls.
For 7000 balls, it will take 6281 days for all balls to cycle at least once.
My AC code takes 0.3 seconds to generate the output for 7000 balls.

[brianfry713]

My approach above got AC in 0.228 seconds.

To optimize even further, iterate each ball individually through the permutation array and calculate the cycle length.
Mark each location as visited so you don't have to repeat the same permutation loops.
All of the cycle lengths can be computed in O(N) instead of O(N * N).