BOX2 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are two boxes, having X and Y stones, respectively.
You want the absolute difference between the number of stones in the boxes to equal K.
In one move, you can transfer a single stone from one box to another.
Find the minimum possible number of moves needed to achieve your goal, or decide that it’s impossible no matter what.

EXPLANATION:

Let d = |X-Y| be the difference between the stone counts. We want to make this equal K.

Note that in one move, we either increase X by 1 and decrease Y by 1, or vice versa.
This means d will change by either +2 or -2.

In particular, the parity of d won’t change: i.e. if it’s initially even it cannot become odd and vice versa.
So, if d and K don’t have the same parity, it’s impossible to achieve our goal.

Now, suppose d and K have the same parity.
We saw d can change by two at a time. So, the number of changes needed equals \frac{|d-K|}{2}.

However, there is one edge case: the total number of stones doesn’t change, and we can’t have negative stones; so the maximum allowed difference is X+Y (when one of the boxes is empty).
So, if K \gt X+Y it’s again impossible to achieve our goal; otherwise the answer is \frac{|d-K|}{2}.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y, k = map(int, input().split())
    dif = abs(x-y)
    
    if (dif - k) % 2 == 0 and k <= x+y:
        print(abs(dif - k) // 2)
    else:
        print(-1)
1 Like