Problem Link :
Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu
Difficulty :
Easy-medium
Pre-requisite
Matrix multiplication, Modular matrix exponentiationProblem :
Given a recurrence relation of the form
T(n) = aT(n-1) + bT(n-2) + c*T(n-3) +d;
Find the nth term.
Explanation
The solution has many approaches but given the high constraints, most trivial ones will fail. Still,
lets take a look at them.
approach 1
Simple recursion -
Here, simply use recursion to find the value of previous terms.
int result=0;
//let t1, t2 and t3 are first three terms of recurrence
int T(n)
{
if(n==1)
return t1;
if(n==2)
return t2;
if(n==3)
return t3;
result + = (a*T(n-1))%MOD;
result%=MOD;
result + = (b*T(n-2))%MOD;
result%=MOD;
result + = (c*T(n-3))%MOD;
result%=MOD;
result + = d;
result%=MOD;
return result;
}
This solution will fail as it has too many overlapping sub problems and calling them will take
too much stack memory causing memory overflow.
approach 2
We can simply create an array to store the result of successive terms and use them to derive
the next ones. This approach will take a fixed amount of memory (i.e. the given array size).
int arr[1000000]={0};
arr[0]=0;
arr[1]=t1;
arr[2]=t2;
arr[3]=t3;
for(i=4;i<1000000;i++)
{
int result=0;
result + = (a*arr[i-3])%MOD;
result%=MOD;
result + = (b*arr[i-2])%MOD;
result%=MOD;
result + = (c*arr[i-1])%MOD;
result%=MOD;
result + = d;
result%=MOD;
return result;
}
This approach will fail as the value of n is upto 10^9 and this will cause memory overflow. But this
approach will give answer for more terms then the recursion approach.
N.B. This approach can be modified a little bit so that there is no requirement of an array. This will
give the required result in linear time (for all values of n) but will fail to pass within time limits.
Check this solution for more details.(This approach will take a lot of time (about a minute for our test case) and will fail)
Approach 3 : Matrix exponentiation :
The given recurrence relation is
T(n) = aT(n-1) + bT(n-2) + c*T(n-3) +d;
What if we write it as
M is a matrix derived later
So now we can solve the problem by finding M^(n-3) and multiplying it with the initial given
terms. The first row of the multiplication result matrix is our answer.
Now the problen reduces to finding the value of the matrix M. Since we are finding M^(n-3), it
means the matrix must be square, otherwise the multiplication of n matrices will not be possible.
Also, we are multiplying the matrix with the initial condition matrix of size 4 X 1. This
multiplication is possible if the matrix M^(n-3) has 4 columns (Matrix multiplication property).
So M is a 4 X 4 matrix.
Multiplying the matrices, we get
a1 * T(n) + a2 * (T(n-1) + a3 * (T(n-2)) +a4 * d = T(n+1)
b1 * T(n) + b2 * (T(n-1) + b3 * (T(n-2)) +b4 * d = T(n)
c1 * T(n) + c2 * (T(n-1) + c3 * (T(n-2)) +c4 * d = T(n-1)
d1 * T(n) + d2 * (T(n-1) + d3 * (T(n-2)) +d4 * d = d
Equating the terms, we get,
a1=a
b1=1
a2=b
b2=0
a3=c
b3=0
a4=1
b4=0
c1=0
c2=1
c3=0
c4=0
d1=0
d2=0
d3=0
d4=1
So the required transformation matrix is :
| a b c 1 |
| 1 0 0 0 |
| 0 1 0 0 |
| 0 0 0 1 |
The matrix multiplication has complexity O(K^3) and we can find the power of the matrix in
O(logn) using modular exponentiation. So, overall complexity of the algorithm is O(K^3 log n)
where K is the size (number of rows or columns) in the transformation matrix and n is the nth term.
For our program, k=4. So overall complexity is O(64*logn).
Check setter solution for implementations.
N.B. If any other method is there for the problem, please share in the comments.