Baltic OI '13 P2 - Palindrome-Free Numbers

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 128M

Problem type

Baltic Olympiad in Informatics: 2013 Day 1, Problem 2

A string is a palindrome if it remains the same when it is read backwards. A number is palindrome-free if it does not contain a palindrome with a length greater than $1$ ~1~ as a substring. For example, the number $16\,276$ ~16\,276~ is palindrome-free whereas the number $17\,276$ ~17\,276~ is not because it contains the palindrome $727$ ~727~.

Your task is to calculate the total number of palindrome-free numbers in a given range.

Input

The input contains two integers, $a$ ~a~ and $b$ ~b~.

Output

The output should contain one integer: the total number of palindrome-free numbers in the range $a, \dots, b$ ~a, \dots, b~ (including $a$ ~a~ and $b$ ~b~).

Constraints

$0 \le a \le b \le 10^{18}$ ~0 \le a \le b \le 10^{18}~

In test cases worth $25$ ~25~ points: $b-a \le 100\,000$ ~b-a \le 100\,000~.

Sample Input 1

123 321

Sample Output 1

Sample Input 2

123456789 987654321

Sample Output 2

167386971

Comments

1

Blackgaurdian3 commented on July 18, 2020, 3:11 a.m. ← edited →

How do I avoid a TLE? I'm currently checking numbers one by one to see if they are a palindrome

3

Plasmatic commented on July 18, 2020, 5:41 a.m. ← edit 2 →

Looping through all the numbers from $a$ ~a~ to $b$ ~b~ is far too slow. A faster approach uses an observation and this technique.