JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
About evaluating the series | Reply
Dear all,
Would anyone explain for me how to evaluate the series... And if possible give a detailed example... preferable problem C in Round 1 A in the 2008 Google Code Jam as I spent 2 days reading codes and tutorials trying to understand but all went in vain :(
Thanks so much...
Re: About evaluating the series (response to post by a.mounir86) | Reply
Hmnn. I'll assume you got the recurrence (which is a huge story to explain how to get)

In that problem the recurrence I found was:

F(n) = 6*F(n-1) - 4*F(n-2)

I know F(2)=28, F(1) = 6 and F(0) = 2

If we want to take a pair (6,2) and get the next pair (28, 6) based on the formula above...

(6,2) x ??? = ( 28, 6 )

(6,2) x ??? = ( 6*6-4*2, 6 )

If the pair was (x,y) :

(x,y) x ??? = ( 6*x-4*y, 1*x + 0*y )

So, this ??? thing we got to find will convert the pair to the next pair when you multiply to it.

From the definition of matrix product:

(x , y)x( 6 1) = (6*x - 4*y , 1*x + 0y)
        (-4 0)      


Anyway, to get the second pair:

(6 , 2)x( 6 1) = (6*6 - 4*2 , 1*6 + 0) = ( 28, 6)
        (-4 0)      


We can now guess that if we raised ( (6,1),(-4,0) ) to the (n-1) power, we would have a matrix we can multiply to (6,2) to get the nth pair. And evaluating the nth power of a 2x2 matrix takes O(log(n)) time.

PS: Is this what you meant?
Re: About evaluating the series (response to post by vexorian) | Reply
Really thank you so much, now I understand and of coarse your reply helped me a lot :)
Re: About evaluating the series (response to post by vexorian) | Reply
Will be happy if you can point me to any tutorial , how you find those values
Re: About evaluating the series (response to post by FameofLight) | Reply
what values?

Well, there's now an editorial for this problem: http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiE2QUM (click on contest analysis, then problem C)
Re: About evaluating the series (response to post by vexorian) | Reply
I am asking for 6 , -4 which you said was long story , Thanks for pointing to tutorial , I got what I want.
RSS