CUREX - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have A_1 gold and B_1 silver coins.
They can be changed as follows:

  • Convert one gold coin to five silver coins, or vice versa.
  • Discard one gold coin and one silver coin.

Is it possible to end up with A_2 gold and B_2 silver coins?

EXPLANATION:

Observe that we’re able to freely transform between gold and silver coins, at a rate of 1:5.
So, we can think of each gold coin as having a “value” of 5 silver coins.

The initial value of coins with us is 5\cdot A_1 + B_1 silver coins, while we want to end up with a value of 5\cdot A_2 + B_2 silver coins.

The only option we have that actually changes the value, is the option to discard one gold coin and one silver coin.
In particular, this means we can only reduce the value of our coins, and never increase it.
So, if 5\cdot A_1 + B_1 \lt 5\cdot A_2 + B_2, it’s definitely impossible to end up with (A_2, B_2) coins.

Now, let’s look at how exactly the value reduces.
We discard one gold coin and one silver coin. The gold coin is worth 5 silver coins, so we’ve really discarded the equivalent of 6 silver coins from the overall value.

Since each time we discard a value of 6, the only values we can reach at all are those of the form

5\cdot A_1 + B_1 - 6\cdot k

for some integer k\geq 0.

Now, 5\cdot A_2 + B_2 must be of this form - which is only possible if (5\cdot A_1 + B_1) - (5\cdot A_2 + B_2) is divisible by 6.
If it’s not, again we know it’s impossible to end up with (A_2, B_2).

We now have a situation where two conditions are true:

  1. 5\cdot A_1 + B_1 \geq 5\cdot A_2 + B_2
  2. (5\cdot A_1 + B_1) - (5\cdot A_2 + B_2) is divisible by 6.

It’s in fact always possible to transform (A_1, B_1) into (A_2, B_2) under these conditions, as follows:

  1. First, transform all gold coins to silver coins. There are now 0 gold coins and 5\cdot A_1 + B_1 silver coins.
  2. Next, while the value of our coins is larger than 5\cdot A_2 + B_2, do the following:
    1. Transform five silver coins to one gold coin.
    2. Then, discard one silver and one gold coin.
    3. This reduces the value by exactly 6.
  3. Since we know (5\cdot A_1 + B_1) - (5\cdot A_2 + B_2) is divisible by 6, repeating the above process will eventually land us in a state where we have exactly 5\cdot A_2 + B_2 silver coins and 0 gold coins.
  4. Now, transform 5\cdot A_2 silver coins to gold, after which we’ll have A_2 gold and B_2 silver coins, as needed.

To summarize: the answer is “Yes” if 5\cdot A_1 + B_1 \geq 5\cdot A_2 + B_2 and (5\cdot A_1 + B_1) - (5\cdot A_2 + B_2) is divisible by 6, and “No” otherwise.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    a1, b1, a2, b2 = map(int, input().split())

    c1, c2 = 5*a1 + b1, 5*a2 + b2
    if c1 >= c2 and (c1 - c2)%6 == 0: print('Yes')
    else: print('No')
1 Like