Official

H - Digit Sum Divisible 2 Editorial by en_translator

Problems that asks to construct and print something that satisfies certain conditions falls into a genre called constructive problems; this problem is one of them. Constructive problems require a kind of inspiration, so some of you may have been perplexed, while those who are good at puzzles may have find it easier to solve than usual.. Considering the divisibility rules,

Since this problem requires a certain amount of inspiration steps, we will explain the solution through step-by-step hints.

Hint 1 First, ignore the constraints $a + 1 \leq 2N$ for a while. What kind of integers form twin good integers?
If you do not get it, think how we can apply the reason why $(2024, 2025)$ is twin good integers.

Hint 2 $(2024, 2025)$ is twin good integers because:
  • The digit sum of $2024$ is $8$, and that of $2025$ is $9$.
  • An integer is a multiple of $8$ if and only if the last three digits is a multiple of $8$.
  • An integer is a multiple of $9$ if and only if the digit sum is a multiple of $9$.
  • These divisibility rules suggest that $(2024,2025)$ is twin good integers.

Hint 3 Considering the divisibility rules, an integer with digit sum $1$, $3$, or $9$ is in general a good integer. Namely, for example these form twin god integers:
  • $a=(\text{even number with digit sum }2)$, $a+1=(\text{integer with digit sum }3)$
  • $a=(\text{multiple of }8\text{ with digit sum }8)$, $a+1=(\text{integer with digit sum }9)$.
We may utilize this fact.

Hint 4 These pairs form twin good integers:
  • for any integer $B$ no less than $3$.
    • $(2 \times 10^B + 24, 2 \times 10^B + 25)$
    • $(2 \times 10^B, 2 \times 10^B + 1)$
    • $(35 \times 10^B, 35 \times 10^B + 1)$
    • $(8 \times 10^B, 8 \times 10^B + 1)$
      $\vdots$
Here, we adjust the digit sum with the most significant digits, insert many zeros in between, and set the last digits so that it forms an even number of a multiple of $8$.

Hint 5 Once you came up with several constructions, all that left is to put them together.


Solution If $N \lt 10^6$, we can brute-force over all $a$ with $N \leq a \leq 2N-1$. The complexity is $\mathrm{O}(N \log N)$, which is fast enough.
Hereinafter we assume $N \geq 10^6$. Considering the divisibility rules, an integer with digit sum $1$, $3$, or $9$ is in general a good integer. Namely, these form twin god integers:
  • $a=(\text{even number with digit sum }2)$, $a+1=(\text{integer with digit sum }3)$
  • $a=(\text{multiple of }8\text{ with digit sum }8)$, $a+1=(\text{integer with digit sum }9)$.

Using this fact, we can construct enormous twin good integers by adjusting the digit sum with the most significant digits, followed by many zeros. Specifically, these are always twin good integers:
  • for any integer $B$ no less than $3$.
    • $(2 \times 10^B + 24, 2 \times 10^B + 25)$
    • $(2 \times 10^B, 2 \times 10^B + 1)$
    • $(35 \times 10^B, 35 \times 10^B + 1)$
    • $(8 \times 10^B, 8 \times 10^B + 1)$
      $\vdots$
All that left is to print appropriate twin good integers according to $N$. Specifically, let $x$ be the most significant two digits of $x$. We can let $(a, a+1)$ be
  • $(17 \times 10^B, 17 \times 10^B + 1)$ if $10 \leq x \leq 16$
  • $(26 \times 10^B, 26 \times 10^B + 1)$ if $17 \leq x \leq 25$
  • $(35 \times 10^B, 35 \times 10^B + 1)$ if $26 \leq x \leq 34$
  • $(62 \times 10^B, 62 \times 10^B + 1)$ if $35 \leq x \leq 61$
  • $(107 \times 10^B, 107 \times 10^B + 1)$ if $62 \leq x \leq 99$
to pick $B$ so that $N \leq a \leq 2N-1$ always holds. Note that $10^B$ is always a multiple of $8$, because we initially imposed $N \geq 10^6$. This problem can be solved by appropriately implementing this, and it runs fast enough.

We think there are a variety of solutions other than this. For example, we can constrain the candidates of $a$ to those integers ending with zeros, and almost all other digits are also $0$, and search them either randomly or deterministically. This is a heuristic solution based on the following conjectures:
  • If the digit sum is $d$ (which is not a multiple of $2$, $3$, nor $5$), it is a multiple of $d$ with the probability of about $1/d$, so it is probably good strategy to keep $d$ small.
  • To support the case where the digit sum is a multiple of $2$ or $5$, it is probably safe to let it end with $0$.
By designing an appropriate search based on the property of good integers, one may get Accepted verdict without actually constructing the solution as described above.

posted:
last update: