DIGITLIS - Editorial

PROBLEM LINK:

Contest
Practice

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

1 Like

@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 .

1 Like

@Alex_2oo8 Can you please explain the above algorithm using an example to make it more understandable?

1 Like

@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

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.

I also hard to understand the editorial

would you expaint for what is your meaning to init state[][]

For example: “1 3 1 2 1”, the correct answer is 156.

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.

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}.

Just to make things clear, when we are updating the array we have to set the bit corresponding to new digit?.

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).