Discussion @ 1462. Uncle Scrooge's Gold @ Timus Online Judge

How to improve my Algo. I got TL on test 4 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 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 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 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 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 VALERO 13 Aug 2006 00:18

Who can you write me om email the algorithm or in what book i can find it?
Thanks.
adas@simnet.kiev.ua

Re: How to improve my Algo. I got TL on test 4 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 Anton [SUrSU] 13 Aug 2006 18:32

What is the answer fo this test?
n = 7000

Re: Test data UdH-WiNGeR 13 Aug 2006 20:23

81937319032993876558582070063011262115783024656965723338526424275071630557443673768160691777974344039339079218543821663526642065353277478431909789983160736348837929626796434540999450923786205450782143686270382692873692233405139629109704561270312322297501776980155782647708033073460077811847296059544586515736242655594916292010288630241998587835886957464588315061688674744586049802510938100726026534538639883653835446753146728656928193874140316597540202353213455487305219113003826047850156459479457447951648423579548704045234844929446845423587933723079796158760129023524040519672308404718221125336963212128205511547407802595672777585867901520427711491099757592076124797583476061864630025076181920889182653070760272884159824308542397653852400985696907858408387639956157978706489167805462854368911415071677899319871467455602850964575780531369593561207038707991166116257391616617990142018311285809472372949541001826651548109149596409807197380997932230498982610632747317000197354547509949735065278160290108373521163485352357077038417341404680343430978229222267611931184569548788576280109768575772879672619415599295926884517066063939649588253695834282602632479823971486742422068816044196848224503022646081677385555572595399717609483383203051148447238015528377198350218937442030369055848713320280710524550172256486540262008219704955151944469303730096667265538925353091481286313382299155890271045282453432557272252772046637042581378078908572780035752442042046549675078127

Re: Test data 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.
Give some hints please

Re: Test data Sid 13 Aug 2006 23:25

Just use java.math.BigInteger in Java.=)

Re: Test data 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 Vasilevskiy Boris 14 Aug 2006 14:35

It`s improbable task!
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 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 Kaliningrad SU -J_A_MES-HeadLiner 31 Aug 2006 20:45

Of course there are fast algorithms for long multiplication. Try to find FFT or FHT.

Your formula is incorrect! SPIRiT 14 Sep 2006 18:48

The actual answer is fib(2*n-1)/fib(n-1). Just check the sample answer....

Re: Your formula is incorrect! 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.

Re: Your formula is incorrect! Todor Tsonkov 15 Sep 2006 18:21

Anyway, Java rulez!!! O(logn) got accepted in about 0.7s. ,yet it would be interesting to see some C++ solutions

Re: Your formula is incorrect! SPIRiT 15 Sep 2006 19:50

What do you mean result is fib(n-1)+fib(n+1)?
For sample (n=3) fib(2)+fib(4)=2+5=7, but real answer is 4. Check that yourself

Re: Your formula is incorrect! Todor Tsonkov 15 Sep 2006 23:26

@spirit:
It depends on how you get the Fibbonacci sequence
if fib(1)=1, fib(2)=1, fib(3)=2 and etc. you get the desired result :)

Oh I get it SPIRiT 18 Sep 2006 18:15

Well, then my formula is fib(n-2)+fib(n)

No subject 3a[3.141592..]Jlu 18 Mar 2009 15:10

I use linear algo O(N) + long addition (10^18), but I got TL#4 :( Please help me.

Discussion of Problem 1462. Uncle Scrooge's Gold