Problem Link
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:
-
N - S = m, as traveling north increase y-coordinate by 1 while traveling south decreases y-coordinate by 1.
-
E - W = n, as traveling east increase x-coordinate by 1 while traveling west decreases x-coordinate by 1.
-
Na + Sb + Ec + Wd = P, constraint that total energy lost should be equal to the inital energy.
-
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
$N(a + b) + E(c + d) = P + mb + nd$.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.
