Posted on 6th May 2015
Busy at 5pm Saturday when this ran (so all the eggs in the final basket of round 1C). Under timed conditions, I did problem A very slowly, and B-small in the time, so would have qualified at around place 770. B-large took a bit longer, and Problem C wasn't really looked at in the time limit. Hard problems...
As ever, links to: Official Contest Analysis and my code on GitHub.
Problem A, Counter Culture: How fast can you get from N from 1 if you are allowed moves of: say one more than the last numbers; or reverse the decimal number. E.g. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23 is the quickest route to 23.
My solution is the same as the official one, but my reasoning is different (and was, under pressure, motivated by some interactive experiments with a brute-force dynamic programming solution). Notice that:
Let's think about "invariant". I've been reading the excellent book "Information Theory, Inference, and Learning Algorithms" by David MacKay and he uses the term "Lyapunov Function" for any function which decreases with each step of an algorithm: this can be used to prove convergence. We'll use a similar idea here.
Suppose the target number is of even length and we've already got to 100...000 of the same length. Think about working backwards from N. So the moves become "decrease" or "reverse" (but now we are not allowed to reverse a number ending in 0). Let n1 be the lower half of the number, and n2 be the upper half, but reversed, so for example, N = 123456 gives n1 = 456, n2=321. Then the "reverse" move swaps n1 and n2 while the "decrease" move will either decrease n1, or if n1 = 0 then n1 becomes 9...9 and something complicated happens to n2 (the most significant digit is decreased, with "borrows" going down). In particular, we see that n1 + n2 is left unchanged by "reverse", decreases by 1 if n1>0, or increases perhaps by a lot. From this observation, it's now easy to see that the following algorithm is optimal:
n1=1.n2=1 and n1 is something else.n1=1, and we've arrived at 10...01Optimal because it decreases n1+n2 at all steps except the "reverse"; any other algorithm must increase n1+n2 at some point.
When the target number is odd length, we argue in a similar way, with a new number n3 being the middle digit, and the new invariant being n1 + n2 + 10^k n3 where 10^k is the correct power to put n3 in the right place, e.g. if N = 12345 then n1=45, n2=21, n3=3, 10^k = 100. We now decrease until n3=0, n1=1 and then reverse and then decrease again.
Problem B, Noisy Neighbors: Just a special case optimisation problem. Brute force the small case, and my large case solution is no different to the official solution.
Problem C, Hiking Deer: This was fun, and admits a nice analysis. Herbert wants to avoid hikers, and at first it seems we have to consider the interaction of hikers; but this is not so. Consider Herbert aiming to complete his walk in time T. Then Hikers can do the following (perhaps the same hiker does all these at different times):
1 <= D < 360) and gets to degree 360 == 0 at time < T. Then Herbert can avoid the hiker.>= T. Herbert must meet the hiker at least once.< T and gets to degree 360 == 0 again next at time <= T. Herbet must meet the hiker at least once.< T and gets to degree 360 == 0 again next at time > T. Herbert can avoid.Notice that Herbert can make the optimal number of encounters by choosing a constant velocity path. So we may assume that Herbert indeed moves at constant speed, and just check which time T is best. For the small cases this is easy, but the Large case needs a trick, e.g. a Heap based priority queue as in the offical solution, which even in Python is plenty fast enough.