CR191 - Editorial

editorial
, , , ,
1

Problem Link:

Contest
Practice

Author: Saurabh Kumar
Tester: Shivam Garg and Mohammad Aquib
Editorialist: Saurabh Kumar

Difficulty:

Easy, Easy-Medium

Prerequisites:

Digit-DP

Problem:

A special Number is defined as a number made of sequence of strictly increasing and decreasing sequences of digits (1<=digits<=9). E.g. 12539752 ({1, 2, 5}, {5, 3}, {3, 9}, {9, 7, 5 2}). Now given an array A of size M, an integer K and a range L and R, we have to output the count of special numbers in the given range satisfying the following two conditions:-

  1. The maximum length of increasing or decreasing sequence has to be less than or equal to K.
  2. The special numbers can contain any digit (1<=digit<=9) any number of time but the given M digits in the array A must occur at least once.

Quick Explanation:

This is a digit-dp problem. The states of dp are- length of the current number, the previous digit which was used, size of the current increasing/decreasing sequence, whether the current number being formed is constrained or not, whether we are currently forming an increasing or decreasing sequence and the current mask which will be used to check which digits were used in forming the current number.
It becomes dp[index][prev][k][constraint][increasing][curMask] i.e. dp[20][10][10][2][2][520].

Some of the points to note:-

  1. The numbers can be made of digits 1 to 9, i.e. 0 is not included in the number.
  2. The special number with K = 1, i.e. numbers in which the maximum length of increasing or decreasing sequence is 1 can only include numbers between 1 to 9.

Explanation:

For those who already know the basic of digit-dp can skip this part and can go to the next part.

The first approach that comes to the mid after reading the problem statement is that we can run a loop i from L to R and for each i we can check whether that number follows the condition or not. The worst case complexity would be O(lengthOfNumber * (R - L + 1)). Seeing the constraint we know that this would not work and we need something extra and so comes the dynamic programming part.

In digit-dp we consider each number as a sequence of digits. In the beginning there is no digit and in each recursion we add 1 digit to the end of the number. For example to make the number 123, in the first recursion call we will add digit 1, in the next digit 2 and so on. And at each recursion call some conditions have to be satisfied based on what is asked in the question.
One other important thing to note in digit-dp is that to count something in the range L and R, we first calculate from 0 to R and then from that subtract 0 to L-1, this gives us the count in the range L to R. Now, suppose R is given as 1234 and to make sure that we are only calculating the numbers from 0 to 1234, i.e. we are not going more than R, we use the states, index (or current_length) and constraint in the function call. Index makes sure that we do not go for numbers which has more than length 4. Constraint is used in the case when we have added 1 and then 2 and currently our function is constrained as at this particular iteration we can only add numbers from 0 to 3. If we go above 3 then the number formed would be more than or equal to 1240 which is more than 1234. Thus constraint is used while maintaining the exact upper limit.

Now coming to this particular question.

The different states of the function calls are-
index - denotes the length of the current number
prev - This denotes the last digit which was last added. This will be used so that we could make strictly increasing or decreasing sequences. For example if prev = 3, then while making increasing sequence we iterate from 4 to 9.
k - This will tell us the length of the current increasing or decreasing sequence. It will be used to make sure that our length of the sequence does not exceed the given K (condition 1 of the problem).
constraint - This is used to make sure whether the current number is constrained or not (explained above).
increasing - If this value is 1 then it will denote that we are making increasing sequence, if 0 then decreasing.
curMask - This is used to know what different digits are used in the particular number. According to condition 2 of the problem, M given digits have to be used at least once. Whenever we add some particular digit we will set the bit at that particular index in mask. As the value of array A can be between 1 and 9 we can use 2^{10}-1 as a mask to represent all the different combinations. For example suppose we have used 1, 5 and 6 while making some number, so in the curMask the value would be 100011000.

Our function becomes:-

long long int solve(int ind, int prev, int k, int increasing, int constraint, int curMask)

Now, suppose we have added some digits and have reached some particular index ind. If at this point we want to add some digits greater than previous digit then we iterate from prev + 1 to 9, and we check that if we were previously forming increasing sequence then the length of this particular sequence would be increased by 1, i.e., k+1 and if we were previously forming a decreasing sequence then the length of current sequence would be 2. We also update the current mask by taking OR with 2^{i-1}.

for(int i=prev+1; i<=9; i++)
	if((!increasing && 2 <= K)|| (increasing && k+1 <= K))
	{
		ans += solve(ind+1, i, (increasing)?k+1:2, 1, 0, curMask|(1<<(i-1)));
	}

Similarly, for making decreasing sequence:-

for(int i=prev-1; i>=1; i--)
	if((increasing && 2 <= K) || (!increasing && k+1 <= K))
	{
		ans += solve(ind+1, i, (increasing)?2:k+1, 0, 0, curMask|(1<<(i-1)));
	}

The above two loops were for the time when it was not constrained (i.e. constraint = 0 in the function). The following code snippet shows the loops when constraint is 1. Almost all the things are same, only one more condition is added which checks whether the current digit added is equal to the digit at index ind in the upper bound or not. When the upper bound in 1234, the vector v contains (1, 2, 3, 4), which is used to check the above condition.

for(int i=prev+1; i<=v[ind]; i++)
	if((increasing && (k+1 <= K)) || (!increasing && 2 <= K))
	{	
		ans += solve(ind+1, i, (increasing)?k+1:2, 1, (v[ind] == i)?1:0, curMask|(1<<(i-1)));
	}

for(int i=min(prev-1, v[ind]); i>=1; i--)
	if((increasing && 2 <= K)|| (!increasing && k+1 <= K))
	{
		ans += solve(ind+1, i, (increasing)?2:k+1, 0, (v[ind] == i)?1:0, curMask|(1<<(i-1)));
	}

To make sure that the given M digits occur at least once in the number, we calculate the mask value by taking the OR with 2^{A[i] - 1} for all i 1 to M. when we reach the base condition of our solve function we take the AND of curMask with mask and if the value equals the value of mask then that means all the M digits have occurred at least once and we return 1 otherwise 0.

Time Complexity of our solution becomes O(20*10*10*2*2*520) which equals about 4*10^6.
Author and Editorialist’s Solution can be found here.
Feel free to give your suggestions and feedbacks, they are always welcome. :slight_smile:

Other Similar Questions:-
Chef and Digits
Logan and DIGIT IMMUNE numbers
Sum of Digits

2 Likes