[Solution] Gritty Grid solution codechef

Table of Contents

Gritty Grid solution codechef

Gritty Grid solution codechef – Alice and Bob are trapped in a grid having N rows and M columns. Alice is currently at cell (1, 1) and Bob is at cell (N, M) and they both want to meet each other at any common cell. But they have some restrictions in the way they can move and meet:

step is defined as moving to an adjacent cell from the current cell that the person is in. So in a single step, if a person is at (X, Y) they may move to any one of the following cells, provided that they are inside the grid’s boundaries – (X + 1, Y)(X, Y + 1)(X – 1, Y)(X, Y – 1).

move for Alice is defined to be exactly X steps. And a move for Bob is defined to be exactly Y steps.

[Solution] Gritty Grid solution codechef

They can only meet at the common cell after Alice has just completed her move i.e. they should not meet in the middle of anyone’s move or at the end of Bob’s move. The first time that they meet should be right after a move of Alice, and they stop moving after that.

Alice makes a move first, then Bob makes a move, and they alternate like this.

Alice and Bob want to know if it is possible to meet with these restrictions. Please help Alice and Bob by telling them whether they would be able to meet each other if they stick to these restrictions.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of a single line of input containing four integers: NMX and Y denoting the number of rows, number of columns, number of steps in Alice’s one move and the number of steps in Bob’s one move respectively.

Output Format

For each test case, output in a single line \texttt{YES} if they would be able to meet each other at a common cell, else output \texttt{NO}.

You may print each character of the string in uppercase or lowercase (for example, the strings \texttt{YeS}\texttt{yEs}\texttt{yes} and \texttt{YES} will all be treated as identical).

[Solution] Gritty Grid solution codechef

  • 1 \leq T \leq 1000
  • 2 \leq N, M \leq 10^6
  • 1 \leq X, Y \leq 10^9

Sample 1:

Input

Output

4
2 2 2 1
2 2 1 1
2 2 1 2
2 3 3 3
Yes
No
Yes
Yes

[Solution] Gritty Grid solution codechef

Explanation:

Test case 1: Alice is initially at (1, 1), and Bob is at (2, 2). In Alice’s first move, she has to take 2 steps – she can choose to go from (1, 1) \rightarrow (1, 2) \rightarrow (2, 2). And so at the end of Alice’s first move, Alice and Bob meet, and they stop. So the answer is Yes.

Test case 2: Alice is initially at (1, 1), and Bob is at (2, 2). In Alice’s first move, she has to take 1 step – she can choose to go from (1, 1) \rightarrow (1, 2), or (1, 1) \rightarrow (2, 1). Similarly for Bob. But you can check that no matter what they do, they can’t coordinate in such a way that they meet only after Alice’s move. So the answer is No.

Test case 3: Alice is initially at (1, 1), and Bob is at (2, 2). In Alice’s first move, she has to take 1 step – she can choose to go from (1, 1) \rightarrow (1, 2). Then in Bob’s move, he has to take 2 steps – he can choose to go from (2, 2) \rightarrow (2, 1) \rightarrow (2, 2). Then in Alice’s second move, she can choose to go from (1, 2) \rightarrow (2, 2). And so at the end of Alice’s second move, Alice and Bob meet, and they stop. So the answer is Yes.

Test case 4: Alice is initially at (1, 1), and Bob is at (2, 3). In Alice’s first move, she has to take 3 steps – she can choose to go from (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3). And so at the end of Alice’s first move, Alice and Bob meet, and they stop. So the answer is Yes.

For Solution

“Click Here”

Leave a Comment