ADD13 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: satyam_343
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given N and M.
Starting from 0, you will do the following exactly N times:

  • Add either 1 or 3.

Is it possible to end up with exactly M?

EXPLANATION:

We have N additions, each of which is either +1 or +3.
Suppose X of them are +3, and the remaining N-X are +1.
Then, our final value will equal

1\cdot (N-X) + 3\cdot X = N + 2X

We can freely choose X, as long as it’s between 0 and N.
Thus, by choosing X = 0, 1, 2, \ldots, N, the set of values we can reach are:

N, N+2, N+4, \ldots, N+2N

That is, we start at N and can then form every value of the same parity as N, till N+2N = 3N.

So, all we need to do is check if M satisfies this condition.
That is, M must satisfy:

  • N \le M \le 3N
    M must lie between the minimum and maximum possible values.
  • (M - N) must be even.
    This is because we can only form elements of the form N + 2X.

If both conditions are satisfied, the answer is Yes. Otherwise, it’s No.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    print('Yes' if n <= m <= 3*n and n%2 == m%2 else 'No')
1 Like