PROBLEM LINK:
Author: Dymtro Berezein
Tester: Mugurel Ionut Andreica
Editorialist: Praveen Dhinwa
DIFFICULTY:
medium
PREREQUISITES:
maths, digit dp
PROBLEM:
A number X is said to be K-special if there exist K or more different digits, such that X is divisible by those digits and those digits are present in the decimal representation of the number. You have to find number of K special integers in the range from L to R.
EXPLANATION:
Observation
Let us say that we have a number x, we want to know divisibility of this number for some numbers a_1, a_2, \dots a_k. If you know the reminder of number x by lcm(a_1, a_2, \dots a_k), then can you find its reminder for each of the a_1, a_2, \dots a_k?
Answer is yes. Observe that you can write any number x as :
LCM of all the numbers from 2 to 9 will be equal to 2^3 * 3^2 * 5 * 7 = 2520. So, we know the reminder of number modulo 2520, we can find its reminder by each of the numbers from 2 to 9.
Back to the problem
In counting problems that ask some quantity in a range [L, R], it is beneficial to ask yourself whether knowing how to compute answer for some range [0, n] will help you or not?
For example, in this problem we want to find number of K special numbers in range [L, R]. If we know the number of K special numbers from 0 to R and from 0 to L-1, then we can easily find the number of K special numbers in range [L, R].
Now, let us solve the problem of finding number of K special numbers from 0 to n for some n. For the largest subtask, value of n can go as large as 10^18, so iterating over the range will be too costly for us. In such problems, we should try whether we can apply a digit dp algorithm or not. In digit dp, we represent number n in some base, for our problem we will have decimal base. We iterate over the digits of number n in base 10 and try to extend the number created till now. let us identify the necessary information for us to store in the state of the dp. We should know the following information.
- The current digit at which we currently are, let us denote it by index.
- We will also need to the number generated till now has already become strictly less than first index - 1 digits of number n, or is equal to that. Let us denote this by a binary variable tight. If tight = 1, then it will denote that currently generated number is equal to number generated by the prefix of length index - 1 digits of n. The condition tight = 0 will denote the number generated has already become less than number generated by prefix.
- Now, let us understand how can we maintain the necessary information to check whether the number generated in the end will be divisible by at least K digits or not. As we are working in base 10, the maximum digit can go up to 9, we have to check divisibility of a number by 1, 2, \dots 9. We can not afford to keep reminder of number generated till now by all the numbers from 2 to 9. We should devise a slightly faster method. From the previous observation, we can notice that we just have to keep reminders by their LCM (i.e. 2520). So, we will also store a number rem denoting the reminder of the number modulo L = 2520.
Time limit of the problem is tight and you should do some constant optimization in your code. You can store the all the new reminders which you will get for a fixed reminder and a fixed next digit to come. This will save you a lot of unnecessary modulo operations. Also, if you are writing an iterative code, you should also break out from impossible situations as soon as possible. For that, you might need to change the order of the state variables.
