You are not logged in. Please login at www.codechef.com to post your questions!

×

MSTQS - Editorial

8
4

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.

This question is marked "community wiki".

asked 31 Dec '16, 19:35

pkacprzak's gravatar image

6★pkacprzak ♦♦
71483787
accept rate: 12%

edited 31 Dec '16, 22:31

admin's gravatar image

0★admin ♦♦
15.9k347484508


Great question. Great editorial.

link

answered 31 Dec '16, 22:51

ironmandhruv's gravatar image

4★ironmandhruv
333239
accept rate: 20%

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

link

answered 31 Dec '16, 23:41

sajo775's gravatar image

3★sajo775
4324
accept rate: 0%

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

link

answered 01 Jan, 02:46

prakhariitd's gravatar image

6★prakhariitd
1.1k19
accept rate: 10%

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.

(01 Jan, 18:20) pkacprzak ♦♦6★

Please add the problem to the practice section.

link

answered 01 Jan, 02:19

prakhariitd's gravatar image

6★prakhariitd
1.1k19
accept rate: 10%

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?

link

answered 02 Jan, 05:06

prayas_sahni's gravatar image

1★prayas_sahni
311
accept rate: 0%

edited 02 Jan, 05:07

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 21e4. Could you explain what i am missing.
Here is my code-> https://www.codechef.com/viewsolution/12393875

link

answered 03 Jan, 18:18

thedark's gravatar image

5★thedark
862
accept rate: 9%

edited 03 Jan, 18:24

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

(03 Jan, 20:15) pkacprzak ♦♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×1,831
×932
×50
×28
×13
×8

question asked: 31 Dec '16, 19:35

question was seen: 1,317 times

last updated: 03 Jan, 20:15