_spartan's blog

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

| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. That helped, especially that blog.