BALLBOX - Editorial

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