LKDNGOLF - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

Basic Maths

PROBLEM

Given N+2 tiles numbered from 0 to N+1 from left to right, there’s a hole at tile numbered x. A ball starting at tile 0, bounces at length k, visiting tiles 0, k, 2*k \ldots until the ball passes N+1. If the ball doesn’t enter hole, it starts from tile numbered N+1, jumps of length k towards left, visiting tiles (N+1), (N+1-k), (N+1-2*k) \ldots until it passes tile numbered 0.

Determine whether the ball enters the hole in its forward or backward journey, or not.

QUICK EXPLANATION

  • Ball enters hole in forward journey if x \bmod k = 0
  • Ball enters hole in backward journey if x \bmod k = (N+1) \bmod k

EXPLANATION

Subtask 1

We can simulate the movement of ball over tiles, starting from position 0 and incrementing position of ball by k at each step.

For reverse pass, we start at position N+1, decrementing the position of ball by k at each step.

Hence, there are at most 2*N iterations, solving the problem in O(N), which is sufficient for subtask 1, but not subtask 2.

Subtask 2

Let’s see which positions are visited by ball in forward journey. Only those tiles are visited, which are a multiple of k. So if x \bmod k = 0, ball enters hole in forward pass.

We can see that if we could somehow reverse the order of tiles, the backward pass becomes same as forward pass. That way, tile numbered 0 is labelled N+1, tile numbered 1 is numbered N, tile numbered p is labelled (N+1)-p.

This reverse problem is same as forward pass. The ball starts at 0, moving k steps at a time, visiting only those positions which are a multiple of k.

Hence, for position p in original numbering to be visited in backward pass, position (N+1)-p must be a multiple of k, or (N+1-p) \bmod k = 0 \implies (N+1) \bmod k = p \bmod k.

Hence, hole x is visited in backward pass if x \bmod k = (N+1) \bmod k.

Hence, we can check in O(1) whether the ball would be visited in forward or backward journey.

TIME COMPLEXITY

The time complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;
  
const int maxt = 1e5;
const string newln = "\n", space = " ";

int main()
{   
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    int n, x, k;
    while(t--){
        cin >> n >> x >> k;
        string ans = (x % k == 0 || (n + 1 - x) % k == 0) ? "YeS" : "No";
        cout << ans << endl;       
    }
} 
Tester's Solution
import java.util.*;
import java.io.*;
class LKDNGOLF{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), X = ni(), K = ni();
        pn((X%K == 0 || X%K == (N+1)%K)?"yEs":"nO");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new LKDNGOLF().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

2 Likes

GOOD EXPLAINATION

My C++ solution is like this:

#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--){
	    int n, x, k;
	    cin >> n >> x >> k;
	    if (x%k==0 || ((n+1)-x)%k==0){
	        cout << "YES" << endl;
	    }
	    else{
	        cout << "NO" << endl;
	    }
	}
	return 0;
}

For those who want to understand the logic behind it:

Let’s take a random test case:

1
6 3 2

On the forward iteration, we will get 0, 2, 4, 6, 8…(Check if 3%2==0 to see if condition satisfies), and on the backward iteration: 7, 5, 3, 1(Check if (6+1)-3%2==0 satisfies, as mentioned in the editorial).


From this, you will get your answer.

2 Likes

Simple JAVA code.

  public static void main (String[] args) throws java.lang.Exception
    	{
    		Reader sc=new Reader();
    		int t=sc.nextInt();
    		while(t-->0){
    		    int n=sc.nextInt();                       //no of tiles
    		    int x=sc.nextInt();                       //hole
    		    int k=sc.nextInt();                       //jumps
    		    
    		    int remainingTiles=(n+1)%k;
            	   if(x%k==0){
            	       System.out.println("YES");
            	   }else if( (x-remainingTiles)%k ==0 ){
            	       System.out.println("YES");
            	   }else{
            	       System.out.println("NO");
            	   }
    		}
    	}

I was able to score 90 points only but the logic is the same
and facing TLE in other 10 points
Anyone please tell how to remove that error
/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try {
// your code goes here
// your code goes here
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
int n,x,k;
for(int i=0;i<t;i++)
{
n = scan.nextInt();
x = scan.nextInt();
k = scan.nextInt();
if(x%k==0 || (n+1-x)%k==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
}
catch(Exception e) {
System.out.println(e);
}

}

}

I did the same :smiley: :smiley:

Kindly format your code.

I am getting wrong output while submission can someone tell me whats wrong with my code;

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

int main() {
int t;
cin>>t;

while(t--){
        int n , k , x;
        cin>>n>>x>>k;
        
        vector<bool> v(n+1);
        for(int i=0; i<=n+1 ; i+=k){
                v[i]=true;
        }
        for(int i=n+1 ; i<=0 ; i-=k){
                v[i]=true;
        }
        
        if(v[x]==true){
                cout<<"Yes"<<endl;
        }
        else
                cout<<"No"<<endl;
        
}
return 0;

}