You are not logged in. Please login at www.codechef.com to post your questions!

×

Matrix exponentiation

0
1

For equation F(x) = F(x-1) + F(x-2) + ( F(x-1) * F(x-2) ) given F(0) and F(1) can we calculate F(n) in log(n) time?

asked 19 Feb, 19:40

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

edited 19 Feb, 19:43


Well, you can just define $G(x) = F(x)+1$, which has the recurrence relation $G(x) = G(x-1)G(x-2)$, which you can calculate in $\log(n)$ time.

link

answered 20 Feb, 23:29

theoneyouwant's gravatar image

5★theoneyouwant
434
accept rate: 0%

Wow..... How did you got this logic ??
Awesome....

(21 Feb, 00:57) l_returns5★

I see it's available on math. stack exchange

(21 Feb, 01:05) l_returns5★

@theoneyowwant how to calculate G(x) = G(x-1)G(x-2) in log(n) time?

(21 Feb, 10:06) phantomhive4★

It's just Fibonacci in power... Take log and see the pattern... Then use matrix exponentiation as shared by @sagar2405

(21 Feb, 10:09) l_returns5★

I hope it's not a question for an ongoing contest... Otherwise you can be banned from discuss site... Please delete this post in case it's for an ongoing contest...

(21 Feb, 10:10) l_returns5★

Well, I just thought of this myself, since it's somewhat similar to think of it as a functional equation, where such transforms are quite common. In general, you can try such substitutions on various reccurences to get a better form/ to solve it faster. You may have also solved some dynamic programming problems where redefinitions give a faster solution.

(21 Feb, 12:05) theoneyouwant5★
1

Its not from a ongoing contest , its from a past contest i cam across ..

(22 Feb, 13:34) phantomhive4★
showing 5 of 7 show all

We can easily found f(n) in O(n) time,but not sure about O(logn).

link

answered 20 Feb, 22:13

sagar2405's gravatar image

4★sagar2405
01
accept rate: 0%

yeah O(n) is pretty simple but the problem required log(n) or something similar . 0 < n < 10^8..

(20 Feb, 23:07) phantomhive4★

This problem is similar of finding nth Fibonacci in O(logn) time. I found this, https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ , in which we can find fibonnaci in O(logn) time. Hope this might help.

(20 Feb, 23:28) sagar24054★

I found it online that $ F(n) = 2^{Fib(n)}-1 $ when f(0)=0 and f(1)=1. And $ 2^{fib(n)} $ can be calculated in $logn$. But it is special case. For the generalized version, @theoneyouwant wrote the perfect answer.

link

answered 21 Feb, 01:16

m_never_dies's gravatar image

4★m_never_dies
335
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×138

question asked: 19 Feb, 19:40

question was seen: 185 times

last updated: 22 Feb, 13:34