PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester & Editorialist: iceknight1093
DIFFICULTY:
908
PREREQUISITES:
None
PROBLEM:
Alice and Bob initially have N and M problems, respectively.
Whenever Alice solves a problem, Bob receives one more problem.
Whenever Bob solves a problem, Alice receives three more problems.
Is there a way for them to solve problems in such a way that they have the same number remaining?
EXPLANATION:
Let d = N - M denote the difference in problems between Alice and Bob.
We want to make d = 0.
Looking at the options we have:
- When Alice solves a problem, N decreases by 1 and M increases by 1.
This decreases d by 2. - When Bob solves a problem, N increases by 3 and M decreases by 1.
This increases d by 4.
Notice that d can only be changed by even numbers.
In particular, if the initial value of d is odd, it can never be made into 0.
On the other hand, if the initial value of d is even, there is always a sequence of operations that turns d to 0.
How?
Suppose d is even.
First, let Alice solve every problem with her.
After this, she’ll have 0 remaining, and Bob will have N+M remaining (which is an even number).
Now, the current value of d is -(N+M).
Then, Bob can start solving problems, till we reach d \geq 0.
Since d increases by 4 each time, there are two possibilities:
- d = 0, in which case we’re done immediately.
- d = 2, in which case Alice can solve one problem and we’re done.
So, the answer is Yes if d is even and No otherwise.
TIME COMPLEXITY
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
print('Yes' if n%2 == m%2 else 'No')