How to improve my Algo. I got TL on test 4

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

fib(n) could be evaluated in O(log n) multiplication operations.

Re: How to improve my Algo. I got TL on test 4

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

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.

adas@simnet.kiev.ua

Re: How to improve my Algo. I got TL on test 4

Test data

What is the answer fo this test?

n = 7000

Re: Test data

81937319032993876558582070063011262115783024656965723338526424275071630557443673768160691777974344039339079218543821663526642065353277478431909789983160736348837929626796434540999450923786205450782143686270382692873692233405139629109704561270312322297501776980155782647708033073460077811847296059544586515736242655594916292010288630241998587835886957464588315061688674744586049802510938100726026534538639883653835446753146728656928193874140316597540202353213455487305219113003826047850156459479457447951648423579548704045234844929446845423587933723079796158760129023524040519672308404718221125336963212128205511547407802595672777585867901520427711491099757592076124797583476061864630025076181920889182653070760272884159824308542397653852400985696907858408387639956157978706489167805462854368911415071677899319871467455602850964575780531369593561207038707991166116257391616617990142018311285809472372949541001826651548109149596409807197380997932230498982610632747317000197354547509949735065278160290108373521163485352357077038417341404680343430978229222267611931184569548788576280109768575772879672619415599295926884517066063939649588253695834282602632479823971486742422068816044196848224503022646081677385555572595399717609483383203051148447238015528377198350218937442030369055848713320280710524550172256486540262008219704955151944469303730096667265538925353091481286313382299155890271045282453432557272252772046637042581378078908572780035752442042046549675078127

Re: Test data

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

Posted by

Sid 13 Aug 2006 23:25

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

Re: Test data

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

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

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.

Your formula is incorrect!

Posted by

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!

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!

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!

Posted by

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!

@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 :)