Can someone share their approach for the problem CHEFSPCL in July LOC competitive programming marathon?
My solution was slightly different than others.
I used digit DP for 2,4, 5 and 6, and brute force for 3 and 7.
2: You can only use digits 1,3,5,7 to make the number.
3: As divisibility criteria is sum of digits, we have to make sure we don’t repeat the same value of prefix[i]%3. If so, this number is not valid. Using PHP, it can be proven such numbers are < 100.
4: Digit DP with extra state for previous digit. We cant use some digit x if (previous*10+x) is divisible by 4.
5: Can’t use 0 or 5.
6: Digit DP with extra state for value of prefix sum %3 done. Whenever you add an even digit, check the prefix value%3 doesn’t get repeated.
7: One of the little known divisibility criteria is multiplying face value by 1,3,2,-1,-3,-2 cyclically. This can be exploited as due to PHP again, the number must be < 10^6. [More][1](see the “Finding remainder of a number when divided by 7” section).
[2]
[1]: https://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_7
[2]: https://www.codechef.com/viewsolution/10980869
2 Likes
This can be solved by using Digit-DP. If you haven’t heard of it before, I suggest you read this [post][1].
We can see that number of special numbers in range [L,R] is simply the difference of counts of special numbers in range [0,R] and range [0,L-1].
Now to count the number of special numbers in range [0,N] we use digit-DP.
The essence of digit-DP lies in generating numbers digit by digit from the MSB to LSB.
So the states in our DP would be defined by -
-
len - The length of number generated till now.
-
tight - We need to know whether the number generated until now is lesser or equal to the number formed by the first len digits of N. tight=1 denotes that it is equal and tight=0 denotes it is strictly lesser. So if tight is 0, then the number has already become lesser than N and all digits 0 to 9 are eligible to be the next digit in the number to be generated. But, if tight is 1, then only digits 0 to digit at pos len in N are eligible to be the next digit in the number being generated.
-
mod_bitmask - We have to ensure that no substring of the number being generated is divisible by K. While adding a new digit to the right of the number being generated, let’s say we have all the remainders R (dividing by K) of the substrings ending at pos len. So, a new digit d can be added only if (10r+d)%K is not 0 for every r in R. As there can only be K different values for the values of these remainders (namely 0…K-1), this information can be stored in a bitmask. The mod_bitmask for len+1 can be calculated by setting the bits corresponding to (10r+d)%K for all r in R.
The number of DP states would be len * 2 * (2 ^ K) and this would also roughly be the time complexity as each state is evaluated once.
Here is my
[2].
Note - Leading zeroes also have to be dealt with specially, because leading zeroes form a substring which is divisible by ***K*** but it has to be ignored.
[1]: http://stackoverflow.com/a/22394258/4977227
[2]: https://www.codechef.com/viewsolution/10999398
2 Likes
What is PHP?