A week with division by zero

TopCoder SRM 658 continued the recent trend of Tuesday rounds (problems, results, top 5 on the left). The hardest problem gave one the most freedom, as it admits several different approaches: consider a bipartite graph with equal number of vertices in both left and right parts. You need to find a non-empty matching (set of edges with no common endpoints) in this graph such that for all vertices covered by the matching in the left part all their neighbors are covered by the matching in the right part. In other words, there should be no way to replace just one edge in the matching with another edge with the same left end. If you’ve already solved this one after reading it, here’s a much harder follow-up from the problemsetter, cgy4ever: what if the total number of vertices in the left and right parts are not necessarily equal? I don’t have a solution for the follow-up yet.

Codeforces Round 302 took place two days later (problems, results, top 5 on the left). Problem D turned out to be the trickiest one, with just 73 solutions accepted for 352 contestants that submitted it. Of course, that also gave rise to a plenty of challenge opportunities. Let me describe one of the more subtle bugs, but first, let’s remember the problem statement.  A green coloring of a rooted tree is such coloring of its edges into green and white such that every path from a leaf to the root contains at most one green edge.  Given an unrooted tree, how many green colorings exist for each possible choice of the root?

When the root is given, counting green colorings can be done via quite standard dynamic programming. In order to solve the problem for all possible roots many contestants including myself updated the total number of colorings as we move the root from a vertex to one of its neighbors. It’s actually not very hard to see how this number should be updated, but it comes with a twist: such update involves dividing the old number by one plus the number of valid colorings for a subtree, and since we’re computing the answer modulo 10⁹+7 (as requested by the problem statement), division is not always possible!

When one implements the above solution in the most straightforward way, it might fail if a subtree of the input tree has exactly 10⁹+6 possible colorings, or more generally k*(10⁹+7)-1 for any positive integer k. It doesn’t look extremely likely to happen at random, but given the existence of challenges on Codeforces, many people were bound to spend some effort creating such testcases, and thus we’ve actually got plenty: some are described in the post-match discussion. Can you come up with such testcase without reading the discussion?

TopCoder Open 2015 Round 1C was the last chance to hop on the TopCoder Open train (problems, results, top 5 on the left). krijgertje, who was once ranked fourth overall but has stopped competing regularly, came out from retirement and claimed the first place thanks to fast solutions and some challenges - congratulations!

And finally, Google Code Jam 2015 Round 1C has determined the final 1000 qualifiers for this year's tournament (problems, results, top 5 on the left, analysis). Congratulations to Klockan on solving all problems just under 40 minutes, and good luck to all 3000 qualifiers in Round 2!

Thanks for reading, and check back tomorrow for this week's summary :)

Tweet