How to solve SANBAN?

I would like to know to simplify the summation given in the problem SANBAN
ie) Σi*fibonacci(i)

LINK : Banta needs help

In this question, if you observe and calculate initial terms , you can get a simple formulae to
solve your problem.
The formulae for the problem is (n-1)*fib(n+2)-fib(n+1)+2.
and you can calculate nth fibonacci number using matrix exponentiation in O(logN) time which will pass both the subtasks,here’s the link
https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/. It is a great blog for understanding matrix exponentiation.
I hope this clears your problem! :slight_smile:

1 Like

First let us find out the sum of the first n Fibonacci numbers.

\begin{aligned} f(n) &= f(n+2) - f(n+1) \\ f(n-1) &= f(n+1) - f(n) \\ f(n-2) &= f(n) - f(n-1) \\ ...&=\;... \\ f(2) &= f(4) - f(3) \\ f(1) &= f(3) - f(2) \\ \sum_{i=1}^n f(i) &= f(n+2) - f(2) \end{aligned}

Now we are ready to solve the given problem.

\begin{aligned} n \times f(n) &= n\times (f(n+2) - f(n+1)) \\ (n-1) \times f(n-1) &= (n-1) \times (f(n+1) - f(n)) \\ (n-2) \times f(n-2) &= (n-2) \times (f(n) - f(n-1)) \\ ..... &= \;..... \\ 2 \times f(2) &= 2 \times (f(4) - f(3)) \\ 1 \times f(1) &= 1 \times (f(3) - f(2)) \\ \therefore \sum_{i=1}^n i \times f(i) &= n \times f(n+2) - \{f(n+1) + f(n) + ... f(3)\} - f(2) \\ &= n \times f(n+2) - \Big\{\sum_{i=1}^{n+1}f(i) - f(2) - f(1)\Big\} - f(2) \\ &= n \times f(n+2) - \sum_{i=1}^{n+1}f(i) + f(1) \\ &= n \times f(n+2) - f(n+3) + f(2) + f(1) \\ \sum_{i=1}^n i \times f(i) &= n \times f(n+2) - f(n+3) + 2 \end{aligned}

That is the final form which can be used to solve the problem. Here is my code for reference, using matrix exponentiation for calculation of the Fibonacci numbers : link.
Cheers!

2 Likes

@meooow , can you help me here - https://discuss.codechef.com/questions/98844/can-anyone-explain-the-problem-geometric-trick

@vijju123, done! :slight_smile:

2 Likes