Can someone share their approach for the problem CHEFSPCL in July LOC competitive programming marathon?
Editorial for CHEFSPCL in LOCJUL16
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*%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
This can be solved by using DigitDP. 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,L1].
Now to count the number of special numbers in range [0,N] we use digitDP.
The essence of digitDP 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…K1), 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