The first sub-round of Google Code Jam 2008 Round 1 featured three little challenges. Each problem required one or two cute ideas to solve.
The first problem is formulated in one of the important concepts connecting algebra and geometry, that of scalar product, also known as inner product. Though the problem itself is an exercise in arrays and numbers.
The second problem, as mundane as the name suggests, has some connection to the propositional logic, especially the satisfiability problem. Unlike the super-hard general satisfiability problem, this one is in a restricted form, and thus allows one to find a simple and cute solution.
The third problem, appears as a numerical problem, actually should be solved with only integer numbers. With ideas from elementary algebra, combinatorics, and number theory, armed with some standard tricks on the computational side, we know at least four different solutions with distinct flavor.
2394 contestants finished the match with a positive score, among them, we have 41 perfect scores.
Credits
Problem A. Minimum Scalar Product Written by Michael Levin. Prepared by Frank Chu.
Problem B. Milkshakes Written by John Dethridge. Prepared by Frank Chu and John Dethridge.
Problem C. Numbers Written and prepared by Cosmin Negruseri.
Contest analysis presented by Cosmin Negruseri, Xiaomin Chen, and John Dethridge.
You are given two vectors v_{1} = (x_{1}, x_{2}, ..., x_{n}) and v_{2} = (y_{1}, y_{2}, ..., y_{n}). The scalar product of these vectors is a single number, calculated as x_{1}y_{1} + x_{2}y_{2} + ... + x_{n}y_{n}.
Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.
For each test case, output a line
Case #X: Ywhere X is the test case number, starting from 1, and Y is the minimum scalar product of all permutations of the two given vectors.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
T = 1000
1 ≤ n ≤ 8
-1000 ≤ x_{i}, y_{i} ≤ 1000
T = 10
100 ≤ n ≤ 800
-100000 ≤ x_{i}, y_{i} ≤ 100000
2 3 1 3 -5 -2 4 1 5 1 2 3 4 5 1 0 1 0 1
Case #1: -25 Case #2: 6
You own a milkshake shop. There are N different flavors that you can prepare, and each flavor can be prepared "malted" or "unmalted". So, you can make 2N different types of milkshakes.
Each of your customers has a set of milkshake types that they like, and they will be satisfied if you have at least one of those types prepared. At most one of the types a customer likes will be a "malted" flavor.
You want to make N batches of milkshakes, so that:
Find whether it is possible to satisfy all your customers given these constraints, and if it is, what milkshake types you should make.
If it is possible to satisfy all your customers, there will be only one answer which minimizes the number of malted batches.
One line containing an integer C, the number of test cases in the
input file.
For each test case, there will be:
C lines, one for each test case in the order they occur in the input file, each containing the string "Case #X: " where X is the number of the test case, starting from 1, followed by:
Time limit: 30 seconds per test set.
Memory limit: 1GB.
C = 100
1 ≤ N ≤ 10
1 ≤ M ≤ 100
C = 5
1 ≤ N ≤ 2000
1 ≤ M ≤ 2000
The sum of all the T values for the customers in a test case will not exceed 3000.
2 5 3 1 1 1 2 1 0 2 0 1 5 0 1 2 1 1 0 1 1 1
Case #1: 1 0 0 0 0 Case #2: IMPOSSIBLE
In the first case, you must make flavor #1 malted, to satisfy the first customer. Every other flavor can be unmalted. The second customer is satisfied by getting flavor #2 unmalted, and the third customer is satisfied by getting flavor #5 unmalted.
In the second case, there is only one flavor. One of your customers wants it malted and one wants it unmalted. You cannot satisfy them both.
In this problem, you have to find the last three digits before the decimal point for the number (3 + √5)^{n}.
For example, when n = 5, (3 + √5)^{5} = 3935.73982... The answer is 935.
For n = 2, (3 + √5)^{2} = 27.4164079... The answer is 027.
The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n.
For each input case, you should output:
Case #X: Ywhere X is the number of the test case and Y is the last three integer digits of the number (3 + √5)^{n}. In case that number has fewer than three integer digits, add leading zeros so that your output contains exactly three digits.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100
2 ≤ n ≤ 30
2 ≤ n ≤ 2000000000
2 5 2
Case #1: 935 Case #2: 027
In spite of the geometric flavor in the name of this problem, it is truly a story of two arrays.
There are two permutations involved. However, after you fix the permutation for V_{1}, you have complete freedom in choosing the permutation for V_{2}. It is clear that the first permutation really does not matter. The important thing is which x_{i} gets to be matched to which y_{j}.
To make thinking easier, we may assume that the first permutation has
x_{1} ≤ x_{2} ≤ ... ≤ x_{n}. (1)
And our task is to match the y's to the x's so that the scalar product is as small as possible.
At this point, if you need a little exercise in the middle: Think about the
case
What we would like to prove is: under condition (1), one of the optimal solutions is of the form
y_{1} ≥ y_{2} ≥ ... ≥ y_{n}. (2)
The rigorous proof of (2) is given at the end of this analysis. For an easy
reading, we point out that the key step is really the
(xy + x'y') - (xy' + x'y) = (x - x')(y - y') > 0. (*)
So we prefer to match bigger y's with smaller x's.
Therefore, this problem is solved by the following simple algorithm.
sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end(), greater<int>()); long long ret = 0; for (int i = 0; i < n; i++) ret += (long long)(v1[i]) * v2[i];
Proof of (2). We prove that any permutation that does not satisfy (2)
can be transformed into one satisfying (2), and in each step we do not
increase the scalar product.
Indeed, any unsorted array can be transformed to a sorted one by only
interchanging adjacent elements that are out of order. (For more rigorous
readers: prove this, maybe by counting the number of flipped pairs in the
array.)
At each step, some
On the surface, this problem appears to require solving the classic problem "Satisfiability," the canonical example of an NP-complete problem. The customers represent clauses, the milkshake flavors represent variables, and malted and unmalted flavors represent whether the variable is negated.
We are not evil enough to have chosen a problem that hard! The restriction that makes this problem easier is that the customers can only like at most one malted flavor (or equivalently, the clauses can only have at most one negated variable.)
Using the following steps, we can quickly find whether a solution exists, and if so, what the solution is.
Notice that whenever we made a flavor malted, we were forced to do so. Therefore, the solution we got must have the minimum possible number of malted flavors.
With clever data structures, the above algorithm can be implemented to run in linear time.
The Satisfiability problem - Horn clauses
This problem with a simple statement was in fact one of the hardest in Round
1. The input restrictions for the small input were chosen so that
straightforward solutions in Java or Python, which have arbitrary-precision
numbers, would fail.
The trick was calculating √5 to a large enough precision and not using
the default double value. It turned out that using the Windows calculator or
the UNIX bc
tool was enough to solve the small tests as well.
Solving the large tests was a very different problem. The difficulty comes from the fact that √5 is irrational and for n close to 2000000000 you would need a lot of precision and a lot of time if you wanted to use the naive solution.
The key in solving the problem is a mathematical concept called
conjugation.
In our problem, we simply note that
(1) α := 3 + √5, β := 3 - √5, and X_{n} := α^{n} + β^{n}.
We first note that X_{n} is an integer. This can be proved by using the binomial expansion. If you write everything down you'll notice that the irrational terms of the sums cancel each other out.
(2)
Another observation is that β^{n} < 1, so X_{n} is actually the first integer greater than α^{n}. Thus we may just focus on computing the last three digits of X_{}.
A side note. In fact, β^{n} tends to 0 so quickly that that our problem would be trivial if we asked for the three digits after the decimal point. For all large values of n they are always 999.
Based on (1) and (2), there are many different solutions for finding the last three digits of X_{n}.
One solution goes like this: α^{n} can be written as
(3) α^{(n + 1)} = (3 + √5)(a_{n} + b_{n}√5) = (3a_{n} + 5b_{n}) + (3b_{n} + a_{n})√5.
So a_{n + 1} = 3a_{n} + 5b_{n} and b_{n + 1} = 3b_{n} + a_{n}. This can be written in matrix form as
(4)
Since α^{0} = 1, we have (a_{0}, b_{0}) = (1, 0).
Now we use the standard fast exponentiation to get A^{n} in O(log n) time. Note that we do all operations modulo 1000 because we just need to return the last three digits of a_{n}.
Here's some Python code that implements this solution:
def matrix_mult(A, B): C = [[0, 0], [0, 0]] for i in range(2): for j in range(2): for k in range(2): C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 1000 return C def fast_exponentiation(A, n): if n == 1: return A else: if n % 2 == 0: A1 = fast_exponentiation(A, n/2) return matrix_mult(A1, A1) else: return matrix_mult(A, fast_exponentiation(A, n - 1)) def solve(n): A = [[3, 5], [1, 3]] A_n = fast_exponentiation(A, n) return (2 * M_n[0][0] + 999) % 1000
Experienced contestants may notice there is a linear recurrence on the X_{i}'s. Indeed, this is not hard to find -- the conjugation enters the picture again.
Notice that
(5) α + β = 6, and α β = 4.
So α and β are the two roots of the quadratic equation x^{2} - 6x + 4 = 0. i.e.,
(6) α^{2} = 6α - 4, and β^{2} = 6β - 4.
Looking at (1) and (6) together, we happily get
(7) X_{n+2} = 6X_{n+1} - 4X_{n}.
Such recurrence can always be written in matrix form. It is somewhat redundant, but it is useful:
From here it is another fast matrix exponentiation. Let us see radeye's perl code that implements this approach here:
sub mul { my $a = shift ; my $b = shift ; my @a = @{$a} ; my @b = @{$b} ; my @c = ($a[0]*$b[0] + $a[1]*$b[2], $a[0]*$b[1] + $a[1]*$b[3], $a[2]*$b[0] + $a[3]*$b[2], $a[2]*$b[1] + $a[3]*$b[3]) ; @c = map { $_ % 1000 } @c ; return @c ; } sub f { my $n = shift ; return 2 if $n == 0 ; return 6 if $n == 1 ; return 28 if $n == 2 ; $n -= 2 ; my @mat = (0, 1, 996, 6) ; my @smat = @mat ; while ($n > 0) { if ($n & 1) { @mat = mul([@mat], [@smat]) ; } @smat = mul([@smat], [@smat]) ; $n >>= 1 ; } return ($mat[0] * 6 + $mat[1] * 28) % 1000 ; } sub ff { my $r = shift ; $r = ($r + 999) % 1000 ; $r = "0" . $r while length($r) < 3 ; return $r ; } for $c (1..<>) { $n = <> ; print "Case #$c: ", ff(f($n)), "\n" ; }
For this problem, we have another approach based on the recurrence (7). Notice that we only need to focus on the last 3 digits of X_{n}, which only depends on the last 3 digits of the previous two terms. The numbers eventually become periodic as soon as we have (X_{i}, X_{i+1}) and (X_{j}, X_{j+1}) with the same last 3 digits, where i < j. It is clear that we will enter a cycle no later than 10^{6} steps. In fact, for this problem, you can write some code and find out that the cycle has the size 100 and starts at the 3rd element in the sequence. So to solve the problem we can just brute force the results for the first 103 numbers and if n is bigger than 103 return the result computed for the number (n - 3) % 100 + 3.
Let us see one more solution of different flavor. Here is a solution not as general as the others, but tailored to this problem, and makes one feel we are almost solving this problem by hand.
Let us look again at (2). We want to know X_{n} mod 1000.
We know from the
chinese remander theorem
that if we can find X_{n} mod 8 and X_{n} mod 125, then
X_{n} mod 1000 is uniquely determined.
(a) For n > 2, X_{n} mod 8 is always 0. Since 5^{i}
≡ 1 (mod 4), 3^{n-2i} ≡ 1 or -1 (mod 4) depending on n,
so, for n > 2,
(b) To compute X_{n} mod 125, we only need to worry about i=0,1,2. All the rest are 0 mod 125. In other words, all we need to compute is
There are various ways to compute the elements in the above quantity. The exponents can be computed by fast exponentiation, or using the fact that 3^{n} mod 125 is periodic with cycle length at most 124. The binomial numbers can be computed using arbitrary precision integers in languages like Java and Python, or with a bit careful programming in languages like C++.
Binomial numbers - Linear recurrence - Exponentiation - Chinese remainder theorem