GRITGRID - Editorial

editorial
,
1

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')
1 Like
3

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
4

hell ">

well

good