CVDRUN - Editorial

PROBLEM LINK:

Division 1
Division 2

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

Can you explain how you reached this equation? I mean which property of modulus is to be used to reached this conclusion? Thank you.

here is my code working fine. Can someone suggest any optimal solution?
#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
long long t,n,k,x,y,ans=0;
bool a;

cin>>t;
while (t--)
{
    cin>>n>>k>>x>>y;
    bool a=false,b=false;
    for(int i=x;!a;i=(i+k)%n){
        if(i==y){
            a=true;
        }
        if(b){
          if(i==x){
            break;
        }
        }
        if(i==x){
            b=true;
        }
    }
    if(a){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }

}

return 0;

}

Actually a time complexity of O(N), is also sufficient to solve the problem.
Of course O(\log N), is much more optimal, but O(N), is enough to solve the test case. The idea is that the city \text{CORONA VIRUS} started with will be repeated after N jumps, no matter what the value of X is.
Here is my solution:(for C++):

#include <bits/stdc++.h>
using namespace std;

bool tester(int arr[])
{
    int N,K,X,Y;
    N = arr[0]; K = arr[1]; X = arr[2]; Y = arr[3];
    int current_city = X;
    for(int i = 0; i < N; i++)
    {
        if(Y == current_city)
        {
            return true;
        }
        current_city = (current_city + K)%N;
    }
    return false;
}

int main() {
	int T;
	cin >> T;
	int touch[T][4];
	for(int i = 0; i < T; i++)
	{
	    int n,k,x,y;
	    cin >> n >> k >> x >> y;
	    touch[i][0] = n;
	    touch[i][1] = k;
	    touch[i][2] = x;
	    touch[i][3] = y;
	    if(tester(touch[i]))
	    {
	        cout << "YES\n";
	        
	    }
	    else{cout << "NO\n";}
	    
	}
	
	return 0;
}