Editorial for TLE '17 Contest 8 P3 - Curious Numbers


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

The K is a red herring and should not add any additional difficulty to this problem.

For the first 20\% of the points, for every query, we check all numbers from M to N to see if they are palindromes and divisible by K. An easy way to check if a number is a palindrome is to reverse the number using multiplication and mod by 10.

Time Complexity: \mathcal{O}(\max(N)Q)

For the next 30\% of the points, we should first precompute whether or not each number from 1 to 10^6 is a palindrome divisible by K. Note that there are only approximately 10^3 palindromes in this range. Thus, for every query, we iterate through all of the palindromes and count those that are in between M and N and divisible by K.

Time Complexity: \mathcal{O}(\sqrt{\max(N)}Q+\max(N))

For full points, we generate all palindromes efficiently. Start with all one and two digit palindromes, including 0 and 00. Then, for each existing palindrome, add digits 0 through 9 to the front and end to create palindromes with two more digits. Repeat until palindromes of length 10 have been generated. Finally, remove all palindromes that end with 0 (as they must begin with 0) or are not divisible by K.

Next, we sort these palindromes, and we can answer the queries using binary search. Note that it is possible to generate palindromes in order, ridding the need to sort.

Time Complexity: \mathcal{O}(Q\log\sqrt{\max(N)}+\sqrt{\max(N)})


Comments

There are no comments at the moment.