Posted on 13th May 2015
Last one of these for a while. Problem D became an obsession. As ever, links to: Official Contest Analysis and my code on GitHub.
Problem A, Speaking in Tongues: Could be solved with pen and paper, as all the information you need is sneakily in the question.
Problem B, Dancing With the Googlers: A "score" is a triple of numbers between 0 and 10 inclusive, and a score is "surprising" if the gap between the bigest and smallest number is 2, while a gap of 1 or 0 is not surprising, and larger gaps never occur. You're given a list of the total score (sum of the three numbers) for each of my participants, and how many scores are surprising. You need to return the maximum number of cases where the best score was >= p.
3x then the best score is x, while in all other cases the best score if floor(s/3) + 1)floor((s-2)/3) + 2).Problem C, Recycled Numbers: This seems hard (at least to me) but on reflection, it's easy. For each n we generate all m which can arise by rotating the numbers of the decimal form of n, and test if A <= n < m =< B. This algorithm is at worst O(B log B) and so plenty fast enough. The only trick is that sometimes the same m can occur twice (e.g. if n=2121 we get 1212 in two different ways), but helpfully the final test case would alert you to this. As a break, I wrote this in C++ initially, but the naive Python version (just using a set to ensure uniqueness) is plenty fast enough.
Problem D, Hall of Mirrors: I almost immediately saw how to attack this, but spent ages on writing various Python implementations, all of which are too slow! The "trick" is to observe that reflecting a light ray is equivalent to reflecting the world through the line of reflection, and leaving the light ray to travel in a straight line. (See the Contest Analysis for some nice pictures). Thus the image of "X" must always be in the exact centre of a grid square, and so the direction the light ray travels in must always be a vector in \( \mathbb Z^2 \).
So, it's just a matter of implementing a ray-tracing algorithm... Easy, right?
d.py) parses the game "maze" into lines and "corners" and implements a quite general raytracing algorithm (e.g. it would work with lines of arbitrary angle etc.) This is extremely slow, partly because I use the Python Fraction to keep computations exact.Fraction class was fun (remember that equal things must hash to the same value!) but not much faster.d_new.py which instead makes use of the context of problem: we always move about squares, which simplifies the geometry (though dealing with "corners" is still a pain, which I solved with a lookup table and using first-class functions, instead of a mass of if/then statements). Still slow.d_new_float.py to use floating-point numbers instead. This is now fast enough to solve the "large" case, but still too slow for the "small" case.