TANDJ1 - Editorial

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