WORKCHEF - Editorial

PROBLEM LINK:

Practice
Contest

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 :

x = p * lcm(a_1, a_2, \dots a_k) + q, \text{where } 0 \leq q < lcm(a_1, a_2, \dots a_k)
x \mod a_i = q \pmod a_i, \text{as } a_i \mid \text{lcm}(a_1, a_2, \dots a_k)

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.

Author’s and Tester’s Solutions:

Tester’s solution
Editorialist’s Solution

1 Like

@admin both setter and tester’s solution are not working :frowning:

One optimisation is to not consider 5 in as divisibility by 5 entirely depends on the last digit of number.

2 Likes

@dpraveen your code is giving TLE for last subtask :frowning:

1 Like

@admin Please fix the Editorialists code. The code is giving TLE

Could someone explain me how to calculate the time complexity of this algorithm.

Can anybody tell me the use of mask in the Editorialist’s Solution?.I am confused with the bit AND,OR operations in the dp function

Yes, I have the same doubt, Why did the dp state have a mask? What is its significance?(In Editorialist Solution)

just heed…

Tester solution is not mentioned why so please post it

Mask is for indicating the digits present in the number generated till now

1 Like

The Editorialist’s Solution solution is giving tle , why ?

It should be O(n) with a very large constant, n being the number of digits in the number.

Thanks @xariniov9 but how did you get it.

Observe the size of the dp array. The possible states are n * lcm * 2 * 2^9, which bounds the running time.

Apart from the n, all other factors are constant. You may want to prove it by yourself, but this simple observation can give the idea.

1 Like

Will someone explain this paragraph please…I am not understanding this editorial at all…either I am too noob in this or the editorial is not written well for all to understand.