JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Linear recurrences (Article) About evaluating the series
 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) = 2If 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.