Can Alice Meet Bob?

Given two coordinates A and B and a few valid movements, you have to determine whether you can move from A to B.

Problem

This is a familiar pattern to me. So, I tried to write a recursive solution with two exit conditions,
one is when the coordinates match in which case I return True.
But I can’t think of the exit condition where I am supposed to return False because the movement can be made to all 4 directions which makes it difficult to set constraints for the coordinate to be only within certain limits.

And even if we manage to find an exit condition for False, the solution seems to be exponential. Makes me wonder if the solution is just a formula and hence a O(1) solution.

I have been stuck on this since morning, please help. Thank you.

gcd cannot decrease.

Can you please elaborate?

Notice that \gcd(a, b) = gcd(a+b, b) = gcd(a, a-b). The fact that it’s related to gcd is already a very big hint.

3 Likes

@raahelpie did you managed to solve the problem? If yes explain.

No. I thought for a while about the GCD hint given in the other comment but couldn’t come up with any solution. Or maybe, I just didn’t think hard enough.