Please read the new rule regarding the restriction on the use of AI tools. ×

_spartan's blog

Matrix Multiplication questions
By _spartan, 10 years ago, In English

So, I was trying to solve this problem on a codechef contest that ended just now.I tried to reduce the expression of g(n).The maximum I could simplify is upto this point:

g(n) = pow(4, n) + 2*(pow(4,n)-1)/3 + Summation of (pow(4,n-k)*f(k)) where k ranges from n to 1.

But I couldn't find a way to find sum of function f upto a point.

On looking at accepted codes, I find that this question was to be done using Matrix Multiplication, kind of what we do in finding fibonacci numbers.

I want to know how do you guess the values in the matrix to be multiplied.?Is there a particular way to be followed around such questions..?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Some general explanation: http://community.topcoder.com/tc?module=Static&d1=features&d2=010408 Interesting blog: http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. That helped, especially that blog.

    → Reply