PROBLEM LINK:Author: Alexey Zayakin DIFFICULTY:EasyMedium PREREQUISITES:DP, bitmasks, longest increasing subsequence 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: 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".
asked 21 Jan '17, 20:41

@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

@Alex_2oo8 Can you please explain the above algorithm using an example to make it more understandable? answered 23 Jan '17, 10:02

would you expaint for what is your meaning to init state[][] answered 24 Jan '17, 16:13
