Problem B: Fair Warning Solution (Google Code Jam Qualification Round 2010)

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: t1, t2, …, tn, and ti ? tj for some i, j. Find the smallest integer y >= 0 such that each ti + 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 t1 is greater than t2.

Therefore,
t1 + y = k1 * T —– (1)
t2 + y = k2 * T —– (2)

ti, y, ki, and T are all integers.

Eq. (1) – (2) gives
t1 – t2 = (k1 – k2) * T

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

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

Substituting in Eq. (2), we get
y = k2 * T – t2
= 1 * (t1 – t2) – t2
= t1 – 2 * t2

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 ti – tj, i ? j, ti > tj. 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.

VN:F [1.9.22_1171]
Rating: 4.3/5 (4 votes cast)
Problem B: Fair Warning Solution (Google Code Jam Qualification Round 2010), 4.3 out of 5 based on 4 ratings

7 thoughts on “Problem B: Fair Warning Solution (Google Code Jam Qualification Round 2010)

  1. 1337c0d3r

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

    VA:F [1.9.22_1171]
    -1
    1. lee

      Actually, 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.

      VA:F [1.9.22_1171]
      0
  2. csLittleye

    maybe 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

    VN:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*