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).<\/p>\n
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.<\/p>\n
It’s problem C in round 1A (start here<\/a>), but essentially, you have to find the last three digits before the decimal point for the number (3 + ?5)n<\/sup> where n is a whole number that can be very large (up to two billion).<\/p>\n 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.<\/p>\n Here’s what I came up with (too late to submit). Let An<\/sub> = (3 + ?5)n<\/sup> and Bn<\/sub> = (3 – ?5)n<\/sup>. Observe that An<\/sub> = Xn<\/sub> + Yn<\/sub>?5 for some series X0<\/sub>, X1<\/sub>, … and Y0<\/sub>, Y1<\/sub>, … where each of Xn<\/sub> and Yn<\/sub> are whole numbers. You can show this easily by induction. You can show a similar thing for Bn<\/sub>; in fact, Bn<\/sub> = Xn<\/sub> – Yn<\/sub>?5.<\/p>\n This means that An<\/sub>+Bn<\/sub> = 2Xn<\/sub>.<\/p>\n Notice that (3 – ?5) < 1, so Bn<\/sub> < 1 for n>1, and goes towards 0 very quickly. Since An<\/sub> = 2Xn<\/sub> – Bn<\/sub>, we can calculate An<\/sub> by calculating 2Xn<\/sub> and subtracting a “small” number… that is, the last three digits of An<\/sub> are the same as the last three digits of 2Xn<\/sub>-1.<\/p>\n So all we need to do is figure out Xn<\/sub>!<\/p>\n We know that X0<\/sub> = 1, Y0<\/sub> = 0. An+1<\/sub> = An<\/sub>(3 + ?5), so<\/p>\n Xn+1<\/sub> + Yn+1<\/sub>?5 = An+1<\/sub> = An<\/sub>(3 + ?5) = (Xn<\/sub> + Yn<\/sub>?5)(3 + ?5) = (3Xn<\/sub>+5Yn<\/sub>)+?5(Xn<\/sub>+3Yn<\/sub>)<\/p>\n so separating rational and irrational parts yields the pretty recurrence relation Xn+1<\/sub> = 3Xn<\/sub> + 5Yn<\/sub> and Yn+1<\/sub> = Xn<\/sub>+3Yn<\/sub>.<\/p>\n That means Xn+1<\/sub> and Yn+1<\/sub> depend only upon Xn<\/sub> and Yn<\/sub>. Since we only care about the last three digits, that means that there are only 1000*1000=a million different combinations of Xn<\/sub>, Yn<\/sub>, and thus, the series must repeat in fewer than a million iterations. It shouldn’t be too hard to find a repeat.<\/p>\n Here’s the Python code to find the cycle length:<\/p>\n When you run this, it takes less than a tenth of a second to figure out that the cycle length is 500, and A503<\/sub>, B503<\/sub> = A3<\/sub>, B3<\/sub>. So now it’s easy! Calculating the first 503 terms is enough.<\/p>\n Here is the rest of the code:<\/p>\n It runs in pretty much no time at all, thanks to the excessive caching.<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading Google Code (Peanut Butter and) Jam<\/span> \r\ndef _a_b_n(n):\r\n if n == 0:\r\n return 3,1\r\n a,b = a_b_n(n-1)\r\n return ((3*a+5*b) % 1000, (a+3*b) % 1000)\r\n\r\nCACHE={}\r\ndef a_b_n(n):\r\n if not CACHE.has_key(n):\r\n CACHE[n] = _a_b_n(n)\r\n return CACHE[n]\r\n\r\nF={}\r\nfor i in xrange(int(1e6)):\r\n k = (Xn, Yn) = a_b_n(i)\r\n #print i, a, b, (2*a-1)%1000\r\n if F.has_key(k):\r\n #print \"repeat: %d, %d\" % (i,F[k])\r\n break\r\n F[k] = i\r\n\r\ncycle_length = i-F[k]\r\nprint \"cycle length is\", cycle_length\r\n<\/pre>\n\r\ndef do_trial(f):\r\n n = int(f.readline())\r\n if n>cycle_length:\r\n n %= cycle_length\r\n n += cycle_length\r\n t = a_b_n(n-1)\r\n return (2*t[0]-1) % 1000\r\n\r\nf = sys.stdin\r\ncount = int(f.readline())\r\nfor i in xrange(count):\r\nv = do_trial(f)\r\nprint \"Case #%d: %03d\" % (i+1, v)\r\n<\/pre>\n