Palindrome, Twelve and Two Terms

Key observation

We need non-negative integers $a,b$ such that

$$a+b=n,$$

$a$ is a palindrome, and $b$ is divisible by $12$.

Since $b=n-a$, the divisibility condition becomes

$$12 \mid b \iff 12 \mid (n-a) \iff a\equiv n\pmod{12}.$$

So we do not need a palindrome close to $n$. We only need any palindrome $a\le n$ with the same remainder modulo $12$ as $n$. That’s the whole trick. Everything else is noise.

Tiny palindromes cover every residue

Let

$$r = n \bmod 12.$$

For most residues, there is an absurdly small palindrome with that residue:

| residue $r$ | palindrome $a$ | |---:|---:| | $0$ | $0$ | | $1,2,\dots,9$ | $r$ | | $10$ | $22$ | | $11$ | $11$ |

Why does this work?

• $0$ is a palindrome, and $0\equiv 0\pmod{12}$.
• Every one-digit number is a palindrome, so $r$ works for $1\le r\le 9$.
• $11$ is a palindrome, and $11\equiv 11\pmod{12}$.
• $22$ is a palindrome, and

$$22\equiv 10\pmod{12}.$$

Then we output

$$b=n-a.$$

By construction, $a\equiv n\pmod{12}$, so $b$ is divisible by $12$.

The only bad case

For $r=10$, our representative is $a=22$. This requires $n\ge 22$.

The smallest positive number with remainder $10$ modulo $12$ is $10$ itself. Can $n=10$ work?

If $a+b=10$ and $12\mid b$, then since $0\le b\le 10$, we must have $b=0$, so $a=10$. But $10$ is not a palindrome.

Equivalently, all palindromes $a\le 10$ are

$$0,1,2,3,4,5,6,7,8,9,$$

and none of them is congruent to $10$ modulo $12$.

So $n=10$ is impossible, and every other $n$ works.

Algorithm

For each test case:

1. Compute $r=n\bmod 12$.
2. If $r=10$:
   • if $n=10$, print $-1$;
   • otherwise take $a=22$.
3. Else if $r=11$, take $a=11$.
4. Otherwise take $a=r$.
5. Print $a$ and $n-a$.

Correctness proof

We prove that the algorithm outputs a valid beautiful pair whenever one exists, and outputs $-1$ only when impossible.

Lemma 1

If the algorithm outputs a pair $(a,b)$, then $a+b=n$.

Proof. The algorithm always sets $b=n-a$, so directly

$$a+b=a+(n-a)=n.$$

Lemma 2

If the algorithm outputs a pair $(a,b)$, then $a$ is a palindrome.

Proof. The possible values of $a$ are:

$$0,1,2,\dots,9,11,22.$$

All one-digit numbers are palindromes, and both $11$ and $22$ are palindromes. Therefore $a$ is always a palindrome. ∎

Lemma 3

If the algorithm outputs a pair $(a,b)$, then $b$ is divisible by $12$.

Proof. The chosen $a$ always satisfies

$$a\equiv n\pmod{12}.$$

Therefore

$$b=n-a\equiv 0\pmod{12},$$

so $12\mid b$. ∎

Lemma 4

If $n=10$, no beautiful pair exists.

Proof. We need $a+b=10$ with $b$ divisible by $12$ and $b\ge 0$. Since $b\le 10$, the only possible multiple of $12$ is $b=0$. Hence $a=10$, but $10$ is not a palindrome. Contradiction. ∎

Theorem

For every test case, the algorithm prints a valid beautiful pair if one exists, and prints $-1$ otherwise.

Proof. For $n=10$, Lemma 4 shows that printing $-1$ is correct. For every other $n$, the algorithm outputs a pair. By Lemmas 1, 2, and 3, that pair satisfies all required conditions. ∎

Complexity

Each test case uses only a few arithmetic operations, so the complexity is

$$O(1)$$

per test case, and

$$O(t)$$

overall. Memory usage is

$$O(1).$$