Problem B. Fair Warning - Qualification Round 2010 - Google Code Jam

Dashboard - Qualification Round 2010 - Google Code Jam

Problem

On our planet, Jamcode IX, three Great Events occurred. They happened 26000, 11000 and 6000 slarboseconds ago. In 4000 slarboseconds, the amount of time since all of those events will be multiples of 5000 slarboseconds, the largest possible amount... and the apocalypse will come.
Luckily for you, you live on Jamcode X! The apocalypse came on Jamcode IX less than a year ago. But Jamcode X has a worrying prophecy: "After the moment of reckoning, on the first optimum anniversary of the N Great Events, the apocalypse will come. 64 bits will not save you. You have been warned."
The people of Jamcode X are very concerned by this prophecy. All of the Great Events have already happened, and their times have been measured to the nearest slarbosecond; but nobody knows when their optimum anniversary will occur. After studying the diary of a scientist from Jamcode IX, scientists working on the problem have come up with a theory:
The moment of reckoning is now, the moment you solve this problem. At some time y ≥ 0 slarboseconds from now, the number of slarboseconds since each of the Great Events will be divisible by some maximum number T. If you can find the smallest value of y that gives this largest possible T, that will give you the optimum anniversary when the apocalypse will come.
On Jamcode IX, for example, there were 3 Great Events and they happened 26000, 11000 and 6000 slarboseconds before the moment of reckoning. 4000 slarboseconds later, the amount of time since each event was a multiple of T=5000 slarboseconds, and the apocalypse came.
Your job is to compute the amount of time until the apocalypse comes. But remember the prophecy: even though the people of Jamcode X have been solving problems for two years, and 64-bit integers have always been enough, they might not always be enough now or in the future.

Input

The first line of the input gives the number of test cases, C. C lines follow. Each starts with a single integer N, which is followed by a space and then N space-separated integers t_i, the number of slarboseconds since Great Event i occurred.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of slarboseconds until t_i + y is a multiple of the largest possible integer factor T for all i.
Official Analysis: https://code.google.com/codejam/contest/433101/dashboard#s=a&a=1

This problem talks about divisors and multiples so it hints at using the greatest common divisor concept in some way. To solve the problem we need to find T and afterwards we can easily find y.

Let's simplify the problem and just look at two numbers a and b. In this case we need to find the largest T so that some positive y exists where a + y and b + y are multiples of T. So (a + y) modulo T = (b + y) modulo T which means that (a - b) modulo T = 0. Thus Tmust be a divisor of |a - b|.

Coming back to the problem with N numbers, we have proved that T must divide every |t_i - t_j|. This means that the solution is the greatest common divisor of all |t_i - t_j| numbers. A simple observation can improve our algorithm from O(N²) to O(N) iterations of the Euclidean algorithm. Let's say a ≤ b ≤ c, then gcd(b - a, c - a) = gcd(b - a, c - a, c - b). To prove this we look at the first iteration of the Euclidean algorithm. Since a ≤ b ≤ c it means that b - a ≤ c - a so in the first step we subtract b - a from c - a: gcd(b - a, c - a) = gcd(c - b, b - a), this proves our observation. Now we can just compute the greatest common divisor of all |t_i - t₁| to find T.

http://articles.leetcode.com/2010/05/problem-b-fair-warning-solution.html

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

Given a list of positive integers: t₁, t₂, …, 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.

Before we go for the general solution, let’s consider the easier case where n=2, and assume t₁ is greater than t₂.

Therefore,
t₁ + y = k₁ * T —– (1)
t₂ + y = k₂ * T —– (2)

t_i, y, k_i, and T are all integers.

Eq. (1) – (2) gives
t₁ – t₂ = (k₁ – k₂) * T

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

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

Substituting in Eq. (2), we get
y = k₂ * T – t₂
= 1 * (t₁ – t₂) – t₂
= t₁ – 2 * t₂

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).

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;

}

http://jamie-wong.com/2010/05/11/google-codejam-2010-solutions-qualification-round/

You can first calculate T (the optimal anniversary) by looking at the gcd (greatest common divisor) of the differences between the time elapsed since the events. This works because in order for T to divide the time elapsed since the events, it must also divide the time elapsed between the events. After that, you just need to find the first y that makes any of the numbers divisible by T. I just wrote out the congruences on my whiteboard (which I probably shouldn’t have needed to do) then typed in my answer.

def gcd(x,y):
    while x:
        x, y = y % x, x
    return y

testcases = open("warning.in").readlines()
t = 1
for tc in testcases[1:]:
  tc = map(lambda x: int(x), tc.split(" ")[1:])
  if len(tc) == 0:
    break
  tc.sort()
  #print tc

  diff = []
  for i in range(len(tc)-1):
    diff += [tc[i+1] - tc[i]]

  T = diff[0]
  for d in diff[1:]:
    T = gcd(T,d)

  #print T
  print "Case #%d: %d" % (t, (-tc[0] % T))

  t += 1

static String process(String line){
String[] parts = line.split("[ ]");
BigInteger[] values = new BigInteger[parts.length-1];
for(int i=1;i<parts.length;i++){
values[i-1] = new BigInteger(parts[i]);
}
Arrays.sort(values);
BigInteger dev = values[1].subtract(values[0]);
for(int i=0;i<values.length-2;i++){
BigInteger b = values[i+2].subtract(values[i+1]);
dev = dev.gcd(b);
}
BigInteger buf = values[0].mod(dev);
if(buf.compareTo(BigInteger.valueOf(0))==0){
return "0";
}
buf = dev.subtract(buf);
return buf.toString();
}

public static BigInteger GCD(BigInteger A, BigInteger B) {
if(B.equals(BigInteger.ZERO))return A;
return GCD(B,A.mod(B));
}
Read full article from Dashboard - Qualification Round 2010 - Google Code Jam