×

# ICL1804 - Editorial

Practice

Contest

Author: Divesh and Bhuvnesh Jain

Testers: Bhuvnesh Jain, Praveen Dhinhwa

Editorialist: Bhuvnesh Jain

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

$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.

Setter's solution

6★likecs
3.7k2380
accept rate: 9%

19.8k350498541

 0 @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 318●1●10 accept rate: 1%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,672
×593
×319
×29
×17
×2

question asked: 03 Mar '18, 19:10

question was seen: 374 times

last updated: 14 Mar '18, 12:17