Omsk Programmers

The annoying-looking part

We have two operations:

$1.$ increment one number by $1$,

$2.$ replace one number $n$ by $\left\lfloor n/x \right\rfloor$.

At first glance, increments before divisions look tricky because of rounding. For example, maybe adding a little before dividing changes the quotient. Classic floor-function bait. Luckily, it is bait.

Key observation: increments can be postponed

Fix one starting number $n$. Suppose a path uses exactly $k$ divide-operations and some number of increments, and ends at value $y$.

If we delete all increments from this path, the value after the $k$ divisions is exactly

$$p_k = \left\lfloor \frac{n}{x^k} \right\rfloor.$$

Adding increments somewhere in the path cannot make the final value smaller, so necessarily

$$y \ge p_k.$$

Also, each increment can increase the final value by at most $1$. If an increment happens before a division, it may even get destroyed by the floor, because division is a cruel little bastard. Therefore to reach $y$ after $k$ divisions, we need at least

$$y-p_k$$

increments.

And this bound is achievable: do the $k$ divisions first, reaching $p_k$, then increment $y-p_k$ times.

So for one number $n$, using exactly $k$ divisions, the cost to reach $y$ is

$$k + (y-p_k), \qquad \text{where } p_k \le y.$$

Combine the two numbers

Let us choose:

• $i$ divisions for $a$,
• $j$ divisions for $b$.

Then their base values are

$$p = \left\lfloor \frac{a}{x^i} \right\rfloor, \qquad q = \left\lfloor \frac{b}{x^j} \right\rfloor.$$

After that, we can only increment. The cheapest common value is obviously

$$y = \max(p,q),$$

because making both numbers even larger is just wasting operations for sport.

The increment cost is

$$(\max(p,q)-p)+(\max(p,q)-q)=|p-q|.$$

So for this pair $(i,j)$, total cost is

$$i+j+|p-q|.$$

Therefore the answer is

$$\boxed{\min_{i,j}\left(i+j+\left|\left\lfloor \frac{a}{x^i}\right\rfloor-\left\lfloor \frac{b}{x^j}\right\rfloor\right|\right)}.$$

Why brute force is enough

The sequence

$$n,\left\lfloor n/x\right\rfloor,\left\lfloor n/x^2\right\rfloor,\dots,0$$

has length at most $O(\log_x n)$, and since $x \ge 2$ and $n \le 10^9$, that is at most about $31$ values.

So we generate all pairs $(\text{value}, \text{number of divisions})$ for both $a$ and $b$, try every pair, and take the minimum.

Complexity

For each test case, there are $O(\log_x a)$ states for $a$ and $O(\log_x b)$ states for $b$.

Thus the complexity is

$$O(\log_x a \cdot \log_x b),$$

which is tiny. Memory usage is

$$O(\log_x a + \log_x b).$$