The Unlucky 13 (HackerEarth)

1

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.

1 Like
2

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.

3

Have u solved the question?

4

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}
5 Likes
5

Thanks buddy :blush:

6

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

7

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

8

Please explain. I am not able to understand.

9

@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 = singlesingle;
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();
}
}

4 Likes
10

@fub_123 If you want to learn more about matrix exponentiation, there’s a good series by errichto on youtube codechef’s DSA series also discusses the logic behind in for 15-20 mins I guess, and a question set on codeforces handling these questions, matrix exponentiation helps in scenarios where you want to find recursive solutions;( DP sometimes fails in those scenarios, you can check by simplest example if you want to find Nth Fibonacci number where N<=1e18.
PS: I am also not very well versed in this as well, as I’ve not come across these questions much.Thanks.

11

can somebody help me I didn’t quite get it?

12

Sorry but I still dont get it, could you tell what is this state n-1 to n thing

13

@lonely_coder12 Thank you very much bro, was stuck over this for hours. Just some corrections (probably typos) that I find in your solution:

  1. On the 2nd last line, it should be “S(n-1) to H(n)”, and not “S(n-1) to S(n)”
  2. H(1) = 9, and not 1.
    Please correct it so that others don’t get confused.
14

@aryan_zx Basically what we need to calculate is the total no of strings of size N with no “13” in it
= (total no of strings of size N with no “13” and which ends with 1) + (total no of strings of size N with no “13” and which doesn’t end with 1)
= H(n) + S(n)

Now, if we have H(n-1) and S(n-1), sum of which = total no of strings of size (N-1) with no “13” in it,
Now, if we want to calculate H(n), we can do it by extending the strings of size(N-1) with no “13” in it (i.e. n-1 to n) meaning H(n) = H(n-1) extended to H(n) + S(n-1) extended to S(n)

Extending H(n-1) to H(n) means adding one more integer to any of the strings counted in H(n-1) which would lie in H(n). Now since H(n) can’t end with ‘1’, so the number of choices we have for last place is 9.
No of extensions from H(n-1) to H(n) = H(n-1) * 9.
Similarly, you can do it for S(n-1) as well.

15

I tried this after coming up with an equation. It seems to work when n is a small number. But throws runtime error on submission.

It is written in Swift. But the code is easy to go through. Could anyone explain what could be going wrong here?

let num = Int(readLine()!) // Reading input from STDIN
if var t = num as? Int{
while(t > 0){
t = t - 1
let input = Int(readLine()!)
if let n = input as? Int{
var ans = getPowerOfTen(nu)
ans = ans - getPowerOfTen(n) * (n - 1)
print(ans % 1000000009)
}
}
}

// Did not import any libraries for calculating power

func getPowerOfTen(_ num: Int)->Int{
var ans = 1
var n = num
while(n > 0){
ans = ans * 10
n = n - 1
}
return ans
}

16