CATHIEF - Editorial

PROBLEM LINK:

Contest

Setter : Utkarsh Gupta
Tester : Rahul Dugar
Editorialist : Rajarshi Basu

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You are a policeman and want to catch a thief. Both can move only on the x-axis.

Initially you are at coordinate (x,0) and the thief is at coordinate (y,0). After each second both you and the thief will move left or right by \textbf{exactly k simultaneously}. No one can go left of (0,0) or right of (n,0), n \leq 10^9. Will you be able to catch the thief if you move optimally. If the policeman and thief are at same coordinate at same time, then the thief is caught. You have to answer T \leq1000 such queries.

BRIEF EXPLANATION

one-liner version
  • YES iff 2*k | (|x-y|) , NO otherwise.

EXPLANATION

Observation 1

Since both can move only in jumps of k steps, the police will only ever be able to catch the thief if \exists \ n, x + n*k = y.

Observation 2

What about them overtaking each other? Well, try the example where x = 2, y = 4, k = 2. Then if the policeman tries to go to x = 2 + 2 = 4, then the thief can kind-of skip and go to y = 4 - 2 = 2. What does this suggest?

Final solution

The police will only be able to catch the thief if k divides their separation. However, if the separation is an odd multiple, then they can “skip/jump” over each other simultaneously. Hence, they must be separated by an even multiple of k. Now go check the brief explanation, it should make more sense.

SOLUTION:

Tester’s Code
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
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,' ');
}
 
void solve() {
//	int x=readIntSp(0,1000000000),y=readIntSp(0,1000000000),k=readIntSp(1,1000000000),n=readIntLn(1,1000000000);
	int x,y,k,n;
	cin>>x>>y>>k>>n;
	assert(x<=n&&y<=n&&k<=n&&x!=y);
	if(abs(x-y)%(2*k)==0) {
		cout<<"Yes"<<endl;
	} else
		cout<<"No"<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
//	int t=readIntLn(1,1000);
	int t;
	cin>>t;
	fr(i,1,t)
		solve();
//	assert(getchar()==EOF);
#ifdef rd
//	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

VIDEO EDITORIAL (English):

VIDEO EDITORIAL (Hindi):

1 Like

Who gave the idea to keep
YES NO in first q and
Yes No in second :sweat_smile: :sweat_smile: :sweat_smile:

15 Likes

lol :joy:

1 Like

Nice catch. There should be consistent system for all Yes/No problems. CF allows case insensitive yes/no. Atcoder always Yes/No. CC should also make a consistent system and do that for all yes/no problems.

6 Likes

Also, it’d better if our solution is judged on samples first and then hidden test cases (if it passes samples) and we are explicitly told if our solution fails sample and we don’t get any penalty for failing samples.
Tagging @admin if they could add this feature.

8 Likes

https://www.codechef.com/viewsolution/40661262
Why is this wrong? I kept submitting this only to get WA, got frustrated and left the contest. I shouldn’t have done that but now can anyone explain :sweat_smile: :sob:?Does it matter if we check divisibility by 2k or check individually by k and then 2 later? UPD:: I missed a new line and hence got 3 WAs in the contest, got frustrated in the end and left. Lesson learnt :sob:

1 Like

I feel you understood the question in the wrong way. Try spending more time on the question, you will definately get AC on your next try.

1 Like

Bruh… I just realized this is the reason my submissions gave WA during the contest.

1 Like

Did you figure out why abs(x - y) % (2*k) == 0 is different from
(abs(x - y) % 2 == 0 and abs(x - y) % k == 0) ? I am getting WA using the later.
https://www.codechef.com/viewsolution/40679228

POOR TEST CASE
My O(N) solution got AC what is going on.
test case: x=0 y=10^9 k=1 n=10^9

 /*
    Author : MAYANK MOHAK
    Date   : DEC 2020
    For    : codechef-learn-dsa-challenge
*/
#include<bits/stdc++.h>
using namespace std;
#define ll              long long int
#define fin(i,s,e)      for(ll i=s;i<=e;i++)
#define fde(i,s,e)        for(ll i=s;i>=e;i--)
#define onedv(data_type, name)   vector<data_type> name
#define twodv(data_type, name, n) vector<vector<data_type>> name(n)
#define pi              3.1415926535897932384626
#define endl            '\n'
#define uomp(data_data_type, value_data_type, name) unordered_map<data_data_type, value_data_type> name 

int main(){
    int test;cin>>test;
    while(test--){
      ll x,y,n,k,temp;
      cin>>x>>y>>k>>n;

      if(x<y){
        temp=x;
        x=y;
        y=temp;
      }
      temp=x;
      for(ll i=0;temp>=y;i++){
        if(temp==y && i%2==0) { 
          cout<<"Yes\n"; 
          break;
        }
        if(temp==y+k && i%2==1) { 
          cout<<"Yes\n"; 
          break;
        }
        temp-=k;
      }
      if(temp<y){
        cout<<"No\n";
      }
    }    
    return 0;
}

6 is divisible by 2 and 6 both but not by 12

1 Like

Can someone help me solve the same problem with a minor variation. Based on the conditions of the current problem, they are not allowed to move left when the position is between 1 and k-1 and not allowed to move right when the position is between n-k+1 and n-1. What happens if we allow those moves but are stopped at the boundaries, that is one can move from between 1 and k-1 to 0 and from between n-k+1 and n-1 to n. Any thoughts on what the optimal strategy would be?

1 Like

Can Some one help me why my code is wrong its giving me WA but i passed all the test case written in the question. Here is my code My Code

What i have done is that i have taken min value to be distance of police and max distance of thief and then i did x + x + k for police and y = y - k for thief if x and y are equal i print yes else no so what is wrong in my solution please help me

You are using “YES”,“NO” while the problem expects “Yes”,“No”. Changing that should fix it.

Hi people!

Solution: 40741219 | CodeChef (WA)
Solution: 40741237 | CodeChef (AC)

var diff = x-y;
The difference is -
diff /= 2;
check - diff%k
&,
check - diff%(2*k)

I didn’t get, how are these two different?

The word “optimally” ruined the question for me

haha
just because of this i was getting wa agan and again.

@chenreddy I was also thinking for the same, In that case answer will vary according to N.
N is divisible by 2*k or not will lead us to lots of different cases.