Skip to Content
CTRL K

Superbull

Análisis oficial (C++) 

Solución 1 - Kruskal

Explicación

Podemos usar Kruskal para encontrar el árbol de expansión máxima del grafo formado por los equipos. Primero, agregamos todas las aristas posibles entre dos equipos al vector edges\texttt{edges} y lo ordenamos en orden decreciente de peso de arista. Para cada arista, si podemos unir las componentes conexas de los dos vértices, entonces eliminamos un equipo. Incrementamos eliminated\texttt{eliminated} en 11 y sumamos el peso de la arista a nuestra respuesta, ans\texttt{ans}. Una vez que se eliminaron n−1n - 1 equipos, podemos imprimir ans\texttt{ans}.

Implementación de Kruskal

Complejidad temporal: O(N2log⁡N)\mathcal{O}(N^2 \log N)

#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 {
	int from, to, weight;
};
 
// BeginCodeSnip{Standard DSU operations}
void init(int n) {
	for (int i = 0; i < n; i++) {
		parent[i] = i;
		compsize[i] = 1;
	}
}
 
int find(int a) {
	if (a == parent[a]) { return a; }
	return parent[a] = find(parent[a]);
}
 
bool unite(int a, int b) {
	int roota = find(a), rootb = find(b);
	if (roota == rootb) { return false; }
	if (compsize[roota] > compsize[rootb]) { swap(roota, rootb); }
	parent[roota] = rootb;
	compsize[rootb] += compsize[roota];
	return true;
}
// EndCodeSnip
 
int main() {
	freopen("superbull.in", "r", stdin);
	freopen("superbull.out", "w", stdout);
	int n;
	cin >> n;
	int ids[MAX_N];
	for (int i = 0; i < n; i++) { cin >> ids[i]; }
	vector<Edge> edges;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) { edges.push_back({i, j, ids[i] ^ ids[j]}); }
	}
	init(n);
	// ordenar las aristas en orden decreciente de peso
	sort(edges.begin(), edges.end(),
	     [](Edge a, Edge b) { return a.weight > b.weight; });
	int eliminated = 0;
	long long ans = 0;
	for (Edge e : edges) {
		if (unite(e.from, e.to)) {
			eliminated++;
			ans += e.weight;
			// si se eliminaron todos los equipos menos 1
			if (eliminated == n - 1) {
				cout << ans << endl;
				return 0;
			}
		}
	}
}

Solución 2 - Prim

Explicación

Podemos tratar a los distintos equipos como nodos en un grafo, y tratar cada emparejamiento posible de dos equipos como una arista.

Para cada arista, su peso es igual al XOR de los dos ids de nodos.

Así, queremos encontrar el árbol de expansión máxima en este grafo conectando las aristas con los pesos.

Hay 2 pasos para hacerlo:

  1. Encontrar un nodo no visitado con el mayor peso, y agregarlo al MST.
  2. Reevaluar todos los pesos de arista desde el MST hacia los demás nodos no visitados.

Podemos repetir estos 2 pasos hasta que los N nodos estén en el árbol de expansión máxima.

Implementación

Complejidad temporal: O(N2)\mathcal{O}(N^2)

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(); }
 
		long max_cost = 0;
		boolean[] visited = new boolean[N];
		int[] score = new int[N];
 
		for (int i = 0; i < N; i++) {
			int node = -1;
 
			// Encontrar un nodo no visitado con el puntaje más alto.
			for (int j = 0; j < N; j++) {
				if (visited[j]) { continue; }
				if (node == -1 || (score[i] > score[node])) { node = j; }
			}
 
			// Agregar este nodo al MST.
			max_cost += score[node];
			visited[node] = true;
			System.out.println(node);
 
			// Reevaluar todos los demás puntajes de nodos.
			for (int j = 0; j < N; j++) {
				score[j] = Integer.max(score[j], (ids[node] ^ ids[j]));
			}
		}
		io.println(max_cost);
		io.close();
	}
	// CodeSnip{Kattio}
}
Fundamentos