A bfs week

Codeforces hosted its Round 586 during the Sep 16 - Sep 22 week (problems, results, top 5 on the left, analysis). The somewhat unusual problem difficulty distribution meant the differences between the top competitors were quite tiny, but still mnbvmar was the fastest of all solving six problems in 37 minutes. Well done!

AtCoder Grand Contest 038 took place on Saturday (problems, results, top 5 on the left, analysis). It was one of those days where tourist solved six problems in 79 minutes, and I ended up with three problems after the whole 110-minute round :) Congratulations to him but also to ksun48 and hbi1998 on solving all problems, too!

Problem D has got me stumbled: 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

The general approach was somewhat clear, but I could not dig through all details. Can you?

For the third week in a row, Open Cup was the last round of the week, this time the Grand Prix of SPb (results, top 5 on the left). Even though team Past Glory was the fifth team to solve all problems, more than an hour later than team USA1, they have returned to the top of the standings thanks to having fewer incorrect attempts. Congratulations!

In my previous summary, I have mentioned a Codeforces problem: you are given a connected graph with m<=10⁵ edges, numbered with consecutive integers from 1 to m. For any path, we obtain its cost by writing down the numbers of its edges in sequence without spaces to obtain one huge number. What is the smallest cost of a path from vertex 1 to each other vertex? You need to return the costs modulo 10⁹+7 (but the smallest cost is chosen before the modulo).

The first idea is to notice that multiple-digit numbers are unwieldy, and that we can avoid them by replacing each undirected edge with two directed edges and then inserting auxiliary vertices in the middle of each directed edge splitting it into single-digit edges: instead of a-1204-b, we would have a->1->u->2->v->0->w->4->b and b->1->x->2->y->0->z->4->a. This does not change the costs of simple paths in the original graph, and since our cost function still satisfies the property that taking a subset of edges in a path results in smaller cost, we do not need to consider non-simple paths.

Now we have a directed graph with only single-digit edges, and need to find the shortest path from vertex 1 to each other vertex, breaking ties by taking the lexicographically smallest one. It turns out that we can modify breadth-first search to do it: in the breadth-first search queue, we will maintain which pairs of adjacent elements have exactly the same distance from vertex 1, and which have different distances. Now, when we need to take the next vertex out of the queue to process, we will instead take out the whole block of vertices with the same distance from 1, and then first process all 0 edges from all vertices from the block, then all 1 edges from all vertices from the block, and so on. This allows us to keep adding vertices to the queue in the correct order (by length, then lexicographically), and to maintain the "blocks by equality" in it.

Note that we never need to compare the actual path costs in this solution, therefore we can store them modulo 10⁹+7.

Thanks for reading, and check back for more!