You are not logged in. Please login at to post your questions!


Editorial for CHEFSPCL in LOCJUL16


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

asked 02 Aug '16, 09:43

prudvinit's gravatar image

accept rate: 0%

This can be solved by using Digit-DP. 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,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 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

chinmay2's gravatar image

accept rate: 12%

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

nibnalin's gravatar image

accept rate: 0%

What is PHP?

(03 Aug '16, 17:13) likecs6★

@likecs pigeon hole principle.

(03 Aug '16, 20:57) nibnalin6★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 02 Aug '16, 09:43

question was seen: 1,227 times

last updated: 03 Aug '16, 20:57