TANDJ1 - Editorial


Contest Division 1
Contest Division 2
Contest Division 3

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






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


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.


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.


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


Setter's Solution
# 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;
        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() {
    int te;
    cin >> te;
    while(te--) solve();
Editorialist's Solution
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;
  cout << "NO" << endl;
int32_t main()
  int t;
  cin >> t;
  while (t--)
  return 0;

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.


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();
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){



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

Hey @anon25577912 :wave: ,
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.