PROBLEM LINK:
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.