PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Akash Bhalotia
Tester: Felipe Mota
Editorialist: Vichitr Gandas
DIFFICULTY:
SIMPLE
PREREQUISITES:
Observation
PROBLEM:
Given n \times m grid. A thief is trying to escape from a policeman. The thief is currently in cell (x,y) in the grid, while the policeman is in cell (a,b).
The thief needs to reach the cell (n,m) to escape. In one second, the thief can move either right, or down. The policeman can move right, or down, or (right + down) or stay in same cell in one second.
The policeman catches the thief if he’s in the same cell as the thief at any point of time, and he had reached that cell strictly before the thief. Find if the thief shall escape, or not, if both of them move optimally.
QUICK EXPLANATION:
Just calculate minimum time for thief and policeman to reach the cell (n, m) . Lets say policeman takes T_{police} and thief takes T_{thief} time to reach the cell (n,m). Now if T_{police} < T_{thief}, policeman will catch him.
EXPLANATION:
Thief is initially at the cell (x,y). It can move one step only in right or down in one second. Lets say it takes T_{thief} time to reach the cell (n,m) then
T_{thief} = (n-x) + (m-y)
Policeman is initially at the cell (a,b). It can move one step in right or down or (right + down) in one second. Lets say it takes T_{police} time to reach the cell (n,m) then
T_{police} = max(n-a, m-b)
Why
Because policeman will first move (right + down) as many steps as it can. Then left over steps either in right or down depending on the situation whether he ends up in last row or last column respectively.
Finally we can compare the times thief and policeman took to reach the cell (n,m). If T_{police} < T_{thief} then the thief is caught.
Why we check for only last cell?
Lets say policeman is able to catch the thief at a cell (p,q). Now lets calculate the time taken for thief and policeman to reach the cell (n,m) from the cell (p,q).
T_{thief} = (n-p) + (m-q)
T_{police} = max(n-p, m-q)
Observe that max(n-p, m-q) \leq (n-p) + (m-q) hence T_{police} \leq T_{thief}.
If policeman caught the thief at the cell (p,q) that means he had reached at the cell (p,q) before the thief. In this case, policeman will also be able to reach at the cell (n,m) before the thief because T_{police} \leq T_{thief}. Hence policeman will also be able to catch him at cell (n,m). Hence we can directly check for the cell (n,m) only.
TIME COMPLEXITY:
O(1) per test case
SOLUTIONS:
Setter's Solution
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
public static void main(String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
int T=Integer.parseInt(br.readLine().trim());
StringBuilder sb=new StringBuilder();
while (T-->0)
{
String[] s=br.readLine().trim().split(" ");
N=Integer.parseInt(s[0]);
int M=Integer.parseInt(s[1]);
s=br.readLine().trim().split(" ");
int x=Integer.parseInt(s[0]);
int y=Integer.parseInt(s[1]);
s=br.readLine().trim().split(" ");
int a=Integer.parseInt(s[0]);
int b=Integer.parseInt(s[1]);
int T1=(N-x)+(M-y);
int T2=Math.max(N-a,M-b);
sb.append(T1<=T2?"YES\n":"NO\n");
}
System.out.println(sb);
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = readIntLn(1, TEN(5));
while(t--){
int n = readIntSp(3, TEN(5)), m = readIntLn(3, TEN(5));
int x = readIntSp(1, n), y = readIntLn(1, m);
int a = readIntSp(1, n), b = readIntLn(1, m);
assert(x != n || y != m);
assert(a != n || b != m);
assert(x != a || y != b);
auto dist_thief = [&](int tx, int ty){
return abs(x - tx) + abs(y - ty);
};
auto dist_policeman = [&](int tx, int ty){
return max(abs(a - tx), abs(b - ty));
};
cout << (dist_thief(n, m) <= dist_policeman(n, m) ? "YES\n" : "NO\n");
}
assert(getchar() == -1);
return 0;
}
Editorialist's Solution
/***************************************************
@author: vichitr
Compiled On: 23 Apr 2021
*****************************************************/
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n, m, x, y, a, b;
cin >> n >> m >> x >> y >> a >> b;
int t_thief = n - x + m - y;
int t_police = max(n - a, m - b);
if(t_police < t_thief)
cout <<"NO\n";
else
cout << "YES\n";
}
signed main()
{
int t = 1;
cin >> t;
for(int i = 1; i <= t; i++)
{
solve();
}
return 0;
}
Evidently that is the case. In my Java implementation, I switched from using Scanner to BufferedReader, and it worked. It made it much longer, but this will be an important note for the future. 