PROBLEM LINK:
Author: Alexey Zayakin
Testers: Hasan Jaddouh
Editorialist: Alexey Zayakin
DIFFICULTY:
Easy-Medium
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:
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.