DIAGMOVE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

CAKEWALK

PREREQUISITES:

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. :slight_smile:

2

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;
}