LKYEDGE - Editorial

PROBLEM LINK

Practice

Contest

Author: Fudail Hasan

Tester: Alexey Zayakin

Editorialist: Jakub Safin

DIFFICULTY

HARD

PREREQUISITIES

DFS, dynamic programming on a tree

PROBLEM

You’re given a list E of edges of a graph. For each edge E_i, consider the number f(i) of intervals [L,R] such that L \le i \le R and if the graph contains only edges E_L,\dots,E_R, then E_i lies on a cycle. Compute all f(i).

QUICK EXPLANATION

Compute the minimum R for each L and each i using information for L+1, then use that to compute f(i). Keep a spanning tree using the smallest possible edges, minimum R for all other edges are trivial. The problem reduces to finding the smallest number of a path (for some given paths) covering each edge of the tree; we only need to solve it for all paths ending at the root.

EXPLANATION

Observation number 1: for fixed L,i, let’s take the smallest R such that i is on a cycle for the range [L,R]. Then i is on a cycle for any larger R too. (This is obvious, we’re just adding edges.) That means we only need to compute this smallest R(L) for each L.

First of all, let’s mention that it is possible to compute f(i) independently for each i in linear time. However, we still need them all, so it’s more comfortable to do it differently: for each L, keep incrementing R and adding edges one by one, compute that smallest R(L,i) for all i and use that to directly compute

f(i) = \sum_{L=1}^M M+1-R(L,i)\,,

where we’ll use R(L,i)=M+1 if there’s no such R that edge i lies on a cycle for [L,R].

Doing that in O(M^2) is rather simple. We can add edges one by one. Everytime we add an edge between two different components, we just merge these 2 components, which is even doable in O(M\log{M}) if we’re merging the smaller component into the larger one (standard disjoint set-union). This builds us a tree T_L (actually a forest, but we can add dummy edges). When we’re adding an edge between vertices already in the same component, we know that the smallest R such that this edge i lies on a cycle is R=i; we still need to go through all edges on the path in T_L between vertices it connects and for all of these edges, we know that the maximum R is also i.

However, O(M^2) per each L is too slow. We can speed this up if we notice that it’s better to build T_L first, root it somewhere, compute the 2^k-th ancestor for each k (which allows us to compute LCA-s) and remember the minimum index of those non-tree edges for each vertex v which covers a path to the 2^k-th ancestor for each k.

In the same way as computing LCA, we can split any path into O(\log{M}) sequences of edges. Then, we can use that to compute the minimum index which covers each edge in the tree: if i_1 covers the path from v to its 2^k-th ancestor, i_2 to its 2^{k-1}-st ancestor and i_3 the path between those ancestors, then we can take \mathrm{min}(i_2,i_1) and \mathrm{min}(i_3,i_1) instead of i_2 and i_3 and then forget about i_1. This way, we can put everything from k into k-1 gradually, leaving only k=0, where the paths are just edges in the tree. There are O(M\log{M}) values to process this way.

O(M\log{M}) per each L is good, but probably still too slow. There are 2 parts of the algorithm where it appears and we’ll need to get rid of it in both: constructing T_L (DSU) and computing all minimum R.

Constructing T_L in O(M) is actually pretty easy. When moving from L+1 to L, we add one edge e. We need to find the last edge g on the cycle e created which we’d be adding when constructing T_{L+1} (we can find it e.g. using DFS); this edge should not be in T_L, so we get T_L by removing it and adding e.

What about computing minimum R? For a fixed L, we can’t do much better than the above described O(M\log{M}), but keep in mind that we can use the results from L+1 here as well. Let’s denote the components created after removing that additional edge g by c_1,c_2 (rooted at the endpoints of g); g moves on to become one of those non-tree edges which have R=i.

There are 2 types of paths created by edges \not\in T_L. The first type is only within c_1 or c_2, the second type connects them and therefore must include e. The first such edge gives us R for e; R for all edges \not\in T_L are easily found in O(M). We only have tree edges in c_1 and c_2 to deal with.

Observation 2: R(L,i) \le R(L+1,i). The reason is obvious, if i is on a cycle for [L+1,R], then it’s on a cycle for [L,R] too, since we just added an edge.

Consider the second type of edges. For each tree edge, we can compute the index of the smallest one of them that covers it quickly in linear time – in each component c_{12}, any non-tree edge of this type covers a path from some vertex v_i to the root. We can do bottom-up tree DP computing for each vertex v the smallest edge that covers vertices in its subtree and therefore the edge from it to its parent (except the root, which doesn’t matter anyway). Just take the minimum of its sons and min. i for all edges with v=v_i.

We should know the min. index from edges of the first type too. Fortunately, we don’t need to compute these minima, since we only need to know the minimal R for each edge and if one of these edges gives this minimum for L, then it must have been giving that minimum for L+1 too; thanks to Observation 2, we can simply take R(L,i) to be the minimum of R(L+1,i) and the above computed minimum from type 2 edges. This works because if the min. from type 1 edges for L+1 was x and the min. from type 2 edges was y, then either x \le y and R gives us what we need, or x > y, but then R(L,i) \le y < x. This part clearly also takes just linear time.

Finally we have an algorithm with time complexity O(M) per each fixed L and O(M^2) in total: iterate from L=M to L=1, recompute T_L and all R using the results for L+1 (the initial conditions are trivial) and add M+1-R(i) to f(i) for each edge. The memory complexity is O(M).

Note: we ignored the number of vertices in complexity computations, since we can renumber the edges’ endpoints to \le 2M in O(M\log{M}), which means N=O(M).

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution: Will be uploaded soon.

Tester’s solution

Editorialist’s solution

http://e-maxx.ru/algo/bridge_searching_online

This solves the problem directly , just fix L and keep going right and whenever an edge goes from bridge to nonbridge , update it’s answer.

5 Likes

What’s the complexity when applied to this problem? Seems like O(M^2\log{M}) since N is comparable to M here. (Not saying it shouldn’t pass, it’s pretty much impossible to distinguish between O(\log) and O(1).)

Did you solve the problem using this?

i get full point with O(m^2) …:
for each L we must use union-find and find first circle contain node of edge L. then we can store(L,R) in all edges of cycle… this give use O(m^2) and union-find reduce factor log(n) near O(1)(even i can use more optimization for get lower time)

https://www.codechef.com/viewsolution/15897542

@chemtham Can you explain a bit more ?

Here’s what I understood.

  • For each L, find the minimum R such that a cycle is formed.
  • In the cycle formed, update the edges.
  • Break out of the loop
  • ??

But what about the edges beyond R, which could also have formed a cycle had they been included ?
Can you explain that part ?