PROBLEM LINK:
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
}
?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