ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1462. Uncle Scrooge's Gold

Pages: 1 2 Next
How to improve my Algo. I got TL on test 4
Posted by Todor Tsonkov 12 Aug 2006 19:35
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 :)
Re: How to improve my Algo. I got TL on test 4
Posted by VALERO 12 Aug 2006 19:40
i have tl too, but i find that
fib(2*n-2)/fib(n-2)=fib(n+1)+fib(n-1) ^)
but i have tl (
Re: How to improve my Algo. I got TL on test 4
Posted by Mafia {Toropov, Isenbaev, Oparin} SPb IFMO 12 Aug 2006 19:48
fib(n) could be evaluated in O(log n) multiplication operations.
Re: How to improve my Algo. I got TL on test 4
Posted by Todor Tsonkov 12 Aug 2006 19:55
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 :)
Re: How to improve my Algo. I got TL on test 4
Posted by UdH-WiNGeR 12 Aug 2006 20:20
Hint: direct formula is hard to implement, but we can rewrite it using linear algebra like this:

.....................................(0, 1)^(n-1)
(fib(n), fib(n+1))=(1, 1)*(....)
.....................................(1, 1)

, so we can use integer arithmetics!

Edited by author 12.08.2006 21:05

Edited by author 12.08.2006 21:05

Edited by author 12.08.2006 21:05

Edited by author 12.08.2006 21:06

Edited by author 12.08.2006 21:06

Edited by author 12.08.2006 21:06
Re: How to improve my Algo. I got TL on test 4
Posted by VALERO 13 Aug 2006 00:18
Who can you write me om email the algorithm or in what book i can find it?
Thanks.
Re: How to improve my Algo. I got TL on test 4
Posted by UdH-WiNGeR 13 Aug 2006 14:37
Here is an explanation of the algorithm in Russian:
http://algolist.manual.ru/maths/count_fast/fibonacci.php

Edited by author 13.08.2006 14:37
Test data
Posted by Anton [SUrSU] 13 Aug 2006 18:32
What is the answer fo this test?
n = 7000
Re: Test data
Posted by UdH-WiNGeR 13 Aug 2006 20:23
81937319032993876558582070063011262115783024656965723338526424275071630557443673768160691777974344039339079218543821663526642065353277478431909789983160736348837929626796434540999450923786205450782143686270382692873692233405139629109704561270312322297501776980155782647708033073460077811847296059544586515736242655594916292010288630241998587835886957464588315061688674744586049802510938100726026534538639883653835446753146728656928193874140316597540202353213455487305219113003826047850156459479457447951648423579548704045234844929446845423587933723079796158760129023524040519672308404718221125336963212128205511547407802595672777585867901520427711491099757592076124797583476061864630025076181920889182653070760272884159824308542397653852400985696907858408387639956157978706489167805462854368911415071677899319871467455602850964575780531369593561207038707991166116257391616617990142018311285809472372949541001826651548109149596409807197380997932230498982610632747317000197354547509949735065278160290108373521163485352357077038417341404680343430978229222267611931184569548788576280109768575772879672619415599295926884517066063939649588253695834282602632479823971486742422068816044196848224503022646081677385555572595399717609483383203051148447238015528377198350218937442030369055848713320280710524550172256486540262008219704955151944469303730096667265538925353091481286313382299155890271045282453432557272252772046637042581378078908572780035752442042046549675078127
Re: Test data
Posted by Anton [SUrSU] 13 Aug 2006 23:11
I know how to calc Fn in O(log n). But also i must use long arithmetic and TL in result.
Re: Test data
Posted by Sid 13 Aug 2006 23:25
Just use java.math.BigInteger in Java.=)
Re: Test data
Posted by Todor Tsonkov 14 Aug 2006 01:07
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)
Re: Test data
Posted by Vasilevskiy Boris 14 Aug 2006 14:35
While I use quick power raising of matrix, I still got tl
Then I tried to calculate it lineary and got AC, c++
Re: Test data
Posted by Petr 31 Aug 2006 17:45
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)

Edited by author 31.08.2006 17:50
Re: Test data
Of course there are fast algorithms for long multiplication. Try to find FFT or FHT.
Posted by SPIRiT 14 Sep 2006 18:48
Posted by Todor Tsonkov 14 Sep 2006 23:59
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.