You are not logged in. Please login at www.codechef.com to post your questions!

×

# GIVCANDY - Editorial

Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

Simple

# PREREQUISITES:

Greatest common divisors, Euclid's algorithm, Linear combinations, Bézout's identity

# PROBLEM:

Alvin has $A$ candies and Berto has $B$ candies. You can give $C$ candies to Alvin at a time, and $D$ candies to Berto at a time. What is the minimum possible absolute difference between their candies that can be achieved?

# QUICK EXPLANATION:

Let $G = \gcd(C,D)$. Then every possible absolute difference is of the form $|A - B + kG|$ for some integer $k$, and every difference of that form can be achieved. The lowest difference that can be achieved is $\min((A - B) \bmod G, (B - A) \bmod G)$.

# EXPLANATION:

First, any absolute value is nonnegative, so the lowest possible answer in every test case is $0$. Sometimes, this can be achieved, like in the first sample input. But in some cases this cannot be achieved. For example, in the second sample input, $A = 1$ and $B = C = D = 2$. In this case, you can only increase $A$ and $B$ by an even amount, so you can't make them have the same parity.

Here's another example. Suppose $A = 11$, $B = 35$, $C = 50$ and $D = 130$. Notice that $\gcd(C,D) = 10$. Thus, no matter what you do, you cannot change the last digit of $A$ and $B$. The difference between any pair of numbers whose last digits are $1$ and $5$ respectively ends in either $4$ or $6$. Thus, the lowest possible difference we can get is $4$, and it turns out we can achieve this difference by adding $C$ to $A$ three times and $D$ to $B$ one time: $|(11 + 3\cdot 50) - (35 + 1\cdot 130)| = |165 - 161| = 4$.

We can generalize the insight we got from the previous example. Suppose we add $C$ to $A$ $m$ times and $D$ to $B$ $n$ times. Then the absolute difference that we get is $|(A + mC) - (B + nD)| = |(A - B) + (mC - nD)|$. Every number of the form $mC - nD$ (a linear combination) is divisible by $\gcd(C,D)$! Thus, we can state the following:

If $G = \gcd(C,D)$, then every possible absolute difference is of the form $|A - B + kG|$ for some integer $k$.

The smallest possible value of the form $|A - B + kG|$ depends on the sign of the number inside the absolute value. If it's possible, then the smallest you can get is $$(A - B + kG) \bmod G = (A - B)\bmod G,$$ and if it's negative, then it is $$-(A - B + kG)\bmod G = (B - A)\bmod G.$$ (Remember that $x \bmod G$ is always nonnegative even if $x$ is negative.) Thus, the answer is at least $$\min((A - B)\bmod G, (B - A)\bmod G).$$ Unfortunately, we haven't yet proved that every integer of the form $|A - B + kG|$ can be achieved as a difference, so "$\min((A - B)\bmod G, (B - A)\bmod G)$" is just a lower bound at this point. Thus, we want to know whether the following is true:

Let $G = \gcd(C,D)$. Can every possible value of the form $|A - B + kG|$ for any integer $k$ be expressed in the form $|A - B + (mC - nD)|$ for some nonnegative integers $m$ and $n$?

If we can show this, then we establish that the answer is $\min((A - B)\bmod G, (B - A)\bmod G)$. If not, then we'll have to find other ways.

Note that the word "nonnegative" is pretty important; Without it, then we can easily answer the problem by using Bézout's identity:

If $G = \gcd(C,D)$, then there exist integers $x$ and $y$ such that $Cx + Dy = G$.

Using this theorem, we can now achieve any difference $|A - B + kG|$ by setting $m = kx$ and $n = -ky$. Unfortunately, the theorem doesn't guarantee anything about the signs of $x$ and $y$.

But actually, there's a way to convert any choice $(m,n)$ to a new choice $(m',n')$ such that both are nonnegative, by noticing that if $(m,n)$ is a valid choice, then $(m+D,n+C)$ is also valid! It's simply because $$(m+D)C - (n+C)D = mC + DC - nD - CD = mC - nD.$$ But $m+D$ and $n+C$ are strictly greater than $m$ and $n$, respectively, so we can apply this rule over and over again until both $m$ and $n$ become positive!

This last piece proves that the answer is $\min((A - B) \bmod G, (B - A) \bmod G)$.

Another way to look at it is that we can (partially) strengthen Bézout's identity to the following two statements:

1. If $G = \gcd(C,D)$ and $C$ and $D$ are positive, then there exist integers $x > 0$ and $y < 0$ such that $Cx + Dy = G$.

2. If $G = \gcd(C,D)$ and $C$ and $D$ are positive, then there exist integers $x < 0$ and $y > 0$ such that $Cx + Dy = G$.

The proof goes similarly: For any $(x,y)$ satisfying $Cx + Dy = G$, the pairs $(x + D, y - C)$ and $(x - D, y + C)$ also satisfies it, so we can keep on applying these until we get the signs that we want. And since we choose $(m,n) = (kx,-ky)$, then:

• If $k \ge 0$, then we can choose $x > 0$ and $y < 0$ to make $(m,n)$ nonnegative.
• If $k < 0$, then we can choose $x < 0$ and $y > 0$ to make $(m,n)$ nonnegative.

# Appendix: Bézout's identity

Here we'll prove Bézout's identity:

If $G = \gcd(C,D)$, then there exist integers $x$ and $y$ such that $Cx + Dy = G$.

We will actually prove this constructively, that is, by giving an algorithm that finds such $x$ and $y$.

Our solution here will involve Euclid's algorithm to compute GCD's. The basic Euclid recursion for GCD goes:
$$\gcd(a,b) = \gcd(b, a\bmod b)$$ Euclid's algorithm simply applies this over and over again until $b$ becomes $0$, in which case $\gcd(a,0) = a$.

Another way of looking at it is that we're generating a sequence of numbers $r_0, r_1, r_2, \ldots$ such that:

• $r_0 = a$
• $r_1 = b$
• $r_i = r_{i-2} \bmod r_{i-1}$

And we halt this sequence when $r_i$ becomes $0$, in which case $r_{i-1}$ is the GCD!

For example, suppose we want to find the GCD of $C = 602$ and $D = 427$. Then:

$$\begin{array}{r|rrrrr} i & & & & & r_i \\ \hline 0 & & & & & 602 \\ 1 & & & & & 427 \\ 2 & 602 &\bmod& 427 &=& 175 \\ 3 & 427 &\bmod& 175 &=& 77 \\ 4 & 175 &\bmod& 77 &=& 21 \\ 5 & 77 &\bmod& 21 &=& 14 \\ 6 & 21 &\bmod& 14 &=& 7 \\ 7 & 14 &\bmod& 7 &=& 0 \end{array}$$

Since $r_7 = 0$, we find that the GCD is $r_6$, or $7$.

But notice that "$a\bmod b$" is equivalent to "$a - qb$", where $q = \lfloor a/b \rfloor$. Thus, every number is a linear combination of the numbers above it: $r_i = r_{i-2} - qr_{i-1}$, where $q = \left\lfloor \frac{r_{i-2}}{r_{i-1}} \right\rfloor$. By also noticing that $C$ and $D$ can be written as linear combinations of themselves: $C = C\cdot 1 + D\cdot 0$ and $D = C\cdot 0 + D\cdot 1$, we can express each subsequent value as a linear combination of $C$ and $D$ too, and by doing so we're able to extend Euclid's algorithm to actually find the coefficients $x$ and $y$!

For example, using $C = 602$ and $D = 427$ again:

$$\begin{array}{r|r|rrrrr|rrrrr} i & \left\lfloor \frac{r_{i-2}}{r_{i-1}} \right\rfloor & & & & & r_i & & & & & \text{linear combination} \\ \hline 0 & & & & & & 602 & & & & & C\cdot 1 + D\cdot 0 \\ 1 & & & & & & 427 & & & & & C\cdot 0 + D\cdot 1 \\ 2 & 1 & 602 &{}-1\,\cdot& 427 &=& 175 & (C\cdot 1 + D\cdot 0) &{}-1\,\cdot& (C\cdot 0 + D\cdot 1) &=& C\cdot 1 + D\cdot -1 \\ 3 & 2 & 427 &{}-2\,\cdot& 175 &=& 77 & (C\cdot 0 + D\cdot 1) &{}-2\,\cdot& (C\cdot 1 + D\cdot -1) &=& C\cdot -2 + D\cdot 3 \\ 4 & 2 & 175 &{}-2\,\cdot& 77 &=& 21 & (C\cdot 1 + D\cdot -1) &{}-2\,\cdot& (C\cdot -2 + D\cdot 3) &=& C\cdot 5 + D\cdot -7 \\ 5 & 3 & 77 &{}-3\,\cdot& 21 &=& 14 & (C\cdot -2 + D\cdot 3) &{}-3\,\cdot& (C\cdot 5 + D\cdot -7) &=& C\cdot -17 + D\cdot 24 \\ 6 & 1 & 21 &{}-1\,\cdot& 14 &=& 7 & (C\cdot 5 + D\cdot -7) &{}-1\,\cdot& (C\cdot -17 + D\cdot 24) &=& C\cdot 22 + D\cdot -31 \\ 7 & 2 & 14 &{}-2\,\cdot& 7 &=& 0 & (C\cdot -17 + D\cdot 24) &{}-2\,\cdot& (C\cdot 22 + D\cdot -31) &=& C\cdot -61 + D\cdot 86 \end{array}$$ Thus, we establish that $\gcd(C,D) = 7$, and $C\cdot 22 + D\cdot -31 = 7$! It's easy to see that this method can also be applied for any pair $(C,D)$. This is one version of the extended Euclid's algorithm.

# Time Complexity:

$O(\log \min(C, D))$

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

asked 03 Jun '16, 04:02 1.7k586142
accept rate: 11% 19.8k350498541

 0 from fractions import gcd ls = [] for dfj in range(input()): a,b,c,d = [int(i) for i in raw_input().split()] g = gcd(c,d) ls.append(min((a-b)%g,(b-a)%g)) for i in ls: print i  answered 05 Jun '16, 21:56 1★samtan 1 accept rate: 0%
 0 Hi,I didn't get this line ."If it's possible, then the smallest you can get is : (A-B+kG) mod G". Please explain it. answered 07 Aug '17, 08:27 0●1 accept rate: 0%
 0 What if we also want to know the sequence in which the candies were given? How to print the sequence? answered 20 Jan '18, 19:47 1●1 accept rate: 0%
 0 @bhagirathi08 ,suppose that the initial apples and bananas be 0, then the difference that can be created is kg, but since initially they were a and b the difference which can be created is (|A-B+kg|) k can also be negative answered 04 Sep '18, 17:08 2★vibhor_1 1●1 accept rate: 0%
 0 how smallest value of |(A−B+kG)|=(A−B)modG? I didn't get it. Please explain answered 07 Oct '18, 11:04 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,191
×321
×82
×8
×5
×5

question asked: 03 Jun '16, 04:02

question was seen: 6,033 times

last updated: 07 Oct '18, 11:04