@Balaji : By using Dave's algo it gives TLE and it should be ...try taking n
as large as 10^18. How did u reduce the no. of iterations in this case
??
On Mon, May 23, 2011 at 9:07 PM, Balaji S balaji.ceg...@gmail.com wrote:
@Dave: nice idea.. ll this give AC ?
--
You received this
@Dave,Balaji,Samby.. Without the matrix exponentiation, the time is not
possible, and without using the intermediate modulo operater as suggested by
Dave, the value cannot be accommodated, as the 300th fibinocci number alone
comes to
--
It's done. Today I tried it.
Simply for N=0 and N=1 answer is (0,0) = 0 and (1,1)=2 respectively.
For other cases, you can get the solution with fib(N+3). Starting fib(1) =
1, fib(2) = 1...
Matrix Exponentiation, and Modulus for given constraints are necessary to
pass the solution.
On Mon,
@aakash
the cases are clear but can you explain how you did the matrix
exponentiation part ??..explain plz...i'm not getting it...
On Tue, May 24, 2011 at 1:25 AM, Aakash Johari aakashj@gmail.comwrote:
It's done. Today I tried it.
Simply for N=0 and N=1 answer is (0,0) = 0 and (1,1)=2
@Akshata: Actually, you only need to find the n+3rd Fibonacci number,
modulus 17. This saves you from having to deal with big
integers. Something like this should do for the calculation, assuming
that long long int is 64 bits:
long long int n;
int a = 1, b = 2, c;
for(i = 0; i n, i++)
{
Replying to my own posting! Even better, since it replaces the
relatively slow modulus operation with a comparison and subtraction:
long long int n;
int a = 1, b = 2, c;
for(i = 0; i n, i++)
{
c = a + b;
a = b;
b = c 17 ? c : c - 17;
}
// b is the result
Dave
On
@Dave: nice idea.. ll this give AC ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For
