https://www.codechef.com/viewsolution/28721596

can u please help me to optimise my code?

Create transformation matrix for the given recurrence relation and then use matrix-exponentiation to find the n^{th} term.

Complexity: O(log_{2}n).

Thanks for reading.

Peace

3 Likes

can’t we optimise something in my code only?

Your code has **Linear Time Complexity**, and as the time limit is **1sec** and constraints is 1 \leq N \leq 10^{9}, you tell me how can you get and **AC** if you can’t reduce the time complexity, and the method which I have told you decreases that time complexity to O(8 \times log_{2}n) , so you should change your code completely.

Learn **Matrix Exponentiation Technique** as it helps in solving linear homogeneous recurrence relation with time complexity O(K^{3}log_{2}n) where K^{3} is because of time complexity of matrix multiplication i.e. O(n^{3}).

And you will encounter Linear Homogeneous Recurrence Relations in many problems in competitive programming.

**Try out yourself and if you don’t get an AC, you can refer to my solution which I will update soon.**

Thanks for reading.

Peace

3 Likes

@yatin_yk08 Here is the link to my solution: **Million Dollar Man Solution in C.**

**NOTE:** The constraints given in the problem statement are **Wrong** because when I put the condition on the values of **a, b** in the range 1 \leq a \leq 10^{9} and 1 \leq b \leq 10^{9} then my solution receives a verdict **WA.**

But when I change the constraints from 1 \leq a \leq 10^{9} and 1 \leq b \leq 10^{9} to 1 \leq a \leq 10^{18} and 1 \leq b \leq 10^{18} then my solution receives a verdict **AC.**

**Be careful about it.**

Thanks for reading.

Peace

1 Like

Btw there is also a closed form solution. sadly, there is some issue in test files due to which this submission gives wrong answer(proof).

1 Like

Can you write the close form solution here in latex? and will appreciate it if you can explain your the close form solution.

1 Like

ok ok

got it

thanks for the help

f(n) = \frac{(a + b) 4^{n - 1} + (b - 4a) (-1)^{n}}{5}

It can be arrived at by considering the characteristic equation of

f(n) = 3f(n-1)+4f(n-2)

which is

x^{n}=3x^{n-1}+4x^{n-2} -> \alpha = 4, \beta = -1.

Hence

f(n) = A\alpha^{n} + B\beta^{n}

A,B can be found by plugging n =1 and n = 2.

2 Likes