Editorial for CHEFSPCL in LOCJUL16

bitmasking
dynamic-programming

#1

Can someone share their approach for the problem CHEFSPCL in July LOC competitive programming marathon?


#2

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

#3

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 -

  1. len - The length of number generated till now.

  2. 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.

  3. 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

#4

What is PHP?


#5

@likecs
pigeon hole principle.