Editorial for COCI '16 Contest 6 #5 Sirni
Submitting an official solution before solving the problem yourself is a bannable offence.
In this task, we needed to find the minimum spanning tree in a graph where two nodes and are connected with weight . This expression is equal to for and vice-versa.
If two nodes exist with equal values, we can connect them with zero cost and observe them as a single node. Furthermore, we will assume that all node values are unique. For each node value we will iterate over all of its multiples where denotes the largest possible node value. For each such multiple, we will find a node with the minimal value larger than or equal to , and in the case when , the node with the minimal value strictly larger than . We denote this node with , and add the corresponding edge to the list of edges we must process.
By doing this, we have at most edges, which we can use to construct a minimum spanning tree using Kruskal's algorithm. If we naively sort the edges, we will obtain a solution worth of total points, but since all edge weights are up to , we can use counting sort and obtain an algorithm in the complexity of .
We still have to prove the existence of a minimum spanning tree that holds only the edges that we singled out. Let's assume the contrary, that a tree exists that hold another edge, and has a smaller cost that any other tree that holds only the singled out edges. Let that edge be between nodes and . Let and . Then, since we did not single out that edge, nodes exist such that it holds , that is if . But, then we singled out edges . Their total cost is . However, now we can remove edge and instead of it place a path from to or some part of it and therefore have a connected graph with smaller or equal weight.
Comments