TILDOM - Editorial

PROBLEM LINK:

Contest
Practice

Author: vallabh43
Tester: rutuja2229

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

DP, Math, Linear Algebra

PROBLEM:

Find the number of ways to tile a 1 X N checkers board with infinite supply of 1 X 1 dominos of 3 colours and 1 X 2 dominos of 2 colours.

QUICK EXPLANATION:

The recurrence relation that counts the number of ways in this problem can be given by T_n = 3*T_{n-1}+2*T_{n-2}. Looking at the given constraints we must use matrix exponentiation to calculate the required answer.

EXPLANATION:

Consider that we know the number of ways to tile the checkers board of dimensions upto 1 X N-1. Now how do we calculate the number of ways to tile 1 X N checkers board using the previous values?

To arrive at the solution of 1 X N checkers board, we can either take the 1 X N-1 board and place one of the three - red, green, blue dominos on it or we can take the 1 X N-2 board and place one of the two - white, black dominos on it. This suggests that the required numeric value can be calculated by the recurrence T_n = 3*T_{n-1}+2*T_{n-2}. We can find values of T_0 and T_1 as T_0 = 1 and T_1 = 3 respectively, as for n = 0, empty board is the only possible configuration and for n = 1, red, green, blue are the three possible configurations.

Scoring 20 points is easy, just define a recursive function for the above recurrence relation.

20 points solution
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define MOD 1000000007

ll tiling(ll n){
    if(n == 0) return 1;
    else if(n == 1) return 3;
    else return (3*tiling(n-1)%MOD + 2*tiling(n-2)%MOD)%MOD;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<tiling(n)<<"\n";
    }
    return 0;
}

Scoring 50 points requires you to store all the previously calculated values in an array to avoid wasting time on recalculations.

50 points Solution
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define MOD 1000000007

int main()
{
    const ll N = 100000;
    ll a[N + 1] = {0};
    a[0] = 1;
    a[1] = 3;
    for(ll i = 2; i <= N; ++i) a[i] = (3*a[i-1]%MOD + 2*a[i-2]%MOD)%MOD;
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<a[n]<<"\n";
    }
    return 0;
}

By looking at the constraints we can conclude that the previous solution will give RunTime Error as N can be as large as 10^{17} and we cannot store that many integers in an array. So somehow, we need to calculate the answer for each test case separately without having to store all the answers in an array. The way to do this is by Matrix exponentiation.
We have the equations:

T_n = 3*T_{n-1}+2*T_{n-2} and
T_{n-1} = 1*T_{n-1}+0*T_{n-2} (trivially)

We can write these in the matrix form as:

\bigl(\begin{matrix} T_n \\ T_{n-1} \end{matrix} \bigr) = \bigl(\begin{matrix} 3&2 \\ 1&0 \end{matrix} \bigr) \bigl(\begin{matrix} T_{n-1} \\ T_{n-2} \end{matrix} \bigr)

Applying the same procedure n-1 times gives:

\bigl(\begin{matrix} T_n \\ T_{n-1} \end{matrix} \bigr) = \bigl(\begin{matrix} 3&2 \\ 1&0 \end{matrix} \bigr)^{n-1} \bigl(\begin{matrix} T_{1} \\ T_{0} \end{matrix} \bigr) = \bigl(\begin{matrix} 3&2 \\ 1&0 \end{matrix} \bigr)^{n-1} \bigl(\begin{matrix} 3 \\ 1 \end{matrix} \bigr)

The matrix \bigl(\begin{smallmatrix} 3&2 \\ 1&0 \end{smallmatrix} \bigr)^{n-1} can be calculated in O(log(n)) using binary exponentiation.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define MOD 1000000007


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;
    }
}

int main()
{

    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        const vector< vector< ll > > matrix = {{3, 2}, {1, 0}};
        vector< vector< ll > > solution = matexpo(matrix, n-1);
        cout<<(3*solution[0][0]%MOD + solution[0][1])%MOD<<"\n";
    }
    return 0;
}

Time Complexity: O(t*log(n))

1 Like