Official Analysis (C++)

Solution 1 - Kruskal

Explanation

We can use Kruskal's to find the maximum spanning tree of the graph formed by the teams. First, add all possible edges between two teams to the vector $\texttt{edges}$ and sort it in decreasing order of edge weight. For each edge, if we can unite the connected components of the two vertices, then we have eliminated one team. Increment $\texttt{eliminated}$ by $1$ and add the edge weight to our answer, $\texttt{ans}$. Once $n - 1$ teams have been eliminated, we can print $\texttt{ans}$.

Kruskal's Implementation

Time Complexity: $\mathcal{O}(N^2 \log N)$

Copy
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 2000;
int parent[MAX_N];
int compsize[MAX_N];
struct Edge {

Solution 2 - Prim

Explanation

We can treat the different teams as nodes in a graph, and treat each possible pairing of two teams as an edge.

For each edge, its weight is equal to the XOR of the two node ids.

So, we would like to find the maximum spanning tree in this graph by connecting the edges with the weights.

There are 2 steps in doing so:

1. Find an unvisited node with the greatest weight, and add it to the MST.
2. Re-evaluate all the edge weights from the MST to the other unvisited nodes.

We can repeat these 2 steps until all N nodes are in the maximum spanning tree.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
import java.io.*;
import java.util.*;

public class Superbull {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("superbull");
		int N = io.nextInt();

		int[] ids = new int[N];
		for (int i = 0; i < N; i++) { ids[i] = io.nextInt(); }