Jam 2014 Round 1A

Posted on 17th April 2015

As ever, links to: Official Contest Analysis and my code on GitHub.

Of current interest is how to progress: top 1000 people go through, and for that you'd need 55 points in a reasonable time. That is, solve all but the tricky statistics based question, Problem C.

Problem A, Charging Chaos: The problem is the find a "mask" which when xored with each outlet gives each device. Of course, what makes this tricky is that there is also an unknown permutation to find, to map the outlets bijectively to the devices. But you can find these iteratively:

  • For the first bit, try the mask having bit 0: then you partition the outlets into two sets, those with bit 1 having 0, and those with bit 1 being 1. Also partition the devices similarly, and then the sets need to match in size for a bijection to exist. Similarly if the mask has bit 1 (then 0 for outlet maps to 1 for device).
  • Then carry on, further subdividing the sets
  • This gives a Backtracking algorithm, or, what amounts to the same thing, a Depth First Search with pruning.
  • This is rather different from the official solution.

Problem B, Full Binary Tree: I solved this using a recursive algorithm:

  • Notice that a full binary tree (FBT) has a nice "sub-problem" property: if you delete the root and each child of the old root into roots of new subtrees, then you get either two empty trees, or two rooted FBTs.
  • Input is a tree (and we're told it's a tree)
  • Try each node as the root of our eventual FBT.
  • If it has degree 1, then we'll have to delete everything below it.
  • If it has degree greater than 2, then we need to decide which children to delete:
    • Examine each in turn, and see what the smallest number of nodes to delete to make it into a FBT is.
    • Select the best 2
  • Note that the task above is exactly the same task as we're performing overall.

Thus we get the following: - For a given root, consider each child. Let \( S_i \) be the total size of the tree rooted at that child, and let \( C_i \) be minimal number of nodes to delete to turn this into an FBT. - We can find these recursively: \( S = 1 + \sum_{\text{children}} S_i \) - For \( C \) we want to find \( i_i, i_2 \) to minimise \[ C_{i_1} + C_{i_2} + \sum_{i\not= i_1, i_2} S_i = \sum_i S_i + (C_{i_1} - S_{i_1}) + (C_{i_2} - S_{i_2}) \] which is easily found by selecting the two smallest terms of the sequence \( C_j-S_j \). - Recursion doesn't work, so in the end, my code using a "dynamic programming" approach, building up these numbers from the leaves upwards. - See the official writeup for a linear time algorithm.

Problem C, Proper Shuffles: I noddled around with this for a bit, got half-way, and then gave up and cheated. Should have remembered "naive bayes classifiers" as the keyword! See the writeup as an IPython Notebook.

Categories
Recent posts