×

SPANTREE - Editorial

Authors: Sidhant Bansal
Testers: Jingbo Shang, Istvan Nagy
Editorialist: Vaibhav Tulsyan

PROBLEM

Given that there exists an undirected weighted connected graph with $N$ vertices, find the total weight of its Minimum Spanning Tree.

You can perform 2 kinds of queries:

1. Provide 2 non-empty, non-intersectin sets of vertices $A$ and $B$ as input to the judge and get the minimum weighted edge between any pair of nodes $u \subseteq A$ and $v \subseteq B$. If there is no such edge, the judge returns -1.
2. Send the weight of the MST to the judge.

The cost of performing a query is $|A|$. The max cost that can be incurred is $10^4$.

Constraints:

$2 \le N \le 1000$

$1 \le weight_{edge} \le 10^5$

EXPLANATION

Will Kruskal's/Prim's Algorithm work?

Primitive Kruskal / Prim will not work. Kruskal's wont work because we will perform $N^2$ queries - once for each pair of nodes, where the cost for each query will be $1$.

For Prim's the set of nodes you know the answer for, will keep on increasing. Hence, the cost for the queries would be something like: $1, 2, 3, ... , N/2, N/2, (N/2 - 1), ..., 3, 2, 1$. Hence, the cost would be of the order $O(N^2)$.

Approach

1. Find the nearest node of each node $u$ by using a query of the format: $[u]$ vs. all except $u$.

• This gives us connected components of size $2$.
2. In increasing order of component size, we can continue to perform queries like: [component] vs. [all except component].

You can observe that after every query, the component's size gets doubled.

Since the size of a component always gets doubled, we can say that every vertex occurs as a vertex in $A$ at most $log(N)$ times. Components can be maintained using a DSU.

Each vertex contributes $1$ to the net cost. Hence, the overall cost is bounded by $O(N * log(N))$.

Since the value of $N$ is at most $1000$, our bound ensures that the max cost of $10^4$ is never exceeded.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester 1's solution can be found here.
Tester 2's solution can be found here.

This question is marked "community wiki".

3.4k194377
accept rate: 16%

19.8k350498541

 0 How do we prove that this gives the optimal MST? answered 14 Jan '18, 19:56 2.6k●1●10●34 accept rate: 7%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,851
×1,236
×202
×94
×72
×72
×24
×4

question asked: 12 Jan '18, 19:12

question was seen: 515 times

last updated: 20 Feb '18, 16:57