TANDJ1 - Editorial

Setter: Daanish Mahajan
Tester: Riley Borgard
Editorialist: Aman Dwivedi

Cakewalk

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


4 Likes

Oh! I figured that if dist is odd then k has to be odd and vice versa but I forgot the cases where k < dist, thats why my code did not work, what a silly mistake.

8 Likes

Same bro I was figuring out what went wrong with my code as my idea was the same that if dist is odd and k is odd or vice-versa it should say yes but even I missed the case where k<dist

1 Like

Great Editorial !!

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner scn=new Scanner(System.in);
int t=scn.nextInt();
while(t–>0){
int a=scn.nextInt();
int b=scn.nextInt();
int c=scn.nextInt();
int d=scn.nextInt();
int k= scn.nextInt();
int sm=Math.abs(d-b) + Math.abs(c-a);
if(k>=sm && k%2==sm%2){
System.out.println(“Yes”);
}

	     else{
System.out.println("No");
}

}
}


}

here is my solution to the problem in java and I’m facing issues with the solution i.e TLE

Hey @anon25577912 ,
your code is giving TLE because of the input method you have chosen.Scanner class is slow.
You can go through this link it’ll help you a lot.

1 Like

thanks sir.