SANTACHOC - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

1285

PREREQUISITES:

None

PROBLEM:

N children have some chocolates, the i-th of them having A_i chocolates initially.
Can the chocolates be redistributed such that each child has at least one, and no two children have a difference of \gt K in their chocolates?

EXPLANATION:

Since we’re allowed to freely redistribute the chocolates, the initial A_i values don’t really matter: the only thing we care about is S = A_1 + A_2 + \ldots + A_N, the total number of chocolates.

First, let’s satisfy the condition that each child receives at least one chocolate, by giving one to each child.
If S \lt N this is impossible and the answer is No, otherwise we’re left with S - N chocolates to distribute.

Notice that it’s always possible to make the maximum difference between two children be \leq 1, by just giving chocolates in order and cycling around.
That is, give a chocolate to child 1, then to 2, then to 3, and so on till you reach N. Then restart the process from 1 again; and continue this till you run out of chocolates.

So, if S \geq N and K \geq 1, the answer is immediately "Yes".
That only leaves the case when S \geq N and K = 0.
However, K = 0 means that all the children should have an equal number of chocolates.
There are S chocolates in total, so the only way this is possible is if each one receives \frac{S}{N} of them - which requires \frac{S}{N} to be an integer, i.e, N should divide S.

Putting everything together:

  • Let S = sum(A_i).
    If S \lt N, the answer is "No".
  • If S \geq N and K \geq 1, the answer is "Yes".
  • If S \geq N and K = 0, the answer is "Yes" if N divides S and "No" otherwise.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    chocolates = sum(list(map(int, input().split())))
    if k == 0: print('Yes' if chocolates%n == 0 and chocolates > 0 else 'No')
    else: print('Yes' if chocolates >= n else 'No')
1 Like
2

Here’s a code in C++

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int T;
	cin >> T;
	while(T--){
	    int N, k;
	    cin >> N >> k;
	    int sum = 0;
	    for(int i = 0; i < N; i++){
	        int num; cin >> num;
	        sum += num;
	    }
	    
	    if(sum < N){
	        cout << "NO\n";
	    }
	    else if(sum == N){
	        cout << "YES\n";
	    }
	    else{
	        int R = sum - N;
	        if(R < N){
	            if(k >= 1){
	                cout << "YES\n";    
	            }
	            else{
	                cout << "NO\n";
	            }
	        }
	        else if(R == N){
	            cout << "YES\n";
	        }
	        else{
	            int r = (R % N);
	            if(r == 0){
	                cout << "YES\n";
	            }
	            else{
                    if(k >= 1){
    	                cout << "YES\n";    
    	            }
    	            else{
    	                cout << "NO\n";
    	            }
	            }
	        }
	    }
	}
	return 0;
}

It’s certainly not the best implementation out there, as I just wrote whatever first came to my mind.
Hope it helps.

1 Like