Code Jam 2013 Qualification
Posted on 9th April 2015
Continuing, here is the 2013 qualification round.
As ever, the Official Analysis is very good, and similar to my approaches. Some code on GitHub.
Problem A: Trivial.
Problem B: Easy once you realise the "invariant": each cell must equal the maximum height in either the row or column to which it belongs. This gives an \( O(NM) \) algorithm, which is clearly optimal, and seems to require less space than the suggested official solution.
Problem C: This is tricky, and I did some experimentation in an IPython notebook. From this you see that a number which is palindromic and whose square is palindromic, consists of digits 0, 1 or 2, and 2 can only occur at the end or the exact middle. Why?
- There is a nice link better decimal (or any base) expansions and polynomials. Consider a decimal number \( x = \sum_{i=1}^n x_i 10^i \) and the polynomial it induces, \( \sum_{i=1}^n x_i X^i \). The difference is that addition and multiplication (etc.) of decimal numbers has to take account of "overflows" or "carries".
- A simple calculation shows that a palindromic polynomial also has a palindromic square.
- So if no overflows occur in squaring, the same is true for a decimal number.
- This gets you thinking, and a bit of work shows that the converse is true: there can be no carry. Again, the official writeup gives a nice concise (shorter than mine) proof of this.
- A little more work shows that we get no carries if and only if the sum of the squares of the digits is at most 9.
- So it's not too hard to search over all such numbers: this was actually a bit of a hassle to code up, I found.
Problem D: This stumped me. Try a naive DFS: nope! Cheat and look up a hint.
- Notice there is a natural "sub-structure" here: if we have opened some chests, then just forgetting those chests gives exactly the same sort of problem we started with: we have a bunch of keys, and want to open a bunch of chests!
- So, we can handle the "lexicographically smallest" issue as follows: can we open chest 1 at the start, and still win? If so, we best do that (and then "optimally" solve the sub-problem). If not, then, can we open chest 2 at the start and win? If so, do that, else look at chest 3, and so on.
- So really, it's enough to solve the problem: can we win at all?
Here's a different argument which arrives at the same solution to the original problem, but is based more on finding an algorithm rather than an existance proof.
- Say that the "type" of a chest is the key type needed to open it.
- Notice that if we can open one or more chests, and at the end have all the key types (and multiplicies) we started with, and maybe some new keys, then we are in a strictly "better" position.
- If we have n keys of type k and n or fewer chests of type k, just open all those chests, and we're in a "better" position, as we maybe gain some keys and we have no further use for type k.
- Otherwise, for some type k, there are more chests of type k than we currently have keys. To win at all, in total, there must be as many keys around as chests. (*)
- So there is some chest containing k. If we can win at all, there is some "path" whereby we can currently open chest C1, then open chest C2, and so on, finally opening the chest containing k. If we look at the minimal length such path, then (i) C1 must be the only chest we can currently open (else start at Ci, resulting in a shorter path), and (ii) C1 must contain the key to C2, C2 contain the key to C3, and so on (or else we could skip some steps). Hence, if we open all the chests in this path, we use type C1, gain k, maybe gain some other keys, and open some chests.
- So select a key type k we have, and find the minimal path to another key of type k. If the first chest in this path is of type k, then opening the path puts us in a "better" position (we lose and gain key type k). If we can do this step for any type k, then do it.
- Otherwise, I claim we can open a chest of type k at random. If we can win at all, then there is some solution, and suppose I chose "at random" wrongly. Then I can open the "chain" to get a new key k and open the "correct" chest. This uses a key type, l say, but otherwise we don't lose any keys. So if I later need l, there must be a chain which starts with something different to l (we covered the other case above). Either open this chain; or, if we have already opened a chest in the chain, simply start at that chest.
So this actually gives an algorithm which will work, if any solution exists. Let's work a bit harder: we get condition (*) out, and the existance of a "chain" from our starting keys to any key type needed to open a chest. These are necessary conditions to win. I claim they are also sufficient. If not, then pick a counter-example containing a minimal number of chests. Then the above algorithm allows us to open at least one chest and not change either condition, contradiction.
These conditions are, of course, as in the official solution.