Editorial for COCI '16 Contest 6 #5 Sirni


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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 a and b are connected with weight \min(P_a \mathbin\% P_b, P_b \mathbin\% P_a). This expression is equal to P_a \mathbin\% P_b for P_a > P_b 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 P_x we will iterate over all of its multiples k \times P_x \le M where M denotes the largest possible node value. For each such multiple, we will find a node with the minimal value larger than or equal to x, and in the case when k = 1, the node with the minimal value strictly larger than P_x. We denote this node with y, and add the corresponding edge to the list of edges we must process.

By doing this, we have at most \mathcal O(M \log M) 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 70\% of total points, but since all edge weights are up to M, we can use counting sort and obtain an algorithm in the complexity of \mathcal O(N + M \log M).

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 a and b. Let P_a < P_b and k \times P_a \le P_b < (k+1) \times P_a. Then, since we did not single out that edge, nodes c_1, c_2, \dots, c_n exist such that it holds k \times P_a \le P_{c_1} < P_{c_2} < \dots < P_{c_n} < P_b, that is P_a < P_{c_1} < P_{c_2} < \dots < P_{c_n} < P_b if k = 1. But, then we singled out edges (a, c_1), (c_1, c_2), (c_2, c_3), \dots, (c_{n-1}, c_n), (c_n, b). Their total cost is P_b - k \times P_a = P_b \mathbin\% P_a. However, now we can remove edge (a, b) and instead of it place a path from a to b or some part of it and therefore have a connected graph with smaller or equal weight.


Comments

There are no comments at the moment.