ADP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Jatin Gupta & Gaurav Aggarwal
Tester: Aanya Jindal
Editorialist: Aanya Jindal

DIFFICULTY:

Easy-medium

PREREQUISITES

GCD, math

PROBLEM:

Given start and end positions on a line and the number of steps in forward and backward direction Adhiraj can take, find if the end position can be reached under the constraints.

QUICK EXPLANATION:

ax + by = c has a solution for x and y if and only if c is a multiple of gcd of a and b.
(Linear Diophantine Equation).

In our problem a = f, b = b and c = y-x. So after checking all boundary conditions if gcd of f and b divides the distance to be travelled, then Adhiraj can reach his destination.

EXPLANATION:

The problem required handling corner cases as well along with the knowledge of the gcd which will be used for main solution.

Following cases should be handled properly:

CASE 1: When c = y-x = 0
Answer will always be YES because Adhiraj has no steps to move.

In further cases we assume that c != 0

CASE 2: When f = 0 AND b = 0
Answer will always be NO because Adhiraj can’t make any step at all and thus won’t be able to reach his destination.

CASE 3: When f = 0 AND b != 0
Here Adhiraj can only move in backward direction and that too only in multiples of b.
Thus,
If c < 0 AND c%b == 0 answer will be YES
Else answer will be NO

CASE 4: When f != 0 AND b == 0
By similar reasoning as CASE 3,
If c > 0 AND c%f == 0 answer will be YES
Else answer will be NO

CASE 5: When none of the above cases follow, i.e. f, b, c != 0

When we try to solve this case, we end up with the equation,
fx - by = c,
Where, x is the number of steps in forward direction
y is the number of steps in backward direction.

It should however be noted that x and y should only take positive integer values.
(since, steps can’t be negative)

This equation is indeed a Linear Diophantine Equation and its solution says that
ax + by = c has integral solutions for x and y if and only if c is a multiple of gcd of a and b.

Let’s see this intuitively using an example,
Suppose that f = 4 and b = 6. So we can easily see that to travel 2 in +X, we can take 2 steps forward and 1 step backward. So, ‘ffb’ gives +2. Now, to travel 2 in -X, we can take 1 step backward and 1 step forward. So, ‘bf’ gives -2. Now we can travel in multiples of 2. But see if you can take steps such that distance travelled is not a multiple of 2 (which is GCD of 4 and 6).

Thus,
If c%gcd(f, b) == 0 answer will be YES
Else answer will be NO

To compute gcd, in-built function __gcd can be used or any implementation of eucledian gcd will work.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

//