 # GRITGRID - Editorial

Author: S. Manuj Nanthan
Preparer: Tejas Pandey
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh

1691

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')

1 Like

can anyone suggest a recursive solution
Here is my shot at it

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;

bool solve(int n,int m,int x,int y,int xa,int ya,int nb,int mb)
//(xa,ya)-->(1,1) starting of alice'
//(nb,mb)-->(n,m) starting point of bob;

{
if(nb==xa and mb==ya)
return true;
if(nb>n || xa>n)
return false;
if(nb<1 || xa<1)
return false;
if(mb>m || ya>m)
return false;
if(mb<1 || ya<1)
return false;
//for x steps alice;
//all posssible moves;
for(int i=0;i<x;i++)
{
solve(n,m,x,y,xa,ya,nb+1,mb);
solve(n,m,x,y,xa,ya,nb,mb+1);
solve(n,m,x,y,xa,ya,nb-1,mb);
solve(n,m,x,y,xa,ya,nb,mb-1);
}
//for y steps bob;
//all possible moves;
for(int e=0;e<y;e++)
{
solve(n,m,x,y,xa+1,ya,nb,mb);
solve(n,m,x,y,xa,ya+1,nb,mb);
solve(n,m,x,y,xa-1,ya,nb,mb);
solve(n,m,x,y,xa,ya-1,nb,mb);
}
}

int main(){
ll int t=0;
cin>>t;
while(t--){
ll int n=0,m=0,x=0,y=0;
cin>>n>>m>>x>>y;
ll int na=n,mb=m;
ll int xa=1,ya=1;
int ans = solve(n,m,x,y,xa,ya,na,mb);
if(ans)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;

}
}


1 Like

hell ">

good