Editorial for Yet Another Contest 6 P1 - No More Separation - Olympiads Online Judge

Editorial for Yet Another Contest 6 P1 - No More Separation

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.

Author: Josh

Let's rephrase this problem in terms of graph theory. We are required to generate a connected graph with $N$ $N$ nodes and $M$ $M$ bidirectional unweighted edges, such that sum of distances between all pairs of nodes is minimised.

Subtask 1

In this subtask, the graph is a tree. We can show that the optimal tree is a star graph, in which one node is connected to every other node. This is because there must be exactly $N-1$ $N - 1$ pairs of nodes which are a distance of $1$ $1$ apart in any construction, and for the remaining pairs of nodes, the star graph guarantees that they are a distance of $2$ $2$ apart.

Time complexity: $\mathcal{O}(M)$ $O (M)$

Subtask 2

Again, there must be exactly $M$ $M$ pairs of nodes which are a distance of $1$ $1$ apart, so any construction which guarantees that all remaining pairs of nodes are a distance of $2$ $2$ apart will be optimal. This can be achieved by starting with a star graph, and repeatedly adding edges until there are $M$ $M$ edges in total.

Time complexity: $\mathcal{O}(M)$ $O (M)$

Comments

There are no comments at the moment.