PROBLEM LINK:Authors: Sidhant Bansal PROBLEMGiven 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:
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$ EXPLANATIONWill 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
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.
This question is marked "community wiki".
asked 12 Jan '18, 19:12

How do we prove that this gives the optimal MST? answered 14 Jan '18, 19:56
