An under 23 week

The last week was exclusively on Codeforces. First, Codeforces Round 360 on Wednesday provided top competitors ample time both for solving all problems and for challenging the solutions of others (problems, results, top 5 on the left, analysis). The top 3 stood out because of the challenges, but TooDifficult has also executed everything in the right order - solving before spending too much time on challenging - and thus claimed the first place. Congratulations!

VK Cup 2016 Finals was the main event of the weekend (results, top 5 on the left). Unlike last year, the winning team, built from the top two teams of 2015, didn't really leave the others any chance. Congratulations on the super convincing victory, Adam and Gennady!

My previous summary included a nice TopCoder problem: you are given just one integer k between 1 and 10⁹, and need to construct a bipartite graph with exactly k perfect matchings. Not any such graph will do: it must have at most 20 vertices in each part, and at most 120 edges. There can be more than one edge between the same two vertices, and all those edges are distinct for the purpose of counting the number of perfect matchings. Apart from those restrictions, you're free to construct the graph in any way you like.

I think there are two main approaches to this kind of problem. One is to start with a random solution, and then keep modifying it towards the required property. I don't have a good feeling whether it would've worked in this problem, although I won't be surprised if it would. The other is to learn how to build answers for some values of k, and how to combine those together, and then represent the required number as a sum or product of primitives we know how to build.

Those primitives in this problem are somewhat atypical: the values of k=3ⁿ. It's quite straightforward to construct a graph with exactly 3ⁿ perfect matchings: it will have n vertices in each part, and for each i it will have 3 parallel edges connecting the i-th vertex in the first part with the i-th vertex in the second part. We haven't yet exceeded our limit of 20 vertices in each part, as 3²⁰ is more than 10⁹. Every other value of k can be represented in base-3 as a sum of powers of 3 (each taken 0, 1 or 2 times), but how do we achieve addition of the numbers of perfect matchings?

Well, addition in combinatorial problems usually means that there's a choice: variant a leads to x possibilities, variant b leads to y possibilities, so if we have to choose exactly one of a or b we have x+y possibilities. And matchings lend themselves well to having choices: for each vertex, we have to choose which vertex it will match. So if we want to build a graph with 3ⁿ+3^m perfect matchings, we can make one of its vertices have exactly two adjacent edges, picking one of them would lead to 3ⁿ possibilities of matching the rest of the graph, and the other would give 3^m.

And here comes the "pull an idea out of the blue sky" moment: let's start with a graph with 19 vertices in each part and 3 parallel edges from connecting the i-th vertex in the first part with the i-th vertex in the second part, as before. Now let's add a 20-th vertex to both parts, without adding any edges initially. Then we add one edge from i-th vertex of first part to (i+1)-th vertex of the second part for all i between 1 and 19. The 20-th vertex in the first part still has no adjacent edges: this vertex will be the pivot representing addition. If we want to add 3ⁱ perfect matchings for any i between 0 and 19, we'll add an edge from the 20-th vertex in the first part to the (i+1)-th vertex in the second part. Were a perfect matching to include this edge, it's not hard to see that matching of vertices with numbers (i+1) and up is uniquely determined - we have to use the diagonal edges. The matching of vertices with numbers up to i, on the other hand, must use the horizontal edges, with 3 choices for each, and thus we have exactly 3ⁱ choices in total.

We can represent any sum of powers of 3 between 3⁰ and 3¹⁹, possibly with repetitions, in this way. The base-3 representation of any k up to 3²⁰-1 will require at most 2*20=40 summands, which require 40 edges in our graph. In addition to those, we have 3*19 horizontal edges and 19 diagonal edges, so the total number of edges doesn't exceed 40+4*19=116, which is good enough. Also note that the boundary is quite tight, so other similar constructions might not work.

Thanks for reading, and check back for this week's summary!

Tweet