I try to find fib(2*n-2)/fib(n-2) but I get TL on test 4, my algo is linear so I couldn't pass the TL, I wonder is the direct algo for finding fib(n-2) and fib(2*n-2) better, because I couldn't implement it :)
Well, my idea was to evaluate fib(n-2) and fib(2*n-2) using the direct formula for fib(n)- as function of n, but I couldn't implement it , while the bruteforce solution was TL, anyway I'm gonna think a bit more about it, btw congrats for the victory, guys, you did a great job, also a great competiton for ACRush as always :)
Yup, I used BigInteger but O(n) gave me TL, so does there exist a solution which doesn't use advanced maths techniques such as the described above, because I tried to use BigDecimal but it loses precision when trying to calculate directly Fib(n)
Hi Boris :) Here my sol: There is sequence a(i)=a(i-1)+a(i-2), a(1)=1,a(2)=3. Ans for this problem is a(n). I tried to calculate it O(n) and it taked ~ 17 sec in n=40000. Then I tried to calculate it o(logN) and it,of course, slower then O(n).
Is there any special quick algo for long numbers?(sum or product)
Yup, but if you use some math knowledge you will find that the result is fib(n-1)+fib(n+1), during the competition as far as I got was the result you mentioned, but I think implementing it is improbable task, anyway can someone send accepted C++ solution to me at ttsonkov [at] gmail.com, I'd be very grateful, cos I implemented the algo with the matrix but I still get TL.
I use this formula: f(N)+f(n-2) where F(0)=1, F(1)=1, F(N)=F(N-1)+F(N-2). But wa. What is in the test 4. I checked the answer for N=7000 at the forum and it matches the answer that my program gives. Can anybody give me a test for 4.
We can state that f(21)=4181*f(1)+6765*f(2), f(22)=6765*f(1)+10946*f(2). Wherefore we can calculate f(i),f(i+1) with N/20 operations. All we need is addition of two long numbers (I used base 10000 for them) and multiplication of long number and simple one, that's all. The usage of recursion formula f(2n)=f^2(n)+f^(n+1) (or something like that) is overridden here by the cost of multiplication of two long numbers.
@Spirit: If you want to I can give you my accepted Java source, please give me your mail, but I'm interested in any accepted C++ solutions, please send to firstname.lastname@example.org, cause all my C++ efforts were unsucessful, btw I used base 10^9 and I was losing accuracy :)
Today I solved this problem using some nice (and easy to find) formulas for computing F[n]: F[2n] = F[n]*(F[n-1] + F[n+1]) and F[2n-1] = F^2[n-1] + F^2[n] with these you cand recursevly compute F[n] fast enough (~0.25 sec). I also precalculated a table with first 2000 Fibonacci and when the recursion dropped below 2000 it returned the computed value. I see some nice times on the best AC list. Will you please tell us how you did it? What formulas, optimizations... Thank you