A bridge week

Codeforces Round 588 started the Sep 23 - Sep 29 week (problems, results, top 5 on the left, onsite results with one more easy problem, analysis). Um_nik solved six problems almost half an hour faster than other top finishers, therefore it's even surprising that his advantage is only 233 points. Congratulations on the convincing victory!

I have enjoyed coming up and implementing a weird approach to problem E1: consider a bipartite graph with 6 vertices in each half, and each edge existing with a certain probability (these 36 probabilities are given to you). What is the probability that this graph has a perfect matching? The probability needs to be computed modulo 10⁹+7, and the time limit is 7 seconds.

How would you approach this problem?

Almost six days later, Open Cup 2019-20 Grand Prix of Eurasia has wrapped up the week (results, top 5 on the left). The winners of the first three stages lined up on the podium this time, team Past Glory prevailing once again thanks to having much, much fewer incorrect attempts than its competitors. Congratulations!

In my previous summary, I have mentioned a supposedly medium-difficulty AtCoder problem: does there exist a simple connected undirected graph with exactly n vertices and exactly m edges that satisfies the q given constraints (n, m, q<=10⁵) of the following two types:

• for a pair of vertices, there must be exactly one simple path between them
• for a pair of vertices, there must be at least two simple paths between them

For most of the time during the round, I was trying to start from constraints of the second type, incorrectly assuming that such pairs of vertices must be in the same biconnected component. In fact, this is not necessary, since the two paths do not have to be completely disjoint, they just need to differ at some point.

The other approach direction turns out to be more fruitful: consider the (only) path between two vertices from a constraint of the first type. All its edges must necessarily be bridges in our graph, as otherwise we could remove one of them and find another path. Now if we group the vertices into connected components using the constraints of the first type, each such connected component is connected with bridges only (possibly via some intermediate vertices). Therefore for any pair of vertices in such connected component there is exactly one simple path between them, which in turn means that if any two vertices in a constraint of the second type are in one such component, then there is no solution.

Notwithstanding the requirement to have exactly m edges, the above case is the only one when there is no solution at all, because of the following construction: let's take the connected components using the constraints of the first type, build an arbitrary tree of bridges inside each such component, then pick one vertex in each component and connect all of them in one big cycle. In such a construction, for any two vertices inside one component there is exactly one path between them, and for any two vertices from different components there is at least two paths between them.

This construction has n edges (since it has exactly one cycle), which is the minimum possible number of edges if we have at least one constraint of the second type (since we must have at least one cycle then). Now, if instead of connecting the chosen vertices in one big cycle we connect them using a complete graph, we get another valid solution but with a lot more edges: if we have k components, the number of edges is n-k+k*(k-1)/2=n+k*(k-3)/2. It is also easy to see how to achieve any number of edges in between those two values, as we can keep adding edges to the cycle until it becomes the complete graph.

The only remaining step is to notice that we can't have more edges than that. The reason for that is that we can't have more than one edge between two components (otherwise one of the component's edges would not be a bridge, as we could bypass it), and adding more vertices to a component only makes things worse as we're replacing a lot of edges with a single new bridge.

Thanks for reading, and check back for more!