[Community Puzzle] Divisibility of Fibonacci numbers sum

https://www.codingame.com/training/hard/divisibility-of-fibonacci-numbers-sum

Send your feedback or ask for help here!

Created by @OPi1,validated by @tutubalin,@pardouin and @RoboStac.
If you have any issues, feel free to ping them.

Is it possible to solve this problem on java? I solve using the matrix method, and I cannot pass further than test 6. I get failure with message “Process has timed out”

It’s solvable in any language.
There’s another fast method that is similar to fast exponentiation.
You can compute the term of rank n based on the terms of rank ~n/2.
Try to find the exact relation.

1 Like

Now I use the fast doubling algorithm to find the required number in the series. And I determine the sum of the series by the formula - Fa + … + Fb = Fb+2 - 1 - (Fa+1 - 1)
Still, this is not fast enough and the test fails. How long should the tests take? On my laptop, dividing the sum of a series from 1,000,000 to 10,000,000 takes 1263 ms.

When you calculate a f_n, do it with the required modulus right from the start.
That way, the numbers never grow big.
If you keep the actual values of f_n, the binary representation of f_n will be O(n) so you lose the benefits of having a O(log n) algorithm to compute it.

2 Likes

Continuing the discussion from [Community Puzzle] Divisibility of Fibonacci numbers sum:

I managed to clear test 7, but then really get out of hand fast, even with f_2n and f_2n+1 relations. My functions can’t even calculate f_10,000,000 (with the forementioned relations), it just times out.

Looking for optimizations is fun though.

At some point the numbers involved have so many digits that despite having a quick algorithm to reach them, you will take too much time to perform basic operations with them.

So really, as all you need is their modulus, apply this modulus right from the start and at each step of the algorithm.

1 Like