https://www.codingame.com/training/hard/divisibility-of-fibonacci-numbers-sum
Send your feedback or ask for help here!
Created by @OPi,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.
2 Likes
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.
2 Likes
Hey everyone! I am quite new here, and I don’t know where to look at for hints or solutions.
I use C++, I use the trick to compute the sum out of two values only, I use the doubling formula, and I only use the modulus in that formula.
And yet, I seem to be to slow, even for #6. Any idea where that might come from?
I use a recursive function for the doubling formula, is there a faster way? Maybe I should keep in memory the Fibonnaci numbers I have already computed?
Thank you for any help.
You don’t need to memoize so it’s not the problem.
pm me your code if you want, I’ll see if I spot a bottleneck somewhere.
2 Likes
You seem made the good choices. I guess there is a hidden bug somewhere.
I checked test cases in Python, JavaScript and C, also with a recursive implementation.
Like pardouin said, there is no need to memoize value. I conceived this challenge to avoid that necessity. You can memoize but it is not necessary and (normally) that doesn’t help to solve it.
If you don’t make progress send me your code. I will take a look.
2 Likes
Thanks for the answer.
I managed to get up to challenge #8 by removing a useless function call.
I cannot get any further though. I tried to pm you my code but it seems I can’t send you pm yet?
DoDoot, the option “Allow other users to send me personal messages” is checked in my preferences. But I never used message here, so I don’t know if there is some restriction.
If it doesn’t work when you will try again, you can send me an email to olivier.pirson.opi@gmail.com
Hi everyone,
I don’t inderstand how it is possible to avoid timeout.
I tryied the the formula - F(a) + … + F(b) = F(b+2) - 1 - (F(a+1) - 1) given in this discussion
I use the modulus at each step
I still timeout on tests 7, 8 and 9.
When I submit, timeout is on tests 8 and 9.
Do i use the good formula ?
4 Likes
Your formula is fine but you also need a fast formula to compute F(n) for any n.
There’s one formula based on division by 2, try to find it.
Also, when you implement it, keep in mind that you have better chance to make it work with ascending dynamic programming than by using a descending recursion.
2 Likes
@pardouin, normally a simple descending recursion is enough.
@Remi_avec_un_i, like pardouin said, you need to compute F(n) faster. If you need n steps to compute F(n), this is not fast enough.
1 Like