### PROBLEM LINK:

**Author:** Sergey Kulik

**Tester:** Yanpei Liu

**Editorialist:** Pawel Kacprzak

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Ad hoc, Palindrome

### PROBLEM:

Let palindromic number be a number whose decimal digits form a palindrome. For example, $1, 22, 414, 5335$ are palindromic numbers, while $13$ and $453$ are not. Your task is to find the sum of all palindromic numbers in a range $[L, R]$ inclusive. In one test file, you have to solve this task for at most 100 test cases.

### QUICK EXPLANATION:

Precompute the sum of palindromic number not greater than $K$, for $1 \leq K \leq 10^5$, and store these values in an array. Provide an answer for a single test case $[L, R]$ using precomputed sums for $R$ and $L - 1$.

### EXPLANATION:

Let's first consider solving the problem for a single test cases. We are given two number $L$ and $R$ and we have to compute the sum of palindromic numbers from $L$ to $R$ inclusive. If we can check if a number $N$ is palindromic, then we can iterate over all numbers $N$ in a range $[L, R]$ and add $N$ to the result if and only if $N$ is palindromic. How to check if a number $N$ is palindromic? Well, it is pretty straightforward, we can list the sequence of digits of $N$ from right to left, and check if that sequence is a palindrome comparing corresponding digits. A pseudocode of that method can look like that:

// we assume that N > 0 bool is_palindromic(N): digits = [ ] while N > 0: digits.append(N % 10) N /= 10 i = 0 j = digits.size() - 1 while i < j: if digits* != digits[j]: return False i += 1 j -= 1 return True

This check runs in $O(\log(N))$ time, because the decimal representation of $N$ has $O(\log(N))$ digits.

Being able to perform the palindromic check, we can accumulate the result iterating over all integers in range [L, R]. A pseudocode for it might look like this:

res = 0 for N = L to R: if is_palindromic(N): res += N

This method works in $O((R - L) \cdot \log(R))$ time for a single test case, but since we have to handle at most $100$ of them and a range $[L, R]$ can have up to $10^5$ elements, this method will pass only the first subtask and will timeout on the second.

##How to speed it up?

The crucial observation here is that, during the whole computation described above, we might check in a number N is palindromic many times! This is not good, but fortunately, there is a common technique to avoid that.

Often when we are asked many times to compute some result for objects in some range [$A, B]$, we can do the following:

Let F[N] := exttt{the result for a range } [0, N]

If we are able to compute F[N] for all possible N, then the answer for a single query [A, B] equals F** - F[A - 1], because F** contains the result for all numbers not greater than B, so if we subtract F[A - 1], i.e the result for all number smaller than A, from it, we will get the result for all numbers in range [A, B].

If you did not know this technique, please remember it, because it is very useful.

Using the above method, we can precompute:

S[N] := exttt{sum of palindromic number not greater than } N

in the following way:

S[0] = 1 for N = 1 to 100000: S[N] = S[N - 1] if is_palindromic(N): S[N] += N

The above method runs in O(10^5 \cdot \log(10^5)) time, and we can use the S table to answer any single query [L, R] in a constant time.

### AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found [here][333]. Tester's solution can be found [here][444].