### 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[i] != 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] := \texttt{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[B] - F[A - 1], because F[B] 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] := \texttt{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.

Tester’s solution can be found here.