Jam 2008 Round 1A

Posted on 1st April 2015

These seem to me to be essentially pure mathematics, in that once I understood the problem, and the maths behind it, the implementation in code was almost trivial.

The Official Contest Analysis is a good writeup, so I won't say a great deal. See the code on GitHub.

Problem A, Minimum Scalar Product: The only comment I have is that the formal "proof" the contest analysis gives seems overly complicated to me.

  • We are free to reorder both the vectors, so assume x is increasing: \( x_1 \leq x_2 \leq \cdots \leq x_n \)
  • As there are only finitely many arrangements, these is a minimal scalar product. Let the given ordering of y give this minimum.
  • Suppose y is not decreasing, so there are \( i < j \) with \( y_i < y_j \). The current scalar product is \( t + x_iy_i + x_jy_j \) where \( t \) is the rest of the product. If we swap \( y_i, y_j \) then the scalar product becomes \( t + x_iy_j + x_jy_i \).
  • As we have a minimum, we must have that \( t + x_iy_i + x_jy_j \leq t + x_iy_j + x_jy_i \) which rearranges to \( x_i(y_i - y_j) \leq x_j(y_i - y_j) \) or \( 0 \leq (x_j-x_i)(y_i - y_j) \). As \( x_j-x_i \geq 0 \) and \( y_i - y_j < 0 \) these inequalities can only hold if \( x_j-x_i = 0 \).
  • So we can get \( y_i < y_j \) "out of order" only when \( x_i = x_j \). But within a "block" \( x_i = x_{i+1} = \cdots = x_k \) say we can always re-arrange \( y_i, y_{i+1}, \cdots, y_k \) and we don't change the inner product.
  • Conclusion: Any minimum arrangement of y is "out of order" only for equal \(x_i\)s.

Problem B, Milkshakes: I came up with much the same algorithm. I must say that, right now, I don't see how to get a linear time algorithm, though in practise this doesn't matter.

Problem C, Numbers: This was extremely mathematical. I, eventually, came up with Solution B from the analysis. Instead, here I'll present an idea which doesn't work!

The collection of numbers \( \{ x + y\sqrt 5 : x,y \in\mathbb Z \} \) forms a ring the proof of which is essentially the observation that \( (x+y\sqrt 5)(a+b\sqrt 5) = (xa + 5yb) + (xb + ya)\sqrt 5 \). Thus, using e.g. Python and its built-in support for large integers and the "repeated squaring" algorithm for finding powers, it's easy to find \( (3+\sqrt 5)^n \) for even very large \( n \).

The problem is that we want to know the final three digits before the decimal point: that is, find \( \lfloor (3+\sqrt 5)^n \rfloor \mod 1000 \). If \( (3+\sqrt 5)^n = a+ b\sqrt 5 \) then we want \( \lfloor a+b\sqrt 5 \rfloor \mod 1000 = a + \lfloor b\sqrt 5 \rfloor \mod 1000 \). Finding \( a \mod 1000 \) is easy, as we can implement the whole "repeated squaring" algorithm modulo 1000, which would also find \( b\mod 1000\). However, how to find \( b\sqrt 5 \rfloor \mod 1000 \)?

My initial idea was to find \( b\sqrt 5 = \sqrt{ 5b^2 } \) using a purely integer algorithm (e.g. repeated bisection). This works, but for the size numbers the "large" problem needs, it's too slow (and it's speed, not memory, on my 2013 era PC, which is the barrier).

Some more thought, and I came up with the link between \(a\) and \(b\) as detailed in the official answer.

Categories
Recent posts