TANDP - Editorial

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

This seems unreasonable:

  • Status: Time Limit Exceeded
  • Time: 0.00 sec
  • Solution: 45414771
1 Like

In the 24th line, Math.max(N - a, M - b) should be there.

3 Likes

Great! Thanks for keeping it simple!

I have tried the exact same approach (atleast I believe that), yet I’ve faced the Wrong Answer verdict.

Here’s the direct link to my Python 3 submission for the problem: Solution: 45393384 | CodeChef

Can anyone please provide me a testcase for which it is failing, or any other error if spotted will be highly appreciated. :pray:

Update: The issue has been resolved. It was the wrong order of inputs that trapped me. I thought x, a and y, b were given, instead of x, y and a, b. The line from constraints had reset me. :sweat_smile:
I will try to stay awake in the next one (i.e., April Lunchtime) :grin:

Why is using distance between two points(((x1-x2)^2)+(y1-y2)^2)^1/2) for police wrong?
I used this in the contest and got WA. I translated the points to the original x-axis,y-axis during this.
For thief, I calculated using((n-p) + (m-q))

This is because of the described movement in the question. The police cannot break the right, down and diagonal movement to choose the displacement upto (N, M). Your formula would give displacement, while we meeded to account for the step by step distance (per unit time).

Police can only travel in angles of 0, -45, and -90 degrees.
Note also that the number of moves from (0,0) to (100,100) is 100, but the distance from the formula is 141.

1 Like
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
	// your code goes here
	ll tc;
	cin>>tc;
	while(tc--){
		ll n,m;
		cin>>n>>m;
		ll x,y;
		cin>>x>>y;
		ll a,b;
		cin>>a>>b;
		ll ts=abs(x-n)+abs(y-m);
		ll ps=0;
		ll tx,ty;
		if(a!=n && b!=m){
			ll tx=a+min(abs(n-a), abs(m-b));
			ll ty=b+min(abs(n-a), abs(m-b));
			ps=min(abs(n-a), abs(m-b));
			ps+=(abs(n-tx)+abs(m-ty));
		}
		else {
			ps+=(abs(n-a)+abs(m-b));
		}
		if(ps<=ts){
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
		}
		
	}
	return 0;
}

Could someone please tell me what is wrong with my code ? I have calculated steps for policeman as max steps he could go in diagonal way + straight steps for the rest of the journey. Someone kindly point out what is wrong with this.

test cases are quite high you should use fast input and output…

1 Like

Thank you. :smiley: 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. 45431543

In simple terms, Since both the players are playing optimally, both of them will try to reach cell (N, M) whoever reaches the cell first, wins the game.

Now the problem boils down to finding the smallest distance from both the points to cell (N, M)

2 Likes

Can anybody help me with this?
Same logic
Got AC in C++ Solution
But getting TLE in JAVA??? Solution
I generally do code in java And i was thinking in mid of contest may be my approach is incorrect
and when i saw code of other peoples post contest my mind is blown up…

1 Like

Use Fast IO

why it’s showing wrong answer even though passing mentioned testcases…

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--){
        int n,m,x,y,a,b;
        cin>>n>>m>>x>>y>>a>>b;
        int tp=0,tc=0;
        if(a==b){
            tp+=(n-a);
        }
        else{
            (a==n)?tp+=(m-b):tp+=(n-a);
        }
        tc+=(n-x)+(m-y);
        if(tp<tc) cout<<"NO"<<"\n";
        else 
        cout<<"YES"<<"\n";
    }
}

Plzzz anybody give reason…!!1

This seems wrong.
What if a \neq n but m-b > n-a? You are doing tp+=(n-a) in this case which is wrong. You should do tp = max(n-a, m-b) instead.

Just curious, in your Java solution, you have written a function to swap Integers.

public static void swap(int a, int b){
    int temp=a;
    a=b;
    b=temp;
}

Do you really think this function swaps Integers :neutral_face:

haha! yes you are right , definitely it is not gonna swap integers
i have just written to use it for another purpose

can anybody tell me what’s wrong with my code.
I had done exactly same but getting wrong answer error.

#include (iostream is not shown here because of #)
using namespace std;

int policedp(int n,int m,int a,int b)
{
int x = n-a;
int y = n-b;
if(x>y)
return x;
else
return y;
}
int thiefdp(int n,int m,int x,int y)
{

return (n-x+m-y);

}
int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
int x,y;
cin>>x>>y;
int a,b;
cin>>a>>b;

    int police = policedp(n,m,a,b);
    int thief = thiefdp(n,m,x,y);
    
    if(police<thief)
    cout<<"NO\n";
    else
    cout<<"YES\n";
}
   
return 0;

}

int x = m - a;
int y = n - b; //(may be)

can someone explain whats wrong in this
https://www.codechef.com/viewsolution/46092128