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

×

Editorial for CHEFSPCL in LOCJUL16

0
1

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

3★prudvinit
10318
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.

link

answered 03 Aug '16, 02:05

chinmay2's gravatar image

4★chinmay2
643
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).

Code

link

answered 02 Aug '16, 22:54

nibnalin's gravatar image

6★nibnalin
1611515
accept rate: 0%

What is PHP?

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

@likecs pigeon hole principle.

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

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,882
×114

question asked: 02 Aug '16, 09:43

question was seen: 1,227 times

last updated: 03 Aug '16, 20:57