Editorial for COCI '20 Contest 2 #2 Odašiljači

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.

First, let's discuss how to check for some fixed radius $r$ $r$ if all antennas can communicate. Two antennas can communicate directly if their distance is at most $2r$ $2 r$ . We can build a graph over antennas, and add edges for all pairs of antennas that are closer than $2r$ $2 r$ . Then, we need to check if the graph is connected, which can be done for example with DFS.

The optimal $r$ $r$ , that is the minimal $r$ $r$ for which the constructed graph is connected, can be found using binary search. For the upper bound, we can put for example $10^9$ $10^{9}$ . The complexity is $\mathcal O(n^2 \log_2 10^9)$ $O (n^{2} \log_{2} 10^{9})$ .

Comments

There are no comments at the moment.