PROBLEM LINK:
Setter- Yulian
Tester- Suchan Park
Editorialist- Abhishek Pandey
DIFFICULTY:
Simple
PRE-REQUISITES:
Observations, Simple Maths
PROBLEM:
Given N apples and K boxes, he has 2 candidates who fill the boxes as following-
- Every minute, first candidate puts 1 apple in each of the K boxes.
- Every minute, the second candidate puts K apple in the box with least number of apples
We need to tell if the final configuration of apples filled by both candidates will be same or not.
QUICK-EXPLANATION:
Key to AC- Configuration can be equal only at time t=K,2K,3K...\& etc. Make sure you have enough apples so that all applies are exhausted at these favorable values of t.
Realize that since first candidate puts 1 apple in each box every minute, while the second candidate puts K apples at once in the box he choses. The configuration can only be same at a time t such that t is a multiple of K. This puts a restriction that N must be divisible by K^2 so that all apples are exhausted only at such favorable t.
EXPLANATION:
This editorial will have 2 sections -
- Proof that final configuration is same only at time t=K,2K,3K.... \&etc
- How to use the above proof to arrive at a solution.
Proof on when final configuration is same.
I will give 2 point of view, or perspective for the proof. Each point of view is based on deriving the proof by looking at actions of a candidate.
-
The first candidate puts 1 apple in each of the boxes, while second candidate puts K apples in a box per minute. This also implies that, number of apples the second candidate has put in some box is always a multiple of K (as he puts K apples every time!) Now, the final configuration can only be same if the number of apples put in by first candidate is also a multiple of K. This can occur only if time t is a multiple of K, as the first candidate puts just 1 apple per minute. Since t must be a multiple of K as proved just now, let t=i*K where i is some integer. Now, since the number of boxes is also K, the second candidate has filled each of the K boxes with K*i apples. Also, the first candidate puts 1 apple every minute, and hence has also filled all boxes with K*i apples. Hence the final configuration is same at t=K*i for all integral values of i.
-
The alternate perspective of proof his from point of view of second candidate. In first minute, the first candidate has filled all boxes with 1 apple. Now, the final configuration can only be same iff the second candidate also fills all the boxes - else its obvious that final configuration is different. This is possible only if t is a multiple of K.
How to use above proof
Now, we know that final configurations are same at t=i*K where i is some integer. This imposes a very nice restriction on N.
The restriction is that N must be such that all N apples are exhausted at time t=i*K. We also know that each minute K apples are being used by each candidate! This means the total number of apples N, such that all apples are used at t=i*K is N=K*(i*K)=i*K^2.
This means that N must be divisible by K^2.
A solution in python, or one using big integer library in JAVA etc can comfortably do it. For C++, where support for numbers >2^{64} is not there by default, we will use below trick.
Now, since K\leq 10^{18} hence squaring K will cause overflow. The usual procedure to then check if N is divisible by K^2 is to first check if N \%K==0 and then check that (N/K) \% K==0. Since its given that N is always a multiple of K, we just need to check if (N/K) \% K==0. If its true, then the configurations are same - else they are not!
SOLUTION
Setter
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) {
ll n,k;
cin>>n>>k;
if((n/k)%k==0) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
Tester(KOTLIN)
fun main(Args: Array<String>) {
repeat(readLine()!!.toInt()) {
val (N, K) = readLine()!!.trim().split(" ").map{ it.toLong() }
require(N in 1L..1000000000000000000L)
require(K in 1L..1000000000000000000L)
println(if(K <= 1000000000L && N % (K * K) == 0L) "NO" else "YES")
}
}
Time Complexity=O(1) per test case
Space Complexity=O(1) per test case
CHEF VIJJU’S CORNER 
-
Solve the following variants of the problem-
- N is not necessarily a multiple of K
- The second candidate puts K apples in a random box instead of the box with minimum apples. In this case, print
YESif final configuration is same no matter how minute candidate puts apples. Discuss if aYESNOsolution to this is even possible or not.
-
Explore a solution of this problem in python and realize why python has an advantage over C++ here.
Setter's Notes
Notice that the amount of apples in each box stays the same for the first employee. So the distribution can be the same only when apples are equally arranged in the boxes. For the second employee the arrangement is the same only in the end of every K-th minute.
So we just need to check whether the N is divisible by K^2 to get the answer (we takes K apples every minute, for K minutes).
For C++ users K^2 will result in overflow on the original constraints. But we know that N is divisible by K so we can first divide N by K and then check whether the result is divisible by K.
Related Problems
Liked the Editorial?
Dont forget to LIKE, COMMENT, SHARE AND SUBSCRIBE,and click the bell icon so you receive notification for every editorial 
) result in SIGFPE.