GERALD07 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Gerald Agapov
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Sqrt Decomposition, Link-Cut Tree

PROBLEM:

Given an undirected graph, with N nodes and M edges, answer Q queries – how many connected components are there, if we only admit the l-th edge to r-th edge?

EXPLANATION:

I know two solutions for this problem. The first one is Link-Cut Tree related, using O((Q + M)logN) time. The second one solves the problem via Sqrt Decomposition, using O((Q + M)sqrt(M)) time.

Both solutions are offline solutions. That is, we first load all queries, and then deal them in some order we defined.

Link-Cut Tree solution

Sort the queries ascending by their right ends. Use a Link-Cut Tree maintaining the maximum spanning tree (forest, if edges are not enough) using the edges from 1-st to r-th (the weight of a edge is its sequential number. The 1-st edge is weighted 1, 2-nd is 2, …). This can be done because we can use the Link-Cut Tree to find the minimum edge between two tree-node, then delete it and insert the new edge in O(logN) time.

For a query of [l, r], count the number of edges with weight larger than or equal to l, denoting it as C. This can be done by some other data structures, like Segment Tree or Fenwick Tree. Also, it requires O(logN) time for each update of edges in the maximum spanning tree. Then, the answer of the query, is N - C.

The correctness of this algorithm can be proven by the Kruskal algorithm. First, greedily apply it to the edges from r-th to l-th (in the described order) and get a spanning tree. It should be a part of the spanning tree got by greedily applying it to the edges from r-th to 1-th.

Sqrt Decomposition solution

Similar to Codeforces 86D, which is the first problem I saw this method using as an offline algorithm, this problem can be solved by the Sqrt Decomposition.

If you can solve that problem, then, the idea here is quite simple:

  1. divide 1…M edges into sqrt(M) blocks, each has sqrt(M) edges.
  2. group the queries by the block IDs of their left ends.
  3. for all queries in the same group (begin at the same block), sort them ascending by their right ends.

Now, we are considering the queries begin at the same block:

  1. scan the queries one by one and use a union-find set to maintain the connectivity of subgraph consisting of edges from the first edge of the next block to the last edges of the current query.
  2. For the edges between the left end of the current query and the last edge of the beginning block (at most sqrt(N) edges here, because they are in the same block), run some brute-force union operations to merge them to get the answer.
  3. After the brute-force merge, we need to restore the union-find set we maintained before. Because there are at most sqrt(N) merge operations, we can record the places we changed (at most sqrt(N), too) and restore them.

Therefore, we can solve this problem in O((Q + M)sqrt(M)) time using this idea.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

8 Likes
2

@shangjingbo I did not get any of the solution mentioned at all, could you please add some more explanation !!!

2 Likes
3

Can any one provide some good tutorial to link-cut tree and heavy light decomposition as these data structures are many times needed to solve the 9th-10th problem. I searched on internet and i got some implementation also but did not got any good tutorial on these two, by studying which one can code the thing himself.

4

note: it is brought to our attention that some users ask live-contest related problems on SO. and some of them even get better and right answers. as @niklasb mentioned on CF i suggest to grow strong on SO. during live contest, by frequenting more on SO, those questions could be detected and flagged. i dont think @niklasb has answered that intentionally, he is there just to help. and there is another problem, you just cant delete your posts on CF.

gojira’s notice

2 Likes
5

Author here, I answered gojira’s question. I have to add, more presence on Stack Overflow’s [algorithm] tag could help fight this problem in the future, since this stuff happens all the time (questions about running contests being answered).

2 Likes
6

I think you will have to look more into research material (papers, lecture notes etc.) rather than “tutorials”. A good starting point would be Wikipedia, which also contains references to the original ST-Tree paper and some lecture notes. I can personally recommend the videos of Erik Demaine’s lectures about advanced data structures. Lecture 19 from 2012 is the one where he talks about dynamic trees. The one after that is about Euler-tour trees, amongst others

3 Likes
7

First understand bottom-up splay trees thoroughly, as they are the basis for the most practically efficient dynamic trees. Thing is, the big-O constant for dynamic trees is substantial – I submitted a solution using my extensively tuned dynamic tree library, and it was four times slower than my other solution that just used parent pointers. They’re still worthwhile in some cases though.

1 Like
8

@niklasb i read your answer bro. i know you havent done that intentionally. and i agree with you on growing stronger on SO as a CP community. anyway, if you wish, i can delete my answer here. my intention was not to give bad image to you @niklasb, im aware of your efforts to help to CP community and thanks for your help

9

You can leave the answer if you want, in fact it is good that people get directed to my response

2 Likes
10

ok bro, i hope i dont discourage you from helping us by posting good tutorials, answers, etc

11

@shangjingbo: Can you provide the explanation of these two logic using one small example? It seems a bit hard to follow the link cut tree part since I am new to this topic .

12

look at here: http://codeforces.com/blog/entry/7383#comment-161520

13

Thanks a lot both of you.

14

You can assume there is a black box (link-cut tree), which supports finding the minimum edge on the path between two tree nodes and deleting/inserting an edge to a tree in O(logN) time.

15

After that, you can search some materials to learn the LCT, as niklasb mentioned.

16

We had this exact same problem on the list of candidate problems for the Romanian IOI selection contests, which usually take place in April-May each year, with the sqrt decomposition solution in mind. We’ll now have to erase it from that list. On one hand it’s a pity that we lost a nice problem that we could have used for the contests in Romania. On the other hand, I didn’t have to spend any time to think about the problem - I just implemented the solution that I already knew.

1 Like
17

@shangjingbo: thanks. I couldn’t understand because of not knowing LCT well . Now I have read it and therefore understood what your solution meant.

18

Please elaborate more on the relation between experiment_id and node.auxiliary in solution of tester link.

By now, I am thinking that the node.auxiliary field is represent for the primary without taking into account all edges from Query Q.left to right = MIN(Q.right, (L + 1) * MAX_SZ - 1);

Therefore, I made some trivial modification like these:

In function

int FindPrimaryAux(int a)
{
if(node[a].primary == a) return a;		
node[a].experiment_id = nexperiment;
return node[a].primary = node[a].auxiliary = FindPrimary(node[a].primary);
}

I changed to

int FindPrimaryAux(int a)
{
node[a].experiment_id = nexperiment;
if(node[a].primary == a) return a;		
return node[a].primary = node[a].auxiliary = FindPrimary(node[a].primary);
}

This change leads to Runtime Error

Or if I change to

int FindPrimaryAux(int a)
{
if(node[a].primary == a) return node[a].auxiliary = a;		
node[a].experiment_id = nexperiment;
return node[a].primary = node[a].auxiliary = FindPrimary(node[a].primary);
}

It leads to Wrong Answer.

Could Manbubul Hasan give me the answer, please ?

19

Can you tell how do we restore the the union find at the end of merge operations ?

20

Terima kasih dan salam kenal.
codechef Link

code Link