SSPLD- Editorial
#PROBLEM LINK:
[Div1][1]
[Practice][2]
**Setter-**[Trung Nguyen][3]
**Tester-** [Misha Chorniy][4]
**Editorialist-** [Abhishek Pandey][5]
#DIFFICULTY:
HARD
#PRE-REQUISITES:
[Fast Walsh Hadmard Transformation][6] (Some knowledge about concepts of FFT etc. may aid in understanding), [Dynamic Programming with Bitmasking][7]
This editorial will assume you have a knowledge of the pre-requisites.
#PROBLEM:
You are to count number of "$S$ Semi Palindromic" numbers which are less than ${10}^{K}$. A non-negative number is called $S$ Semi Palindrome if its digits can be re-arranged to give a palindromic number.
#QUICK EXPLANATION:
Let $A[i][mask]$ be the matrix of transition where $i$ represents the remainder $\%S$ and $mask$ represent a $XOR-SUM$ of digits as- $XorSum={2}^{d_0}\oplus{2}^{d_1}.....\oplus{2}^{d_k}$. Our answer is $\sum_{i=1}^{K} {A}^{i}$ $-$ but it will count leading zeroes! However, we can easily remove count of leading zeroes if we also store the state $\sum_{i=1}^{K-1} {A}^{i}$. Say matrices $Ans1[][]=\sum_{i=1}^{K} {A}^{i}$ and $Ans2[][]=\sum_{i=1}^{i=K-1} {A}^{i}$. Our final answer will be $(Ans=\sum_{d_i=0}^{9}Ans1[0][1<< d_i]-Ans2[0][(1<< d_i)\oplus 1])$
#EXPLANATION:
First, lets make a transition matrix, which is initially initialized to hold answer for $K=1$ (i.e. single digit numbers). Hence, the initial state of our transition matrix is-
`for (int i=0; i<10; i++)
A[i%s][1<< i]=1;`
The meaning of $A[i][mask]$ is **All numbers, which leave a remainder i when $\%S$ and have the given mask**. Note that, mask here is calculated by $Mask={2}^{d_0}\oplus{2}^{d_1}.....\oplus{2}^{d_k}$. This helps in easy semi-palindrome detection, as digits can have values only from $0-9$ and if he do a $xor$ of $\large {2}^{d_i}$, then a semi-palindrome must have mask which is either a power of $2$ , or $0$. Power of $2$ represents a single digit occurring odd number of times (middle digit) while rest occurs even number of times, and a $0$ represents that every digit occurs in multiples of $2$ which makes it possible to re-arrange the number to make it a palindrome.
Our $A[][]$ holds answer for $K=1$ currently. To answer the query, we need $\sum_{i=1}^{K} {A}^{i}$ where ${A}^{i}$ will store answer for numbers of length $i$. This process will also, however, count numbers with leading $0s$ which is undesirable. To compensate for that, we will need the state value of $\sum_{i=1}^{K-1} {A}^{i}$.
But how to find these in first place?
We will be using two tricks.
The first one is Fast Walsh Hadmard Transformation of our transformation matrix $A$ , so that we can compute things faster.
The second one is how we will calculate the polynomials.
Say we have the following values-
- Matrix $T$=$\sum_{i=1}^{P} {A}^{i}$
- Matrix $U$=${A}^{P}$
We need to find $\sum_{i=1}^{2P} {A}^{i}$ from it. What to do?
It turns out to be pretty simple!
We can reformulate $({A}^{2p}+{A}^{2P-1}....{A}^{P+1})+{A}^{P}.....+A$ as-
${A}^{P}({A}^{P}+{A}^{P-1}+....+A)+{A}^{P}+{A}^{P-1}+.....+A$
Which is equivalent to, in terms of our matrices, $UT+T$.
Now, remember that we need $\sum_{i=1}^{K} {A}^{i}$ AND $\sum_{i=1}^{K-1} {A}^{i}$. Hence, lets find upto $\sum_{i=1}^{K-1} {A}^{i}$ using the above logarithmic method. The answer for $\sum_{i=1}^{K} {A}^{i}$ can be easily obtained by multiplying with, and adding $A$ once more to $\sum_{i=1}^{K-1} {A}^{i}$.
Suppose matrix $B$ holds the value of ${A}^{K}$ (equivalent to matrix $U$ of my example.)
, matrix $D$ stores values of answering summation, and matrix $A$ holds the value of polynomial, (equivalent to matrix $T$ of my example).
So, our code should look somewhat like this-
Suppose matrix $B$ holds the value of ${A}^{K}$ (equivalent to matrix $U$ of my example.)
, matrix $D$ stores values of answering summation, and matrix $A$ holds the value of polynomial, (equivalent to matrix $T$ of my example).
` Fast-Walsh Transform(A);
int lim=k-1;
while (lim) {
if (lim&1)
{
Multiply_Matrices(D, B, s, r); //s passed to calculate %s
Add_Matrices(D, A, s);
}
for (int i=0; i<s; i++)
for (int j=0; j<N; j++)
Duplicate[i][j]=A[i][j];
Multiply_Matrices(A, B, s, r); //r is needed in multiplication process. Explained in bonus section.
Add_Matrices(A, Duplicate, s);
Multiply_Matrices(B, B, s, r);
k>>=1;
r<<=1;
}`
We are almost done!
We have the answer of $\sum_{i=1}^{K-1} {A}^{i}$ stored in matrix $D$. Lets make another matrix $F$ to store the answer for $\sum_{i=1}^{K} {A}^{i}$. Any guesses about $F$ till now?
`A=Restore_Original(A);//The transition matrix which stored answer for K=1 length.
FWT_Transform_Matrix(A);
Multiply_Matrices(D, A, F, s, r);//Multiply D and A, store in F.
Add_Matrices(F, A, s);`
We are just two steps away from the final answer!
Our first task is to reverse the transformation which we did for faster multiplication and computation of required answer. We have $D=\sum_{i=1}^{K-1} FWT({A}^{i})$ and $F=\sum_{i=1}^{K} FWT({A}^{i})$.
Our next step is to calculate the inverse of this FWT transformation. Once we calculate the inverse, our answer will be of form-
` ans=f[0][0]-d[0][1];//Separately for digit 0
for (int i=0; i<=9; i++)
ans+=F[0][1<< i]-D[0][(1<< i)^1];//For rest of digits from '1'-'9' `
Recall that $mask$ must be either $0$ or a ${2}^{i}$. Now, why `F[0][1<< i]-D[0][(1<< i)^1]` ? The exact reasoning will be clear only when you get acquainted with transition matrices- but I can try giving an intuition on why its right.
We know that matrix $D$ has answer till length $K-1$. One interpretation goes this way. In numbers of length $K-1$ we have some unpaired number (as ${2}^{i}$) and another unpaired $0$. When we added another digit at $MSB$ to get the ans for numbers till length $K$, the $0$ got paired. So naturally, what will that number be? (Please see, this isnt intended to be an "Absolute Mathematical Reasoning" but merely a rough intuition to kind of help get the logic. People are always advised to explore the topic and get the real mathematical reasoning).
The exact definition of functions `Multiply_Matrix, Add_Matrix` and another way of dealing with number of leading zeroes is discussed in bonus section.
#SOLUTION:
[Setter][8]
[Tester][9]
#CHEF VIJJU'S CORNER:
**1.** **Add_Matrix function.**
[hide]
`void add(int A[16][N], int B[16][N], int s) //Take matrix A, B. Store result in matrix A.
{
for (int i=0; i< s; i++)
for (int j=0; j< N; j++) //N=1024
(A[i][j]+=B[i][j])%=MOD;//Simple addition
}`
[/hide]
**2.** **Multiply_Matrix Function**
[hide]
`void mul(int A[16][N], int B[16][N], int C[16][N], int s, long long f) {
int mid=power(10, f, s);//10^r. At one step, we are directly jumping from 10^2 to 10^4 to 10^8 &etc.
for (int i=0; i< s; i++)
for (int j=0; j< N; j++) //N=1024
c[i][j]=0;//This will store the values temporarily.
for (int i=0; i< s; i++)
for (int j=0; j< s; j++)
{
int u=(i*mid+j)%s;//Remainder. Remember, expression's form is
//A^K(A^K+A^(K-1)...+A)+A^K+A^(K-1)....+A. Hence, remainder is also of form i*10^f +j.
for (int k=0; k< N; k++)
c[u][k]+=(long long )A[i][k]*B[j][k]%MOD;
}
for (int i=0; i< s; i++)
for (int j=0; j< N; j++)
C[i][j]=c[i][j]%MOD;//Store value in matrix C finally.
}
`
[/hide]
**3.** Another way of bypassing leading $0's$
[hide]
Let, $DP0[k][i][j]$ be equal to the count of $K-length$ numbers which are give remainder $i$ by modulo $S$ and $j$ is mask of those digits as we calculated for this question.
Then, let, $DP1[k][i][j]$ - count of $K-length$ numbers which are give remainder $i$ by modulo $S$ and $j$ is mask of those digits, and they don't start by $0$
Let's see the state transitions:
$DP0[0][0][0] = 1$
$DP0[k][i][j] \implies DP0[k+1][(10^k*i+d)%s][j \oplus {2}^{d}]$, **d = 0..9 (transitions A)**
$DP1[k][i][j] \implies DP1[k+1][(10^k*i+d)%s][j \oplus {2}^{d}]$, **d = 1..9 (transitions B)**
The result is:
`SUM i = 1..K
ans += DP1[i][0][0]
SUM d = 0..9
ans += DP1[i][0][1<< d]`
We can use something like the matrix multiplication for finding the answer:
If we know transitions $A$ and we know transitions $B$:
Let $A$ is matrix of transitions: $ A[i % s][1<< i] = 1, i = 0..9$
Let $B$ is matrix of transitions: $ B[i % s][1<< i] = 1, i = 1..9$
$(i, j) -> ((10^k*i+d)%s, j \oplus {2}^{d})$ and we know ${10}^{k}$ before hand. $d=1..9$(for $B$), $d =0..9$( for $A$)
FIXED length of left size = ${10}^{k}$, define operation multiplying
$(i1, j1) * (i2, j2) \implies ((i1 * 10^k + i2) % s, (j1 \oplus j2))$
We can use something like binary exponentiation next. So,
$DP0[i]=A*DP0[i-1]$, and we know ${10}^{(i-1)}$
$DP1[i]=B*DP0[i-1]$
Let's calculate the sum over all values $RES[i][j] = \sum_{i=1}^{K}DP1[i][j]$
$RES = B*{A}^{(K-1)}+B*{A}^{(K-2)}+...+B$(with define operations $+$ and $*$, i.e we need to know $K$ and count of $k-length$ numbers and their $XOR$)
*
`for i = 0..S-1
for j = 0..S-1
for ii = 0..(1<<10)-1
for jj = 0..(1<<10)-1
RES[(i*10^leftBlockSize+j)%s][ii ^ jj] += A[i][ii] * B[j][jj]
RES[(i*10^leftBlockSize+j)%s][ii ^ jj] %= MOD`
$Time$ $Complexity=O({S}^{2}*{2}^{20})$
It can be boosted with FWT to achieve a complexity of $O({S}^{2}*{2}^{10}*{10})$
[/hide]
[1]: https://www.codechef.com/APRIL18A/problems/SSPLD
[2]: https://www.codechef.com/problems/SSPLD
[3]: https://www.codechef.com/users/chemthan
[4]: https://www.codechef.com/users/mgch
[5]: https://www.codechef.com/users/vijju123
[6]: https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it
[7]: https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/tutorial/
[8]: http://campus.codechef.com/APR18TST/viewsolution/18028799/
[9]: http://campus.codechef.com/APR18TST/viewsolution/18049001/