Problem Link

Practice

Contest

Author: Divesh and Bhuvnesh Jain

Testers: Bhuvnesh Jain, Praveen Dhinhwa

Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

System of Equations, Greatest common divisor.

Problem

You have an initial energy of $P$ units. You are required to reach from $(0, 0)$ to $(n, m)$ in any possible way with the only condition that your final energy should be zero. The energy lost in traveling in all $4$ directions is given the problem.

In case, you are able to reach $(n, m)$ with zero energy, then report the length of the shortest path possible else print $-1$.

Explanation

Since we can move in any possible way we want, let us assume after reaching our destination, $(n, m)$, the numbers of steps taken in north, south, east, west direction are $N, S, E, W$ respectively. Also, the corresponding energy lost while traveling in each of these directions be $a, b, c, d$. Thus we have the following constraints for any valid path:

1. $N - S = m$, as traveling north increase y-coordinate by 1 while traveling south decreases y-coordinate by 1.

2. $E - W = n$, as traveling east increase x-coordinate by 1 while traveling west decreases x-coordinate by 1.

3. $Na + Sb + Ec + Wd = P$, constraint that total energy lost should be equal to the inital energy.

4. N, S, E, W are integers and $N >= m$, $S >= 0$, $E >= n$, $W >= 0$.

Using the first 2 equations, we can modify the 3rd equation as

Since, all variables are integers, by Euclid algorithm solution exists only when gcd(a + b, c + d) divides $(P + mb + nd)$. But existence by Euclid algorithm just tells us that solution with integers exists, not that these integers satisfy the additional constraints mentioned in $4$.

To check this, just iterate over the possible values of $N$ and find the corresponding value of $E$ from last equation and of $S, W$ from equation $1$ and $2$. In case, all these integers satisfy the constraints mentioned in $4$, then we can update the answer with the value of the length of path i.e. $(N + S + E + W)$.

For details, refer to the setter's solution below.

Bonus Problem

To solve this problem with harder constraints, i.e. in complexity of $O(\log{P})$, you can refer to ideas in this thread

Time Complexity

$O(P)$, per test case.

Space Complexity

$O(1)$ per test case.

Solution Links

Setter's solution