PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: S. Manuj Nanthan
Preparer: Tejas Pandey
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
1691
PREREQUISITES:
Observation
PROBLEM:
On an N\times M grid, Alice starts at cell (1, 1) and Bob starts at cell (N, M). Alice moves X steps at a time, and Bob moves Y steps at a time.
Is it possible for Alice and Bob to reach the same cell at the end of Aliceâ€™s move?
EXPLANATION
Working out a few examples should give you the idea that the only things that really matter are the parities of N, M, X, and Y.
Since N, M \geq 2, there are only two cases to consider (and no edge cases):
- The answer is â€śYesâ€ť if at least one of X and Y has the same parity as N+M
- The answer is â€śNoâ€ť otherwise
Proof
Let d = N-1 + M-1.
We claim that the answer is â€śYesâ€ť If and only if d has the same parity as at least one of \{X, Y\}. Note that d has the same parity as N+M.
The parity of the manhattan distance between Alice and Bob after the first move is (d-x)\pmod 2. After the second move, it is (d-x-y)\pmod 2, and so on. This sequence is:
d, d-x, d-x-y, d-y, d, d-x, \ldots
The points where it is the end of Aliceâ€™s turns are d-x, d-y, d-x, d-y, \ldots
If the distance is zero after Aliceâ€™s move, we need this to be 0. So, d should have the same parity as at least one of \{X, Y\}. If not, the answer is definitely â€śNoâ€ť.
Now, we show that this condition is also sufficient.
First, note that if X is odd, Alice can always be made to move exactly one square on her turn. Similarly, Bob can do this when Y is odd.
- Case 1: If Y is even: We make Bob stay at (N, M) always. Since even X and odd d cannot be the case (since Y is already even), we can always make Alice reach (N, M).
- Case 2a: If Y is odd, and X is even, and if d \gt X: We make Alice stay at (1, 1) throughout the beginning, and make Bob reduce the Manhattan distance by 1 in each move. When the distance between them becomes exactly X, Alice moves and meets Bob.
- Case 2b: If Y is odd, and X is even, and if d \leq X: Either Alice can meet in the first move itself, or Bob reduces the distance by 1, and then Alice meets Bob on the next move (Note that since N, M \geq 2, the d \geq 2, and so it can be reduced by 1 by Bob without meeting Alice).
- Case 3: If Y is odd, and X is odd: This means that d is also odd. So, we just make Alice and Bob reduce the distance by 1 at each move, and eventually Alice will be the person to meet Bob in her move.
TIME COMPLEXITY:
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, m, x, y = map(int, input().split())
print('yes' if x%2 == (n+m)%2 or y%2 == (n+m)%2 else 'no')