PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Testers: Utkarsh Gupta, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
994
PREREQUISITES:
None
PROBLEM:
You have N balls. Determine if they can be split into K boxes so that each box has at least one ball, and the boxes have distinct numbers of balls.
EXPLANATION:
The answer is “Yes” if and only if N \geq \frac{K(K+1)}{2}
Proof
Since the boxes must have a distinct number of balls, the minimum possible number of balls is 1 + 2 + 3 + \ldots + K = \frac{K(K+1)}{2}. So, we must definitely have N \geq \frac{K(K+1)}{2}.
On the other hand, suppose we have more than \frac{K(K+1)}{2} balls. Distribute them so that initially the boxes have 1, 2, \ldots K balls. Then, put all remaining balls into the last box (the one with K balls initially). This gives us a valid distribution, thus completing the proof.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
print('yes' if 2*n >= k*(k+1) else 'no')