×

# DIGITLIS - Editorial

Author: Alexey Zayakin
Editorialist: Alexey Zayakin

Easy-Medium

# PROBLEM:

For an $n$-digit number $x$ we define the $LIS$ array as follows: $i$-th element of the array is the length of the longest strictly increasing subsequence of numbers $x$ digits that ends with the $i$-th digit.

Given the $LIS$ array of some $n$-digit number, find the count of different $n$-digit numbers that correspond to this $LIS$ array.

# QUICK EXPLANATION:

Use dynamic programming (add digits one by one). All the information we want to know about previous digits is for every length $len$ ― the smallest digit $d$ such that there exists a $LIS$ of length $len$ that ends with digit $d$.

# EXPLANATION:

Consider the algorithm of finding the longest increasing subsequence described in wikipedia. It processes the digits one by one and all the information stored about the processed digits is the array $M$. Here we will define the array $M$ to store the value $X[k]$ itself instead of the index $k$ as described in wikipedia.

The state of the above mentioned algorithm can be described with length of already processed prefix of digits and the array $M$. Let's try to figure out how big the array $M$ can be. It stores a strictly increasing sequence of digits. As we have only ten different digits, naturally its length cann't be greater than ten. Additionaly, given that array $M$ stores a strictly increasing sequence, all its elements are different and thus it can be threated as a subset of digits. This gives us a nice and convienient way to enumerate all the possible arrays $M$, as well as their total count is just $2^{10} = 1024$.

Now we will build a dynamic programming solution based on the above observations. The state of the DP will be pair $(pref, mask)$, where $pref$ is the length of already processed prefix of digits and $mask$ is a bitmask on ten bits that encodes the array $M$. The value of the DP will answer the question "How many different numbers of length $pref$ will generates an array $M$ that is encoded in $mask$ and have $LIS$ array equal to the one provided in the input?".

Now let's speak about the DP transitions. Any transition will be just one step of the algorithm, i.e. addition of one digit. So, for every state there will be ten different tansitions (using digits $0, 1, \dots, 9$). After fixing the digit we are going to add (denote it with $d$), as per the algorithm, we will search for the largest index $j$ such that $M[j] < d$. This gives us the information that the $LIS$ that ends with a newly added digit $d$ has length $(j + 1)$. Here we should check that this value matches with the one in the provided $LIS$ array (if it doesn't we just ignore this transition). Now we update the array $M$ with $M[j + 1] = d$ and process the transition:
$DP[pref + 1, newmask] \mathrel{+}= DP[pref, mask]$, where $newmask$ is the encoded version of the updated array $M$.

The last thing to discuss are the base/final states. Our DP has just one base state ― $DP[0, 0] = 1$, i.e. at the very beginning we have not processed any digits and the array $M$ is empty. The final states are just $DP[n, mask]$ for every $mask$, beacuse we actually do not care about the final array $M$, we just want for the $LIS$ arrays to match and this is guaranteed by skipping wrong transitions.

# Time Complexity:

$\mathcal{O}(2^B \cdot B \cdot n)$ per test case, where $B$ is the base of the numeral system we are working with. In this problem $B = 10$.

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

3841612
accept rate: 28%

19.8k350498541

 1 @Alex_2oo8 would you please tell me or give me any use case where i am going wrong with my dp Solution Link I didn't use bitmask . answered 23 Jan '17, 00:34 10●1●2●7 accept rate: 0% For example: "1 3 1 2 1", the correct answer is 156. (23 Jan '17, 01:16)
 1 @Alex_2oo8 Can you please explain the above algorithm using an example to make it more understandable? answered 23 Jan '17, 10:02 11●2 accept rate: 0%
 0 @Alex_2oo8 How is 1 3 1 2 1 a valid input? For example, at position 2 the LIS is 3, but before that we've only got just one number so the maximum LIS at position2 would be 2 answered 23 Jan '17, 14:50 11●1 accept rate: 0% The first number is the number of testcases (1), the second is the value of $n$ for the first testcase (3), three following numbers (1 2 1) describe the $LIS$ array. (23 Jan '17, 15:18)
 0 I can't understand how is array M being mapped to bitmask. The array M may contain integers from 0-9 .Can someone explain how is the mapping done in setter's solution. answered 23 Jan '17, 15:06 31●1 accept rate: 0% If the array $M$ has length $k$, i.e. the $LIS$ so far is $k$, then it is mapped to bitmask $\displaystyle 2^{M_1} + 2^{M_2} + \dots + 2^{M_k}$. (23 Jan '17, 15:21) Just to make things clear, when we are updating the array we have to set the bit corresponding to new digit?. (23 Jan '17, 15:57) If you update the array as $M[j] = d$, the you should set the bit corresponding to $d$ and unset the bit corresponding to the old value of $M[j]$ (in case there was an old value). (23 Jan '17, 16:24)
 0 I also hard to understand the editorial answered 24 Jan '17, 15:58 1 accept rate: 0%
 0 would you expaint for what is your meaning to init state[][] answered 24 Jan '17, 16:13 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,683
×1,672
×281
×52
×36
×2

question asked: 21 Jan '17, 20:41

question was seen: 1,913 times

last updated: 24 Jan '17, 16:13