PROBLEM LINK:
Author: Aryan Agarwal
Tester: Aryan Agarwal
Editorialist: Srikkanth
DIFFICULTY:
Cakewalk
PREREQUISITES:
Arrays
PROBLEM:
Given a circular array A, and integers X, Y,
starting from position X keep moving to position X + K (coming back to the first point when needed).
Will you ever reach position Y?
EXPLANATION:
There are only a finite number of cities, after some time, we will visit a city again.
After this point no new city will be visited and we will end up visiting the same cities again and again in a cycle.
We can implement this by keeping a visited array and stop after some position is visited already.
Finally if we visited position Y, answer is “YES”, otherwise “NO”.
This complexity of above method is \mathcal{O}(n) and is more than enough to get 100 pts, however I’d like to describe a more efficient solution, which wasn’t required because we intended this to be a cakewalk problem.
The position after t jumps is (X + kt) \mod n.
We need to find if there exists some integer t such that Y = (X + kt) \mod n
Which implies there is a pair of integers t, l such that X + kt = Y + nl
Rewriting this we get, X-Y = nl - kt
Observing the above equation, we know that rhs is divisible by gcd(n, k) (because this divides both n and k and hence the difference also)
Therefore X-Y should be divisible by gcd(n, k)
We can obtain the numbers t, l using extended euclid algorithm, so the above condition is sufficient.
Therefore the answer is “YES” if (X - Y) is divisible by gcd(n, k) otherwise “NO”.
This solution is \mathcal{O}(\log n)
TIME COMPLEXITY:
TIME: \mathcal{O}(\log n)
SPACE: \mathcal{O}(1)
SOLUTIONS:
Setter's Solution
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
private static long _gcd(long a, long b) {return a==0?b:_gcd(b%a,a);}
public static void main(String[] args) throws IOException
{
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().split(" ");
N=Integer.parseInt(s[0]);
int K=Integer.parseInt(s[1]);
int X=Integer.parseInt(s[2]);
int Y=Integer.parseInt(s[3]);
boolean[] vis=new boolean[N];
for(i=X;!vis[i];i=(i+K)%N) vis[i]=true;
sb.append(vis[Y]?"YES\n":"NO\n");
}
System.out.println(sb);
}
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)
clock_t start = clock();
const int N = 1e5 + 5;
void solve() {
int n, k, x, y;
cin >> n >> k >> x >> y;
assert(1 <= n && n <= 1000);
assert(0 <= x && x <= n-1);
assert(0 <= y && y <= n-1);
assert(0 <= k && k <= 1000);
y = abs(y - x);
if (y % __gcd(n, k) == 0) cout << "YES\n";
else cout << "NO\n";
}
int main() {
FASTIO;
int T = 1;
cin >> T;
assert(1 <= T && T <= 100);
for (int t=1;t<=T;++t) {
solve();
}
cerr << fixed << setprecision(10);
cerr << "Time: " << (clock() - start) / (CLOCKS_PER_SEC) << " secs\n";
return 0;
}