MSTQS - Editorial

PROBLEM LINK:

Practice
Contest

Author: Pawel Kacprzak
Tester: Misha Chorniy
Editorialist: Pawel Kacprzak

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graph theory, Minimum Spanning Tree, Kruskal’s algorithm

PROBLEM:

This problem is all about Minimum Spanning Tree, which we call MST here. For a given graph G with N vertices and M weighted edges, the goal is to handle Q queries. Each query can either assign 0 weight to given existing edge in G or assign to a given edge its original weight, or ask for the weight of MST of the current graph G.

QUICK EXPLANATION:

Take a closer look at how does Kruskal’s algorithm work and notice that the answer for each query asking for the weight of the current MST can be computed by running Kruskal’s algorithm only on edges with zero weight and edges in the initial MST of G.

EXPLANATION:

Subtask 1

In the first subtask we have N \leq 200, M \leq 2000 and Q \leq 2000, so we can just keep track of the current weights of the edges while performing queries and for each query asking for the weight of the current MST, we can run any fast algorithm computing MST from the scratch, for example Kruskal’s algorithm. This solution has time complexity of O(Q \cdot f(N, M)), where f(N, M) is the complexity of used MST algorithm on a graph with N vertices and M edges. Notice that this results in O(Q \cdot M \cdot \log^*(M)) time for Kruskal’s algorithm even when full sorting is performed only at the beginning.

Subtasks 2 and 3

In these subtasks we have N \leq 2000, M \leq 2 \cdot 10^5 and Q \leq 20000.

The following approach can be used to solve both of these subtasks, the only difference is that in the last subtask one have to handle restoring original weights of edges, which is just a little bit more straightforward implementation.

Let’s first compute MST of the initial graph before performing any queries and let T be this MST. The crucial observation is that at any point while handling the queries, the weight of the MST of the current graph can be computed by running Kruskal’s algorithm on edges with zero weight at this point and edges of T.

Why is this observation correct? Well, if we take a closer look at how does this algorithm work, we can see that it iterate over a list of given edges in ascending order of their weights and put the current edge into the result if and only if it connects not yet connected components of G. So if we run it on edges with zero weight and edges from T, it will merge some components using some of these zero edges first and then try edges from T if necessary. Since the algorithm is only merging components, it follows that no edge not it T with non-zero edge at this point will be used by the algorithm, because after processing edges with zero weights, some edges from T might not be needed, but if any two components still require to be merged, the algorithm will do it with an edge from T just as it did in the initial graph.

Thus in order to solve the problem, one can maintain the list of edges with zero weights updating it when necessary - this can be done in O(1) time if for example a linked list is used, and for each query asking for the weight of the current MST run Kruskal’s algorithm on at most O(Q + N) edges. Theoretically this results in O(Q \cdot (Q + N) \cdot \log^*(N)) complexity, but notice that in order for K zero edges to be processed by the algorithm, we have to perform K queries adding them first, so the factor of Q^2 is divided by some constant of at least 4 here.

AUTHOR’S AND TESTER’S SOLUTIONS:

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

9 Likes

Great question. Great editorial.

4 Likes

The practice link gives “problem not visible” message. When will the problems be added to the practice section?

2 Likes

Please add the problem to the practice section.

1 Like

Can the order in which zero weight edges are processed, affect the weight of the spanning tree formed, when answering queries?

2 Likes

I thought this would time out.
Is there some upper bound on value of n in O(n) such that it passes tests in ‘t’ seconds?

Great problem @pkacprzak but I am having hard time understanding why is it not giving TLE. I have used following approach:

Made a vector named total of size 2m in which first m are 0 and next m are sorted m edge weights. And I maintain give two ids for each edge one in first half and one in second half therefore each edge has id i and i+m. Now at a time I am setting one id of each edge off and other one on by an array marked. Now whenever query 3 is encountered it runs on whole vector total and according to marked array include the edges. This is making time complexity of O(Q*(N+Q)(log(star)N)).How can it pass when Q is 2*1e4. Could you explain what i am missing.

Here is my code-> CodeChef: Practical coding for everyone

No, it doesn’t affect the weight of MST. Notice that we are interested just in the weight of MST, not the edges it contains. You can try to prove it from the scratch, but perhaps the easiest way to do it is just to see that if you want to compute weight of MST using Kruskal’s algorithm, it sorts all the edges at the beginning by their weights and it doesn’t care what’s the relative order of two edges with the same weight there.

Hi, I’ve just read your code. The only reason I see it passes, is that when you’re processing query 3, you break early from the loop (because you added already n-1 edges), let’s say it happens after O(n) iterations. If this is the case, then probably and unfortunately tests are not as strong as the should and it’s my fault then. You can put some assertions to check how many maximum iterations of this loop are performed to verify this hypothesis. Thanks