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