ICL1804 - Editorial

easy-medium
editorial
equations
gcd
icl1804
icl2018
likecs

#1

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

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

Solution Links

Setter’s solution


#2

@likecs simple explanation and easy solution :stuck_out_tongue:

But didn’t get the idea of implementing the solution in O(log p) time complexity . Can someone help ?