# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Practice

**Setter:** Daanish Mahajan

**Tester:** Riley Borgard

**Editorialist:** Aman Dwivedi

# DIFFICULTY

Cakewalk

# PREREQUISITES

Observation

# PROBLEM

Given a grid of size 10^5 \times 10^5, covered completely in railway tracks. Tom is riding the train and he is initially at cell (a,b) and Jerry in cell (c,d) . You need to **determine** if Tom can ride the train in exactly K moves to reach cell (c,d). In one step, the train must move to one of its neighboring cells, sharing a side. Tom can go back to the same cell multiple times

# QUICK EXPLANATION

Tom can reach Jerry in **total minimum moves** X where X= abs(c-a) + abs(d-b).

- Tom can reach Jerry in exactly X minimum moves, therefore K needs to greater than equal to X.
- Now, if Tom can reach Jerry in exactly X moves then he can also reach Jerry in exactly X+2, X+4, X+6.... moves.

# EXPLANATION

Why minimum moves required to reach Jerry is X where X=abs(c-a)+abs(d-b)?

The path along the column b i.e abs(c-a) and path along the row c i.e abs(d-b) is the minimum path between (a,b) and (c,d). Therefore, X = abs(c-a)+abs(d-b).

If Tom can reach Jerry in exactly X moves then he can also reach in exactly X+2, X+4, X+6... But why ?

If Tom can reach Jerry in exactly X moves then he can also reach Jerry in X+2, X+4, X+6... If he wants to reach Jerry in exactly Z moves where Z is integer just greater than X, then he would need minimum 2 other cells to reach Jerry. If he requires 2 cells, then he can repeat the path back and forth and that will basically be **even multiple** of 2. Therefore he can reach Jerry in exactly X+Y, where Y is an even multiple of 2.

Letβs take an example to understand better.

- Let (a,b)=(1,1) and (c,d)=(2,4).
- The minimum path is (1,1) β (1,2) β (1,3) β (1,4) β (2,4). Therefore X=4. Now letβs try another path that needs exaclty Z moves, where Z is number just greater than X. Try it with Z=5, and youβll see that there is
**no such path**to reach (2,4). Now letβs try with Z=6, here we can see that we have multplie paths like :- (1,1) β (1,2) β (1,3) β (1,4) β (1,3) β (1,4) β (2,4).
- (1,1) β (1,2) β (1,3) β (1,4) β (1,5) β (1,4) β (2,4).
- (1,1) β (1,2) β (1,3) β (2,3) β (1,3) β (2,3) β (2,4).
- Similarly, we can find that there are multiple such paths to reach (2,4) in exactly Z=6 moves.

Hence, given K we need to check if it is greater than equal to X and also if they have the same parity or not, that can be checked using modulo 2 i.e X%2==K%2.

# TIME COMPLEXITY

The time complexity is O(1) per test case.

# SOLUTIONS

## Setter's Solution

```
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
const int maxn = 1e5, maxm = 1e5, maxt = 1e5, maxk = 2e5;
const string newln = "\n", space = " ";
int main()
{
int t; cin >> t;
int a, b, c, d, k;
while(t--){
cin >> a >> b >> c >> d >> k;
int dist = abs(c - a) + abs(d - b);
string ans = (k >= dist && (k - dist) % 2 == 0 ? "YeS" : "nO");
cout << ans << endl;
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
void solve() {
ll a, b, c, d, k;
cin >> a >> b >> c >> d >> k;
assert(a != c || b != d);
ll move = abs(a - c) + abs(b - d);
if(k >= move && k % 2 == move % 2) {
cout << "YES\n";
}else {
cout << "NO\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
```

## Editorialist's Solution

```
#include<bits/stdc++.h>
using namespace std;
#define int long long int
void solve()
{
int a, b, c, d, k;
cin >> a >> b >> c >> d >> k;
//minimum moves required
int X = abs(c - a) + abs(d - b);
// Checking minimum and parity condition
if (k >= X && k % 2 == X % 2)
{
cout << "YES" << endl;
return;
}
cout << "NO" << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
```