Editorial for Ground Is Lava

Walking directly from $a$ to $b$ is always possible, so one candidate answer is:

The only other useful idea is to use the pole-vault move, which connects consecutive multiples of $k$. If a route uses these vaults, then it has the following form:

1. walk from $a$ to some multiple $kx$,
2. use vault moves between multiples of $k$,
3. walk from some multiple $ky$ to $b$.

For fixed integers $x$ and $y$, the cost of this route is:

Now we only need to know which multiples are worth trying. For the start point $a$, it is enough to consider the closest multiple of $k$ on the left and the closest multiple of $k$ on the right. These correspond to:

The same is true for $b$.

Why is this enough? Suppose we choose a multiple farther away from $a$ than both of these. Moving it one step closer to $a$ changes the vaulting part by at most $1$, but decreases the walking distance from $a$ by $k$. Since $k \geq 1$, this never makes the answer worse. So an optimal route that uses the pole can always be found using one of the two neighboring multiples near each endpoint.

Therefore, we try at most four vault candidates:

The answer is the minimum of the direct walking cost and these four values.

Be careful with negative values of $a$ and $b$. In C++, integer division rounds toward zero, not toward $-\infty$, so a custom floor-division function is needed.

Complexity

Only a constant number of candidates are checked, so the time complexity is:

The memory complexity is also: