Can someone share their approach for the problem CHEFSPCL in July LOC competitive programming marathon? asked 02 Aug '16, 09:43

This can be solved by using DigitDP. If you haven't heard of it before, I suggest you read this post. 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 
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 code. 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. answered 03 Aug '16, 02:05

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(see the "Finding remainder of a number when divided by 7" section). answered 02 Aug '16, 22:54
