BINARYSUM - Editorial

PROBLEM LINK:

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

Author: mathmodel
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

cakewalk

PREREQUISITES:

None

PROBLEM:

Given N and K, does there exist a binary string of length N whose sum is K, and S_i \neq S_{i+1} for every index 1 \leq i \lt N?

EXPLANATION:

The condition S_i \neq S_{i+1} restricts our choices for strings quite heavily: since the string must be a binary string, the only possible options are 0101010\ldots and 101010\ldots
That is, the string must alternate between 0's and 1's, though it can start with either of them.

Since there are only two possible strings, check if either of them satisfy the condition, which is easy enough in \mathcal{O}(N) time.


It’s also possible to solve the problem in constant time.
Note that in an alternating string, the number of zeros and ones will be almost equal - if N is even the counts will be equal (and so be \frac N 2); and if N is odd the counts will differ by 1, meaning one count will be \frac{N-1}{2} and the other will be \frac{N+1}{2}.

Note that the sum of a binary string is simply the number of ones in it.
So,

  • If N is even, a valid string exists if and only if K = \frac N 2.
  • If N is odd, a valid string exists if and only if either K = \frac{N-1}{2} or K = \frac{N+1}{2}.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

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