Problem LinkAuthor: Divesh and Bhuvnesh Jain Testers: Bhuvnesh Jain, Praveen Dhinhwa Editorialist: Bhuvnesh Jain DifficultyEASYMEDIUM PrerequisitesSystem of Equations, Greatest common divisor. ProblemYou 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$. ExplanationSince 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:
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 ProblemTo 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 Linksasked 03 Mar '18, 19:10

@likecs simple explanation and easy solution :p But didn't get the idea of implementing the solution in O(log p) time complexity . Can someone help ? answered 14 Mar '18, 11:35
