DISTSUB - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

An island in a binary string is a maximal subatring of zeros.
You’re given N and K. Does there exist a binary string of length N that contains exactly K islands, all of distinct sizes?

EXPLANATION:

If there are to be K islands of distinct sizes, their smallest total length is 1 + 2 + \ldots + K, of course obtained by taking sizes 1, 2, 3, \ldots, K.

Further, the islands need to be separated by ones (otherwise they could be separated to form a larger island).
WIth K islands, we’d need at least K-1 ones to separate them: one between each pair.

So, for a binary string with K islands of distinct sizes, its length has to be at minimum

1 + 2 + \ldots + K + (K-1) = \frac{K\cdot (K+1)}{2} + (K-1)

If this length is \gt N, clearly no valid binary string exists.
If this length is \leq N, it’s always possible to create a valid binary string.
For example, start with

01001000100001\ldots 1\underbrace{000\ldots000}_{K\text{ times}}

and then simply keep appending 1 to it till the length reaches N.

tl;dr the answer is Yes if \frac{K\cdot (K+1)}{2} + (K-1) \leq N, and No otherwise.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    mnlen = k*(k+1)//2 + (k-1)
    print('Yes' if mnlen <= n else 'No')