DSTAPLS - Editorial

PROBLEM LINK:

Div1
Div2
Practice

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 :smiley:

  • 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 YES if final configuration is same no matter how minute candidate puts apples. Discuss if a YES NO solution 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 :stuck_out_tongue:

20 Likes

Can’t stop laughing :joy::joy:… Just can’t :joy::joy: Apart from awesome editorials, @vijju123 also has an amazing sense of humor

6 Likes

why in all editorial tester programs are in kotlin?
should I switch to kotlin for solution of problems?

Kotlin: papa ko bolo horlicks pilaye
Others: beer

Why shouldn’t they? Also the setter’s solution is in C++. Understanding either of them is more than enough ig.

I found a simple pattern for this problem.

For three cases namely:

  • K = 1 (there is only one box)
  • N = K^2 and
  • N = x*( K^2) (N is multiple of square of K)

The distribution of apples would be same. Beginner’s luck or simple math?
Seeing the explanation my approach seems legit!

can’t agree more XD \hspace{0mm}.

Why am I wrong to apply that if ( (n/k)%k==0) then output is “NO” otherwise output is “YES” ?

1 Like

The question asks if final configuration is same or not. You switched conditions for YES and NO.

Sir, the exact statement stated in the problem is as below
" For each test case, print a single line containing the string "YES" if the final distributions of apples can be different or "NO" if they will be the same (without quotes). "

Nice one simple but I am a dumb and haven’t identified the logice even after solving many test cases (I have tried many cases for this problem), I couldn’t get exact logic of this, I wan’t satisfied with the editorials explanation and was ready ask a question to Vijju bhai.

But when I typed last line of the following block then I realized why you have considered it as k*k.
Thanks for the editorial :wink:

{@vijju123 will you please explain the case when N=12 and K=3

on minute 1:
person1 : 1 | 1 | 1
person2 : 3 | 0 | 0

on minute 2:
person1 : 2 | 2 | 2
person2 : 3 | 3 | 0

on minute 3:
person1 : 3 | 3 | 3
person2 : 3 | 3 | 3

on minute 4 (final minute) :
person1 : 4 | 4 | 4
person2 : 6 | 3 | 3 }

This was my solution on challenge days :joy:

for _ in range(int(input())):
n,k = map(int,input().split())
if k==1 or n==1:
    print('NO')
elif n==k or n<k:
    print('YES')
else:
    f=True
    while n>k:
        n=n/k
        if n%k==0:
            f=False
            break
    if f:
        print('YES')
    else:
        print("NO")
1 Like

@vijju123 advantage of python over c++ is calculating the k^2.if we calculate k^2 in c++ it will SIGFPE

Right. Sorry, my bad! :stuck_out_tongue: I got confused haha.

Can you give me submission link? Your condition is correct, but your latest submission in python ( https://www.codechef.com/viewsolution/25883245 ) gets a TLE coz you are making a list of size k

Yessssss. :smiley:

If you try to calculate k^2 in C++, you will get overflow and hence undefined behavior - which may (or may not :stuck_out_tongue: ) result in SIGFPE.

What part do you think could have been better? :slight_smile:

I think you no longer need me to explain the test case - because what you wrote is correct!

The main thing to realize is that, equality can be achieved only after putting K^2 applies at time t=0,K,2*K,3*K... minutes

1 Like

Yeah , I tried to do differently but my previous solutions were based on the logic stated here

Solution link please? :slight_smile:

Here is the link:
https://www.codechef.com/viewsolution/25882552

Replace n/k with n//k .

In python / operator performs floating point division which can lead to precision errors if numbers are large. Hence your n/k does not get accurate value.

// is integer division and gives correct precision.

Okay , I got it !
Thank you sir .