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 \leq a \leq b \leq 10^{18}$

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

Sample Input 1

Copy

123 321

Sample Output 1

Copy

Sample Input 2

Copy

123456789 987654321

Sample Output 2

Copy

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.