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

×

SPANTREE - Editorial

PROBLEM LINK:

Practice
Contest

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".

asked 12 Jan '18, 19:12

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

edited 20 Feb '18, 16:57

admin's gravatar image

0★admin ♦♦
19.8k350498541


How do we prove that this gives the optimal MST?

link

answered 14 Jan '18, 19:56

mathecodician's gravatar image

6★mathecodician
2.6k11034
accept rate: 7%

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:

×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