PROBLEM LINK:
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:
- 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.
- 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
-
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.
-
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.