Read the question here from GCJ Qualification Round 2010:

» Problem B: Fair Warning

This problem is cryptic in description, but it can be summarize as a Math problem below:

Given a list of positive integers: t

_{1}, t_{2}, …, t_{n}, and t_{i}? t_{j}for some i, j. Find the smallest integer y >= 0 such that each t_{i}+ y is divisible by an integer T. T must be the largest of all possible divisors.

First, this problem is named “Fair Warning” for a reason. It is a fair warning to you that a problem using Big Integer library is possible (which the large input requires), and you should prepare for that in future rounds.

I guess many would agree that this is the hardest problem for most people. If you know basic number theory, you would probably breeze through this problem. If you don’t (like me), it is still possible to find your way to the solution, but it is a bit harder.

Before we go for the general solution, let’s consider the easier case where n=2, and assume t_{1} is greater than t_{2}.

Therefore,

t_{1} + y = k_{1} * T —– (1)

t_{2} + y = k_{2} * T —– (2)

t_{i}, y, k_{i}, and T are all integers.

Eq. (1) – (2) gives

t_{1} – t_{2} = (k_{1} – k_{2}) * T

Therefore, we can conclude that t_{1} – t_{2} is also divisible by T. Since T must be the largest among all possible divisors, k_{1} – k_{2} must equal 1. Why? Consider when k_{1} – k_{2} = 2, then the value of T would be halved. We have just found the value of T, which is equal to t_{1} – t_{2}.

After we have found the value of T, we can obtain value of y. From the previous information that k_{1} – k_{2} = 1, we can deduce from Eq. (1) and (2) that k_{2} = 1 and k_{1} = 2. Why not k_{2} = 2 and k_{1} = 3? Recall that y is the smallest value that fulfill the requirement.

Substituting in Eq. (2), we get

y = k_{2} * T – t_{2}

= 1 * (t_{1} – t_{2}) – t_{2}

= t_{1} – 2 * t_{2}

We have solved the easy case. Now generalize for all cases. You can probably see that for n >= 3, the value of T is equal to the Greatest Common Divisor (GCD) of all possible t_{i} – t_{j}, i ? j, t_{i} > t_{j}. Note that finding all such possible pairs of i and j takes O(n^2) time.

Once we found the value of T, we can then solve for y.

For large input, you have to use a Big Integer library and there is one possible optimization. When a = b = c, then gcd(b – a, c – a) = gcd(b – a, c – a, c – b). Taking advantage of this property, we are able to reduce the GCD step from O(n^2) to O(n).

The below solution only works for the small input (without the optimization mentioned above). Unfortunately, it timeouts for the large input. (I am using my own Big Integer library). I suspect that my Big Integer library is not efficient enough. I would love to know if you have tested my solution using a Big Integer library and if it finishes within the time limit. Anyway, the below solution gives a general idea on how to approach this problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
long long gcd(long long a, long long b) { if (b == 0) return a; return gcd(b, a % b); } long long gcd(long long arr[], int n) { long long temp = arr[0]; for (int i = 1; i < n; i++) { temp = gcd(temp, arr[i]); } return temp; } int n, m; long long arr[1400], arr2[100000]; cin >> n; for (int i = 0; i < n; i++) { cin >> m; for (int j = 0; j < m; j++) cin >> arr[j]; sort(arr, arr+m); int sz = 0; for (int j = m-1; j >=0; j--) { for (int k = j-1; k >= 0; k--) { arr2[sz++] = arr[j]-arr[k]; } } long long T = gcd(arr2, sz); long long ans = (ceil((double)arr[0] / T))*T - arr[0]; cout << "Case #" << i+1 << ": " << ans << endl; } |

Thank you for the wonderful and concise explanation. Great Job ðŸ™‚

0Thanks! Please subscribe to my blog via RSS on the right hand side. I will keep my blog updated!

-1Actually, there is some error in your deducting for y, y = t1 â€“ 2 * t2, since y>=0, which means if and only if t1 >=2*t2, k2 = 1, otherwise k2 may be larger than 1. For example, let’s say t1 = 9 and t2 = 7, then T= t1 – t2 = 2, but t1 + 1 = 10 = 5*2 and t2 + 1 = 8 = 4*2.

In this case k1 = 5 and k2 = 4, y = 1.

0Nice work!!

0maybe we don’t need do all pairs which takes O(n^2). Since t_1 < t_2 < t_3, t_2-t_1 = (k_2-k_1)*T, t_3 – t_2 = (k_3-k_2)*T, then we know (t_3-t_1) is divisible by T because t_3-t_2 + t_2-t_1 = (k_3-k_2)*T + (k_2-k_1)*T=(k_3-k_1)*T = t_3-t_1

0What happens when t1<2t2? I guess at this time if N=2 then the algorithm fail?

0Oh wait just ignore me…

0