ROUTES - Editorial

editorial
, , , ,
1

Problem Link:

Practice

Contest

Difficulty:

Medium-Hard

Pre-requisites:

Biconnected Components

Problem:

Maintain the sum of biconnected components’ sizes squares during adding the edges in the graph.

Explanation:

Solution to sub tasks 1, 2, 3:

Let’s solve the following problem: you are given a graph, calculate the number of unsafe unordered pairs of vertices in it. It’s naturally the same as: calculate the number of ordered unsafe pairs of vertices and then divide it by two. Another observation is that the number of unsafe pairs equals to the number of all possible pairs minus the number of safe pairs of paths. So, we will solve this modified problem.

This time we will find the O(N+M) solution to a single query. The number of all possible pairs is naturally the sum of squares of the connected components’ sizes and the number of safe pairs is the sum of squares of the biconnected components’ sizes. Finding biconnected components is a very standard problem, generally you can obtain the new graph where connected components correspond to the biconnected components of the initial graph if you remove all the bridges from the initial graph.

So, we have solved our problem in O(M(N+M))* time. But it’s not enough to get 100 points.

Solution to all the sub tasks:

The problem can be solved in O(N log N+M) time. We will keep the idea from the previous solution, generally, we have to maintain two sums: the sum of squares of connected components’ sizes and the sum of squares of biconnected components’ sizes.

It’s very easy to maintain the first sum. We can use the DSU in order to do it in O(1) time. When the edge is added, it can change nothing or it can merge two different connected components. In the second case we just decrease the sum by squares of these two components’ sizes, merge them and then simply add the square of the size of the new connected component.

Now, how to maintain the sum of squares of biconnected components’ sizes. At first, we have already noted the fact that if we remove all the bridges, we’ll obtain biconnected components. Now, let’s note that if we shrink these biconnected components to the single vertice, and then add all the bridges again, we’ll obtain forest. There will be no cycles because the cycle would add one more BCC. Let’s have another DSU, where we will store the information about to which BCC every vertice belongs.

So, when we add an edge, there are three possible cases:

  1. Both vertices of the edge belong to the same BCC - this edge will not change anything.

  2. The edge connects two different connected components - connect these components (there will be an important notice about this below) and modify the first sum, as it is described above.

  3. The edge connects two different biconnected components that belong to the same connected component - well, this is the hardest case…

Generally, in the third case, we add an edge to the tree. Obviously, it forms the cycle. And now we have to find the cycle and to shrink it to the single vertice. Naturally, it is OK to do it in O(cycle) time. Let’s say that the forest of BCCs is denoted by the ancestors’ array pr[]. So, we can find the LCA of these vertices simply by going up in this tree until we find some vertice that is an ancestor of the both - the first and the second vertice (let’s call them X and Y). Then we just merge all the vertices of this cycle in the BCCs’ forest and in the BCCs’ DSU and recalculate the sizes of the biconnected components.

The last important observation is that in the second case we can’t just change the value of either pr[x] or pr[y] because both x and y might be non-root vertices of their trees. So, we have to make one of these vertices a root one, because it’s obvious that only the root doesn’t have any ancestors. But which vertice should become the root of its tree? It can be proved that if we make the vertice from the smallest tree root, we will obtain amortized O(N log N) complexity. To make the vertice a root one, we just “lift” it up the tree, till the moment, when this vertice doesn’t contain any ancestor.

Summing up these facts, we finally obtain an O(N log N+M) solution to the problem that scores 100 points. The solution is an online-one, and I’ve thought of making online-type queries, but I’ve decided not to do it because, I believe, if an offline solution exists, it isn’t much easier than the provided one.

Setter’s Solution:

Solution to subtasks 1, 2 and 3 can be found here

Solution to all the subtasks can be found here

Tester’s Solution:

Can be found here

4 Likes
2

I would like to say that the way the problem statement was formulated seemed to suggest that there can be AT MOST one direct road connecting a pair of cities - see the following phrase taken from the problem statement: “On the i-th day, the road connecting the towns Ai and Bi will be built.” (I added the text “the road” in bold myself). In fact, most test cases contained at least one pair of cities multiple times (with the meaning that there are multiple direct roads built between that pair of cities). A more appropriate formulation would have been to say that “a road between the cities Ai and Bi will be built”. Although the problem statement did not explicitly forbid the existence of multiple roads between the same pair of cities, this formulation made me believe that there can be at most one road between each pair of cities (and I’m sure that I’m not the only one who misunderstood this).

A second observation is related to a question asked by @utkarsh_lath about finding the LCA of two biconnected components. An alternative to the one presented in the editorial is to use the fact that the queries are, in fact, offline. Thus, we can build a tree with all the edges that are ever bridges in the beginning (we can find them using DSU). Then, we can build a segment tree over the vertices of this tree (actually, the tree can be a forest, but this won’t pose any problems). Whenever two biconnected components are unified together, one of them is, in fact, lifted one level higher - in fact, the whole subtree of that component is lifted one level higher. Thus, we can update a whole interval of vertices in the segment tree meaning that their depth in the tree decreased by one. This way, we can use the standard technique of finding the LCA, because we can always find the depth in the tree of a biconnected component (by asking a query to the segment tree). I did not implement this approach, yet, but I will implement it soon in the Practice section.

2 Likes
3

Well… If we first calculate the depth of each node , cliimb up step by step to find the LCA and union the nodes we pass through in the union-find sets, the complexity will reduce to O((N + M)α(N))

See this solution for details: CodeChef: Practical coding for everyone

2 Likes
4

It is not clear how to find LCA by simply going up the tree from both nodes, because they might be at different heights.

5

@utkarsh_lath, we lift from these two nodes alternately, until we get some node that is an ancestor of the both of them (generally, until we get the node that was marked as used)

1 Like
6

very smart technique to find LCA :slight_smile:

7

tester’s solution missing.

8

Can you please clarify, what does “edges that are ever bridges” mean? Are they bridges after all queries? Or bridges when they are just added to the graph?

9

@mmaxio: The second - bridges when they are just added to the graph.

10

I accidentally stumbled across this paper online, which addresses exactly this problem and more (except for maintaining the sizes of the biconnected components, which would be very easy to add): http://alexandria.tue.nl/repository/books/371273.pdf

The paper even uses the same technique mentioned in the editorial for finding the LCA of two biconnected components in their biconnected component tree.