The Unlucky 13 (HackerEarth)

Please Help me in solving The Unlucky 13 question on the link I provided.I am thinking it in terms of recursion but the value of n is huge to memoize the solution.

Seems like a simple PnC problem. Example for 2 : 10c1*10c1 - 1 = 99. Will ping you after I code this up.
PS: Calculation doesn’t seem to be easy. Gotta find a way make it simpler.

Have u solved the question?

Do you know matrix multiplication?

Let dp_{i,j} be the number of valid strings of length i such that the last character is j.

We can notice dp_{i,j} = \sum dp_{i-1,k} where k sums over all the numbers from 0 to 9.
The only special case is j=3, in which case k does not contain 1.

Now we can notice that dp_{i,j} is equal for all j!=3.

So let dp_{i,0} be the value of dp_{i,j} for j!=3, and dp_{i,1} as the number of strings with length one that end with 3(dp_{i,3}).

Now using our redefined states,

dp_{i,0} = 9\times dp_{i-1,0} + dp_{i-1,1}
dp_{i,1} = 8\times dp_{i-1,0} + dp_{i-1,1}.

Now this can be computed with basic matrix exponentiation.

matrix
\begin{bmatrix} 1 & 1 \end{bmatrix}\times \begin{bmatrix} 9 & 8 \\ 1 & 1 \end{bmatrix}^{n-1}

Thanks buddy

Can u plz suggest some good resources to learn where to apply matrix exponentiation.

Yes I also want it. If you get it. Plz send me too. Thnx in advance.

Please explain. I am not able to understand.

@shobhit01
For large N such recurrences can be solved using Matrix Exponentiation. Let us denote characters ending with {0,2,3,4,5,6,7,8,9} as happy states (H) and character ending with {1} as sad(S).
For the number to be valid, we don’t want a 3 after the sad state i.e. after {1}. Let the current states be H(n-1) and S(n-1). There are 9 ways to transition from H(n-1) to H(n) (i.e.{0,2,3,4,5,6,7,8,9}) and 8(i.e.{0,2,4,5,6,7,8,9}) ways to transition from S(n-1) to S(n). There is only 1(i.e.{1}) way to transition from H(n-1) to S(n) and 1(i.e.{1}) way to transition from S(n-1) to S(n).
So we get something like :
9 H(n-1) + 8 S(n-1) = H(n)
1 H(n-1) + 1 S(n-1) = S(n) , S(1) = H(1) = 1

So [[9 8] * [H(n-1)]= [H(n)]
[1 1]] * [S(n-1)]= [S(n)]

This is a basic matrix exponentiation with can be done in log(n). So the overall complexity is (M^3 * log(n)) where M is size of matrix(here it is 2).

Here is the code for reference.

#include<bits/stdc++.h>

#define ll long long
#define rep(i,k) for (int i = 0 ; i<k ; i++)

using namespace std;

ll n;

const int mod = 1e9+9;

struct Matrix{
vector<vector>a = vector<vector>(2,vector(2,0));
Matrix operator*(const Matrix& other){
Matrix res;
rep(i,2){
rep(j,2){
rep(k,2){
res.a[i][k] += a[i][j] * other.a[j][k];
res.a[i][k] %= mod;
}
}
}
return res;
}
};

Matrix expo_power(Matrix single,ll p){
Matrix id;
rep(i,2)id.a[i][i] = 1;
while (p>0){
if (p & 1)id = idsingle;
single = single
single;
p = p>>1;
}
return id;
}
void solve(){
cin>>n;
Matrix single;
single.a[0][0] = 9;
single.a[0][1] = 1;
single.a[1][0] = 8;
single.a[1][1] = 1;

Matrix ans = expo_power(single,n);
cout<<(ans.a[0][0] + ans.a[0][1])%mod<<endl;


}

int main(){
int t;
cin>>t;
while (t–){
solve();
}
}

1 Like