Contest Duration: - (local time) (100 minutes) Back to Home

## F - +1-1x2 Editorial by en_translator

Considering the opposite operations, we have the following equivalent problem:

Find the minimum number of operations of the following three types to change $$Y$$ to $$X$$:

• Type $$1$$ : Add $$1$$ to $$Y$$
• Type $$2$$ : Subtract $$1$$ from $$Y$$
• Type $$3$$ : Divide $$Y$$ by $$2$$ (only if $$Y$$ is divisible by $$2$$)

Here, it is obvious that Type $$1$$ and Type $$2$$ does not appear consecutively.
Also, instead of adding $$1$$ $$k (k \ge 2)$$ times and then dividing by $$2$$, we can add $$1$$ $$k-2$$ times, divide by $$2$$, and then add $$1$$ once, so that the number of operations is fewer (and the same applies for subtraction). Thus, we can see that we don’t have to perform Type $$1$$ or Type $$2$$ consecutively, except for after the last operation of Type $$3$$.
Conversely, if $$Y = y$$ after the last operation of Type $$3$$, the number of remaining operations is determined to $$|X - y$$.

With the observations above, consider the following recursive function:

$$\mathrm{solve}(y)$$ : Answer for $$Y = y$$
$$\mathrm{solve}(y) =$$

• If $$y = 1$$ : $$|X - y|$$
• If $$y$$ is odd but not $$1$$ : $$\min(|X - y|, \mathrm{solve}(\frac{y + 1}{2}) + 2, \mathrm{solve}(\frac{y - 1}{2}) + 2)$$
• If $$y$$ is even : $$\min(|X - y|, \mathrm{solve}(\frac{y}{2}) + 1)$$

Memorize this by $$y$$ and call $$\mathrm{solve}(Y)$$, and we obtain the answer.

Now let’s consider the time complexity.
Consider the number of $$y$$ in $$\mathrm{solve}(y)$$ that originates from $$\mathrm{solve}(Y)$$.
If we regard the execution of $$\mathrm{solve}(Y)$$ as Level-$$0$$ recursion, then $$y$$ in Level-$$d$$ recursion satisfies:

• $$y \ge \frac{\frac{\frac{Y - 1}{2} - 1}{2} - 1}{2}_\ddots$$ ($$d$$ fractions) $$= \frac{Y}{2^d} - \sum_{i = 1}^d \frac{1}{2^d} \gt \frac{Y}{2^d} - 1$$ (If the recursion is repeated with $$\mathrm{solve}(\frac{y - 1}{2})$$)
• $$y \le \frac{\frac{\frac{Y + 1}{2} + 1}{2} + 1}{2}_\ddots$$ ($$d$$ fractions) $$= \frac{Y}{2^d} + \sum_{i = 1}^d \frac{1}{2^d} \lt \frac{Y}{2^d} + 1$$ (If the recursion is repeated with $$\mathrm{solve}(\frac{y + 1}{2})$$)

Therefore, for each level, at most $$2$$ (constant) kinds of $$y$$ is called.
Since there are no more than $$O(\log(Y))$$ levels, the total time complexity is $$O(\log(Y))$$ if we use an $$O(1)$$ hash map.

posted:
last update: