EQUALIZEAB - Editoriale

PROBLEM LINK:

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

Author: Utkarsh Gupta
Tester: Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

1069

PREREQUISITES:

Basic math

PROBLEM:

You are given A, B, and X. In one move, you can increase either A or B by X and reduce the other by X. Is it possible to make A equal to B?

EXPLANATION:

It is possible to make A and B equal if and only if 2X divides A-B.

Proof

Note that making any move does not change the value of (A-B) modulo 2X, since:

  • (A+X) - (B-X) \equiv A-B + 2X \equiv A-B \pmod {2X}
  • (A-X) - (B+X) \equiv A-B - 2X \equiv A-B \pmod {2X}

If A = B eventually, then of course A-B must be 0 modulo 2X, i.e, 2X divides A-B.

Also, if 2X divides A-B, then A and B can be made equal as follows:

  • If A = B, nothing needs to be done
  • If A \gt B, add X to B and subtract X from A
  • If A \lt B, add X to A and subtract X from B

In either case, A and B are brought closer together by 2X. Since their difference is a multiple of 2X, eventually they will become equal.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    a, b, x = map(int, input().split())
    print('Yes' if (a-b)%(2*x) == 0 else 'No')