You are not logged in. Please login at www.codechef.com to post your questions!

×

SSPLD- Editorial

PROBLEM LINK:

Div1
Practice

Setter-Trung Nguyen
Tester- Misha Chorniy
Editorialist- Abhishek Pandey

DIFFICULTY:

HARD

PRE-REQUISITES:

Fast Walsh Hadmard Transformation (Some knowledge about concepts of FFT etc. may aid in understanding), Dynamic Programming with Bitmasking

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][{2}^{d_i}]-Ans2[0][({2}^{d_i})\oplus ({2}^{0})])$

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-

for(int i=0;i< s;i++) Fast-Walsh Transform(A[i]); 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); lim>>=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<<0];//Separately for digit 0 for (int i=0; i<=9; i++) ans+=F[0][1<< i]-D[0][(1<< i)^(1<<0)];//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
Tester

$Setter$ $Solution's$ $Time$ $Complexity-$ $O(2^{10} * S * log(K) * (S + log(2^{10})))$
$Editorial$ $Solution's$ $Time$ $Complexity-$ $O({2}^{10}* {S}^{2} *LogK * log({2}^{10}) )$

CHEF VIJJU'S CORNER:

1. Add_Matrix function.

View Content

2. Multiply_Matrix Function

View Content

3. Another way of bypassing leading $0's$

View Content
This question is marked "community wiki".

asked 17 Apr, 03:37

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857
accept rate: 18%

edited 18 Apr, 17:04

admin's gravatar image

0★admin ♦♦
19.6k349497539


Actually, The complexity is $O(2^{10} * S * log(K) * (S + log(2^{10})))$.

link

answered 18 Apr, 12:33

chemthan's gravatar image

7★chemthan
1913
accept rate: 12%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,322
×331
×307
×194
×34
×34
×7

question asked: 17 Apr, 03:37

question was seen: 894 times

last updated: 18 Apr, 17:04