yaro's blog

Round 51, D
By yaro, 14 years ago, translation, In English

In this problem one should answer the query: how many beautiful numbers are there in the interval from 1 to R.

Clearly, to check whether a number is divisible by all its digits, it is sufficient to know the remainder of a division by the lcm of all possible digits (call this lcm M), that is M = 8 * 9 * 5 * 7 = 2520. The standart dynamic solution is supposed to maintain such state parameters: the length of the number, "strictly less" flag, current remainder of a division by M and the mask of already taken digits.

The first note: we can maitnain the lcm of the digits already taken, not the mask. This will decrease the number of different values of the last parameter (from 256 to 4 * 3 * 2 * 2 = 48, where 4 is the number of different powers of 2 etc).

Then, it is a good idea to pre-count transitions to the new parameters. But we wanted and tried to set such a time limit restriction, so that this solution would not be enough to avoid TL.

The idea that will decrease the running time even more lies in number theory. If we add digits from the end of a number we may see that the remainder of a number after division by 5 depends only on the last digit. Therefore, we may maintain the flag "last digit = 5 or 0" and ban transitions to the digit 5 if the flag is set to "false". Such an idea reduces the number of states by 5 * 2 / 2 = 5. This solution is fast enough to pass in any language, though there are even more powerful optimizations (the trick mentioned above can be done with digit 2 also).

  • Vote: I like it
  • +18
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I didn't use either of these optimizations but avoided the 'strictly less' flag (so, the number of states is only 2 times less, while with these optimizations it's 48*5 = 240 times less). Still got AC…
→ Reply
  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is actually a lot less due to unnecessity of re-initialization! thanks :)

    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the "strictly less" flag?
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    We want to count the quantity of beautiful numbers that are not greater than some constant N. Dynamic goes by digits from left ro right. "Strictly less" flag is true means that current number is strictly less than correspoding part of N so we are able to add any new digit from '0' to '9'. "Strictly less" flag is false means that current number equals correspoding part of N so we are only able to add new digits from '0' to the corresponding digit of N.
    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In your last paragraph,you say: The idea that will decrease the running time even more lies in number theory. Dost it means "decrease time" is main in number theory,or it can "decrease time" base on number theory? I think it's the first meanning ,but my teammate is the second.⊙﹏⊙b

→ Reply