Million Dollar Man

general
1

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

can u please help me to optimise my code?

2

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 :v:

3 Likes
3

can’t we optimise something in my code only?

4

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 :v:

3 Likes
5

@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 :v:

1 Like
6

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
7

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
8

ok ok
got it
thanks for the help

9

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