Editorial for NINENINE - PELT2019

Problem setter: panik

Problem Code: NINENINE

Difficulty: Medium-Hard

Prerequisites: Finding Bridges in a graph in linear time, Combinatorics, Inclusion Exlusion Principle…

First of all, you need to calculate the bridges in the graph in linear time, since the graph must remain connected at every step i.e during deletion and insertion.
To find this you can read about it in these links:

1.) G4G

2.) youtube video (I personally found this link better than G4G)

After you have obtained the set of Bridges, you now need to precalculate some things which would later prove to be helpful.

1.)save all the edges of the Graph in an unordered Set. This can be done in nearly Linear time.

2.) For each vertex find the count of vertices connected to it having a particular degree for each kind of available degree. Store this information in a vector of maps which contains this information for each node. This can be done in O(M).

3.) Store the count of edges between vertex of degree x and vertex of degree y for all possible edges available in the graph. Store this information in a map which stores the count of edges between a particular degree x to a particular degree y. This can be done in O(M)

4.) Make a frequency array and find the count of vertices of each particular degree.

Now comes the time to finally start calculating all the possible graphs.

Start Traversing all the edges in Graph.

If the edge is available in the set of bridge edges, then skip this edge

If not,

Temporarily reduce the degree of both the vertices of the edge and reflect this change only in the frequency array. So the count of original degree frequencies reduces by 1 and the new degree frequency increase by 1.
This change would be reverted later.

If the degree of both the vertices is same p= (freq[degree]X(freq[degree]-1))/2 -1

Else p= freq[degree1]*freq[degree2] - 1

Now we need to remove some cases from p to remove the cases where multiple edges occurred in some possible graphs i.e edge already exist in the graph. We also need to add some cases in p because of change in the degree of some vertex due to which count of edges between two particular degrees would change, so some extra cases would be subtracted from p when subtracting those edges which already exist in the graph. This can be done by some observation in the graph

Refer to the solution for better clarity.

Author’s solution: click here

Testers Solution : click here

Bonus question: What if I remove the statement that the graph must be connected at each step and replace it with that the final graph should be connected which means that the graph can disconnect during deletion but later during insertion has to become connected again.

Personally, I was not able to find a solution to this question. Lets discuss this in the comment section. I would seriously like to know the solution to this problem.

At first, I missed the statement that graph should be connected at each step and thought of the following solution: Make bridge tree of the graph and calculate the answer corresponding to non-bridges as earlier. For bridges (let u-v), find the components (nodes in the bridge tree) in which u and v lie. Now we need to calculate the number of nodes with a given degree in the subtree of a node of bridge tree. This can be done using euler tour of the tree which is used for subtree queries. Since degree can be upto M, we can store the nodes for each degree and use binary search to get the count of nodes that belong to the subtree. Here, we do not need to worry about formation of multiple edges since it is a bridge.

1 Like

this would solve the bonus question right?

Yeah, I guess so.