 # DIAGMOVE - Editorial

Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

CAKEWALK

None

## PROBLEM:

Given two integeres x and y, we need to find if it is possible to reach (x, y) from (0,0) if we can perform the following operations any number of times:

• Move coordinate (i,j) to (i+1,j+1)
• Move coordinate (i,j) to (i+1,j-1)
• Move coordinate (i,j) to (i-1,j+1)
• Move coordinate (i,j) to (i-1,j-1)

## QUICK EXPLANATION:

• If the absolute value of x+y is even, we output YES, else we output NO.

## EXPLANATION:

Without loss of generality, we can change (x,y) to (abs(x), abs(y)) where abs(i) denotes the absolute value of i.

First, let us observe the following:

Suppose we are at (i,j) and perform the first operation and move to (i+1,j-1). We can observe that in this case the parity of i+j doesn’t change, for (i+1,j-1) the parity is same as (i,j) since (i+1+j-1)\mod 2=(i+j) \mod 2.

Similarly, we can prove that the parity of i+j doesn’t change for other operations also.

We know that for the starting point (i,j) = (0,0), parity of i+j=0+0=0 .

From this, we can tell that if parity of x+y is 1, the answer is impossible.

Otherwise we can prove that the answer is always possible.

Let us assume x \lt y. Then we can apply the first operation \frac{(y+x)}{2} times, and then second operation \frac{(y-x)}{2} times. The x coordinate will then become \frac{(y+x)}{2} - \frac{(y-x)}{2} = x and the y coordinate will become \frac{(y+x)}{2} + \frac{(y-x)}{2} = y.

Similarly, we can prove this for x \geq y.

## TIME COMPLEXITY:

O(1) for each testcase.

## SOLUTION:

Editorialist's solution

#include <bits/stdc++.h>
using namespace std;

int main()
{
int tests;
cin >> tests;
while (tests--)
{
int x, y;
cin >> x >> y;
if (abs(x + y) % 2 == 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}


Setter's solution

#include<bits/stdc++.h>
using namespace std;

void solve(int tc) {
int x, y; cin >> x >> y;
if ((abs(x) + abs(y)) % 2 == 0) cout << "YES\n";
else cout << "NO\n";
}

signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) solve(i);
return 0;
}


Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int x, y;
cin>>x>>y;
if((x + y) % 2){
cout<<"NO\n";
}else{
cout<<"YES\n";
}
}
return 0;
}



Please comment below if you have any questions, alternate solutions, or suggestions. My Approach

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#define ll long long
const unsigned int M = 1000000007;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T_set; // PBDS_set
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> T_multiset; // PBDS_multiset

void solve()
{
int t;
cin>>t;
ll a, b;
while(t--){
cin>>a>>b;
if(abs(a+b)%2 == 0) cout<<"YES\n";
else cout<<"NO\n";

}
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
solve();
return 0;
}