GIOGIO - Editorial

PROBLEM LINK:

Contest

Author: vallabh43
Tester: rutuja2229

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Math, Recurrence

PROBLEM:

Solve the given recurrence relation.

QUICK EXPLANATION:

The constraints for the given problem are too large to solve it using recursion or O(n) DP. We have to solve it either by matrix exponentiation (O(logn) per test case) or by solving the recurrence and simply plugging in the value of n (O(1) per test case).

EXPLANATION:

I’ve shown 2 methods of solving the given problem. First let us look at the optimal solution i.e. solving the recurrence relation. I will solve the recurrence using its characteristic equation but you can solve it using any other method you find suitable.
The given recurrence relation is T_{n} = 3*T_{n-1} - 3*T_{n-2} + T_{n-3}.
Its characteristic equation is x^3-3*x^2+3*x-1=0. Notice that LHS is simply the expansion of (x-1)^3 which means the characteristic equation has repeated roots at x=1. Hence, the solution of this recurrence can be written in the form of T_n = a+b*n+c*n^2. Plugging in the values of n = 1, 2, 3 we get:
a+b+c=0
a+2*b+4*c=2
a+3*b+9*c=5

We now have 3 simultaneous linear equations in 3 variables. We can solve for a, b, c using Gaussian elimination.
\biggl(\begin{matrix} 1&1&1 \\ 1&2&4 \\ 1&3&9 \end{matrix} \biggr) \biggl(\begin{matrix} a \\ b \\ c \end{matrix} \biggr) = \biggl(\begin{matrix} 0 \\ 2 \\ 5 \end{matrix} \biggr)
After applying row transformations, we get,
\biggl(\begin{matrix} 1&1&1 \\ 0&1&3 \\ 0&0&2 \end{matrix} \biggr) \biggl(\begin{matrix} a \\ b \\ c \end{matrix} \biggr) = \biggl(\begin{matrix} 0 \\ 2 \\ 1 \end{matrix} \biggr)

Hence we get the solution c = ½, b = ½, a = -1.
Plugging in the values of a, b, c in T_n = a+b*n+c*n^2 gives us T_n = -1+(1/2)*n+(1/2)*n^2.
Rearranging the terms we get T_n = n*(n+1)/2 - 1.
We got the recurrence relation in closed form, we just need to apply MOD operation as asked in the problem.

O(1) solution
	#include<iostream>
	
	using namespace std;
	
	#define MOD 1000000007
	typedef long long ll;
	
	void solve(){
	    ll n;
	    cin>>n;
	    cout<<(((n*(n+1)/2)%MOD - 1)%MOD+MOD)%MOD<<"\n";
	}
	
	int main()
	{
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		int t = 1;
		cin>>t;
		while(t--){
	        solve();
		}
		return 0;
	}

The other solution is to use matrix exponentiation where we don’t need to solve the recurrence.
We have the equations:

T_{n} = 3*T_{n-1} - 3*T_{n-2} + T_{n-3}
T_{n-1} = 1*T_{n-1}+0*T_{n-2}+0*T_{n-3} (trivially)
T_{n-2} = 0*T_{n-1}+1*T_{n-2}+0*T_{n-3} (trivially)
\biggl(\begin{matrix} T_n \\ T_{n-1} \\ T_{n-2} \end{matrix} \biggr) = \biggl(\begin{matrix} 3&-3&1 \\ 1&0&0 \\ 0&1&0 \end{matrix} \biggr) \biggl(\begin{matrix} T_{n-1} \\ T_{n-2} \\ T_{n-3} \end{matrix} \biggr)

Applying the same procedure n-3 times gives:
\biggl(\begin{matrix} T_n \\ T_{n-1} \\ T_{n-2} \end{matrix} \biggr) = \biggl(\begin{matrix} 3&-3&1 \\ 1&0&0 \\ 0&1&0 \end{matrix} \biggr)^{n-3} \biggl(\begin{matrix} T_{3} \\ T_{2} \\ T_{1} \end{matrix} \biggr) = \biggl(\begin{matrix} 3&-3&1 \\ 1&0&0 \\ 0&1&0 \end{matrix} \biggr)^{n-3} \biggl(\begin{matrix} 5 \\ 2 \\ 0 \end{matrix} \biggr)

The matrix \biggl(\begin{matrix} 3&-3&1 \\ 1&0&0 \\ 0&1&0 \end{matrix} \biggr)^{n-3} can be computed in O(logn) time.

Alternate Solution
#include<bits/stdc++.h>

using namespace std;

#define MOD 1000000007
typedef long long ll;

template <typename T>
vector< vector< T > > matmul(const vector< vector< T > > &A, const vector< vector< T > > &B){
    ll n = A.size();
    vector< vector< T > > v(n, vector< T > (n));
    for(ll row = 0; row < n; ++row){
        for(ll column = 0; column < n; ++column){
                T dot = 0;
                for(ll element = 0; element < n; ++element){
                    dot += A[row][element] * B[element][column]%MOD;
                    dot %= MOD;
                }
                v[row][column] = dot;
        }
    }
    return v;
}

template <typename T>
vector< vector< T > > matexpo(const vector< vector< T > > &A, ll n){
    ll m = A.size();
    if(n <= 0){
        vector< vector< T > > v(m, vector< T > (m));
        for(ll i = 0; i < m; ++i) v[i][i] = 1;
        return v;
    }
    else{
        vector< vector< T > > t = matexpo(A, n >> 1);
        t = matmul(t, t);
        if(n&1) t = matmul(t, A);
        return t;
    }
}

void solve(){
    ll n;
    cin>>n;
    if(n <= 3){
        int ans[3] = {0, 2, 5};
        cout<<ans[n-1]<<"\n";
        return;
    }
    vector< vector< ll > > matrix = {{3, -3, 1}, {1, 0, 0}, {0, 1, 0}};
    matrix = matexpo(matrix, n-3);
    cout<<((5*matrix[0][0]%MOD+(2)*matrix[0][1]%MOD)%MOD + MOD)%MOD<<"\n";
}

void oJudge() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
#endif
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	oJudge();
	int t = 1;
	cin>>t;
	while(t--){
        solve();
	}
	return 0;
}

SOLUTIONS:

Setter's Solution

Refer the above 2 solutions

Time Complexity: O(t*1)

1 Like