Path Parity solution codechef

Path Parity solution codechef

You are given an integer NN. Let AA be an N×NN×N grid such that Ai,j=i+N(j1)Ai,j=i+N⋅(j−1) for 1i,jN1≤i,j≤N. For example, if N=4N=4 the grid looks like:

Path Parity solution codechef

You start at the top left corner of the grid, i.e, cell (1,1)(1,1). You would like to reach the bottom-right corner, cell (N,N)(N,N). To do so, whenever you are at cell (i,j)(i,j), you can move to either cell (i+1,j)(i+1,j) or cell (i,j+1)(i,j+1) provided that the corresponding cell lies within the grid (more informally, you can make one step down or one step right).

The score of a path you take to reach (N,N)(N,N) is the sum of all the numbers on that path.

You are given an integer KK that is either 00 or 11. Is there a path reaching (N,N)(N,N) such that the parity of its score is KK?

Recall that the parity of an integer is the (non-negative) remainder obtained when dividing it by 22. For example, the parity of 246246 is 00 and the parity of 1111 is 11. In other words, an even number has parity 00 and an odd number has parity 11.

Input Format

  • The first line contains a single integer TT — the number of test cases. Then the test cases follow.
  • The first and only line of each test case contains two space-separated integers NN and KK.

Output Format

  • For each test case, output the answer on a new line — YES if such a path exists, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, the strings YESyEs, and yes will all be treated as identical.


  • 1T1051≤T≤105
  • 1N1091≤N≤109
  • K{0,1}K∈{0,1}

Sample Input 1

Path Parity solution codechef

1 0
2 0
2 1
3 1

Sample Output 1 



Test case 11: There is only one possible path, which starts and ends at the same cell. The score of this path is 11, which is odd. An even score is impossible.

Test case 22: The following path has an even score for N=2N=2:

Test case 33: The following path has an odd score for N=2N=2:

Path Parity solution codechef

Test case 44: The following path has an odd score for N=3N=3:


Click Here

Leave a Comment

Your email address will not be published.