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$ $a$ and $b$ $b$ are connected with weight $\min(P_a \mathbin\% P_b, P_b \mathbin\% P_a)$ $min (P_{a} % P_{b}, P_{b} % P_{a})$ . This expression is equal to $P_a \mathbin\% P_b$ $P_{a} % P_{b}$ for $P_a > P_b$ $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$ $P_{x}$ we will iterate over all of its multiples $k \times P_x \le M$ $k \times P_{x} \leq M$ where $M$ $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$ $x$ , and in the case when $k = 1$ $k = 1$ , the node with the minimal value strictly larger than $P_x$ $P_{x}$ . We denote this node with $y$ $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)$ $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\%$ $70 %$ of total points, but since all edge weights are up to $M$ $M$ , we can use counting sort and obtain an algorithm in the complexity of $\mathcal O(N + M \log M)$ $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$ $a$ and $b$ $b$ . Let $P_a < P_b$ $P_{a} < P_{b}$ and $k \times P_a \le P_b < (k+1) \times P_a$ $k \times P_{a} \leq P_{b} < (k + 1) \times P_{a}$ . Then, since we did not single out that edge, nodes $c_1, c_2, \dots, c_n$ $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$ $k \times P_{a} \leq 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$ $P_{a} < P_{c_{1}} < P_{c_{2}} < \dots < P_{c_{n}} < P_{b}$ if $k = 1$ $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)$ $(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$ $P_{b} - k \times P_{a} = P_{b} % P_{a}$ . However, now we can remove edge $(a, b)$ $(a, b)$ and instead of it place a path from $a$ $a$ to $b$ $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.