Shortest Increasing Path

The answer is weirdly tiny: it can only be $2$, $3$, or $-1$. No hidden DP. No graph search. The grid is just there to make the statement look more athletic than it is.

Why one step is impossible

The first step must be along the $x$ axis. But $y \ge 1$, so after one step your $y$ coordinate is still $0$. Therefore, answer $1$ is impossible.

Two steps

With two steps, there is no freedom:

1. Move $x$ along the $x$ axis.
2. Move $y$ along the $y$ axis.

The second step must be strictly longer than the first, so this works iff

$y > x.$

If $y>x$, the minimum is immediately $2$.

Three steps

If two steps do not work, try three steps:

• step 1: move $a$ along $x$
• step 2: move $y$ along $y$
• step 3: move $b$ along $x$

We need:

$a+b=x$

and the step lengths must increase:

$a < y < b.$

So the question becomes: can we split $x$ into two positive integers, one smaller than $y$ and one larger than $y$?

The smallest possible first $x$-step is $a=1$. Then the last step is $b=x-1$. This works when:

$1 < y < x-1.$

Since values are integers, that is the same as:

$y \ge 2 \quad \text{and} \quad x \ge y+2.$

If that holds, use steps:

$1,\ y,\ x-1.$

They are strictly increasing, and the total $x$ movement is $1+(x-1)=x$.

Why longer paths never improve the answer

This is the part where people sometimes overthink it and accidentally invent a whole damn algorithm.

Suppose there is some valid path with an even number of steps. Then there are equally many $x$-steps and $y$-steps. Pair them like this:

$(s_1,s_2), (s_3,s_4), \dots$

In every pair, the $y$-step is larger than the $x$-step because the sequence is strictly increasing:

$s_2>s_1,\ s_4>s_3,\dots$

So the total $y$ movement is larger than the total $x$ movement. That means $y>x$, and then the two-step solution already works.

Now suppose there is some valid path with an odd number of steps, at least $3$. Then there is one extra $x$-step. The total $x$ must beat the total $y$ by enough to allow a split around $y$. In particular, any such path implies $x\ge y+2$ and $y\ge 2$, so the three-step construction works.

So we only need these cases:

• If $y>x$, answer is $2$.
• Else if $y\ge 2$ and $x\ge y+2$, answer is $3$.
• Otherwise, answer is $-1$.

Complexity

Each test case is $O(1)$. Memory is $O(1)$.