Last Friday, I participated in the Google Code Jam, a programming puzzle contest sponsored by Google. It was the first qualification round, and I was very happy with how I did, coming in 74th in my heat (there were three heats, and mine had almost 3000 participants).
There were three problems, each with two data sets. The last problem was really more of a math problem, which I figured would have given me more of an edge because most of the time when I cheat on my second love, computers, it’s with my first love, math. However, I couldn’t complete it in the time allotted. But I also couldn’t stop thinking about it. I eventually came up with a solution which I’ll share here.
It’s problem C in round 1A (start here), but essentially, you have to find the last three digits before the decimal point for the number (3 + √5)n where n is a whole number that can be very large (up to two billion).
This means you cannot calculate the whole thing; it would contain several hundred million digits, which would use most of RAM just to hold the representation. So you have to figure out a trick.
Here’s what I came up with (too late to submit). Let An = (3 + √5)n and Bn = (3 – √5)n. Observe that An = Xn + Yn√5 for some series X0, X1, … and Y0, Y1, … where each of Xn and Yn are whole numbers. You can show this easily by induction. You can show a similar thing for Bn; in fact, Bn = Xn – Yn√5.
This means that An+Bn = 2Xn.
Notice that (3 – √5) < 1, so Bn < 1 for n>1, and goes towards 0 very quickly. Since An = 2Xn – Bn, we can calculate An by calculating 2Xn and subtracting a “small” number… that is, the last three digits of An are the same as the last three digits of 2Xn-1.
So all we need to do is figure out Xn!
We know that X0 = 1, Y0 = 0. An+1 = An(3 + √5), so
Xn+1 + Yn+1√5 = An+1 = An(3 + √5) = (Xn + Yn√5)(3 + √5) = (3Xn+5Yn)+√5(Xn+3Yn)
so separating rational and irrational parts yields the pretty recurrence relation Xn+1 = 3Xn + 5Yn and Yn+1 = Xn+3Yn.
That means Xn+1 and Yn+1 depend only upon Xn and Yn. Since we only care about the last three digits, that means that there are only 1000*1000=a million different combinations of Xn, Yn, and thus, the series must repeat in fewer than a million iterations. It shouldn’t be too hard to find a repeat.
Here’s the Python code to find the cycle length:
def _a_b_n(n):
if n == 0:
return 3,1
a,b = a_b_n(n-1)
return ((3*a+5*b) % 1000, (a+3*b) % 1000)
CACHE={}
def a_b_n(n):
if not CACHE.has_key(n):
CACHE[n] = _a_b_n(n)
return CACHE[n]
F={}
for i in xrange(int(1e6)):
k = (Xn, Yn) = a_b_n(i)
#print i, a, b, (2*a-1)%1000
if F.has_key(k):
#print "repeat: %d, %d" % (i,F[k])
break
F[k] = i
cycle_length = i-F[k]
print "cycle length is", cycle_length
When you run this, it takes less than a tenth of a second to figure out that the cycle length is 500, and A503, B503 = A3, B3. So now it’s easy! Calculating the first 503 terms is enough.
Here is the rest of the code:
def do_trial(f):
n = int(f.readline())
if n>cycle_length:
n %= cycle_length
n += cycle_length
t = a_b_n(n-1)
return (2*t[0]-1) % 1000
f = sys.stdin
count = int(f.readline())
for i in xrange(count):
v = do_trial(f)
print "Case #%d: %03d" % (i+1, v)
It runs in pretty much no time at all, thanks to the excessive caching.