# LKDNGOLF - Editorial

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

Simple

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

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.

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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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

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

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).

2 Likes

Simple JAVA code.

``````  public static void main (String[] args) throws java.lang.Exception
{
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 {
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

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;
``````

}