Sirni

Pista 1

Con $10^5$ cartas, hay demasiadas aristas posibles para que la fuerza bruta las considere. ¿Hay alguna forma de recortar la mayoría de estas aristas posibles?

Pista 2

Digamos que tienes una carta de valor $5$ , y otras dos cartas de valores $12$ y $13$ . ¿Es alguna vez óptimo enlazar $5$ con $13$ ?

Solución

Explicación

Siguiendo la primera pista, intentemos construir una lista candidata de aristas que tengan alguna posibilidad de ser incluidas en el MST de Daniel.

Primero, ordenemos las cartas. También podemos no considerar ninguna carta duplicada, ya que esas se pueden enlazar con otras cartas del mismo valor a costo cero.

Ahora, para cada carta $c$ , queremos hallar todas las cartas posibles que podrían enlazarse con ella en un MST. Como las aristas van en ambos sentidos, solo tenemos que considerar cartas con valores mayores que $c$ .

Aquí entra la segunda pista. Haya las cartas que haya en este ejemplo, siempre será óptimo que $5$ se enlace con $12$ en lugar de $13$ .

Para generalizar esto, digamos que tenemos una carta de valor $n$ , y tenemos algunos valores entre $kn$ y $(k+1) \cdot n$ , donde $k$ es algún múltiplo cualquiera. Entre estos valores, siempre tiene sentido elegir el más cercano a $kn$ , porque eso da el menor costo.

Para aplicar esta observación, sí tenemos que hacer algunas precomputaciones para hallar el siguiente valor mayor para cada valor posible de carta, pero esto se puede hacer en tiempo lineal.

Implementación

Complejidad temporal: $\mathcal{O}(N \log{N} + P \log{P})$

C++


#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
// BeginCodeSnip{DSU (from the module)}
class DisjointSets {
  private:
	vector<int> parents;
	vector<int> sizes;
 
  public:
	DisjointSets(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}
 
	int find(int n) { return parents[n] == n ? n : (parents[n] = find(parents[n])); }
 
	bool unite(int n1, int n2) {
		n1 = find(n1);
		n2 = find(n2);
		if (n1 == n2) { return false; }
		if (sizes[n1] < sizes[n2]) { std::swap(n1, n2); }
		sizes[n1] += sizes[n2];
		parents[n2] = n1;
		return true;
	}
};
// EndCodeSnip
 
int main() {
	int card_num;
	std::cin >> card_num;
	vector<int> cards(card_num);
	for (int &c : cards) {
		std::cin >> c;
		assert(c >= 1);
	}
 
	std::sort(cards.begin(), cards.end());
	// podemos borrar los duplicados porque modularlos con el original da 0
	cards.erase(std::unique(cards.begin(), cards.end()), cards.end());
 
	int largest = cards.back();  // ya que ordenamos las cartas
	// next_largest[i] contiene el índice del menor valor de carta que es >= i
	vector<int> next_largest(largest + 1, -1);
	for (int i = 0; i < cards.size(); i++) { next_largest[cards[i]] = i; }
	for (int c = largest - 1; c >= 0; c--) {
		// si todavía no está asignado, asignarle el anterior
		if (next_largest[c] == -1) { next_largest[c] = next_largest[c + 1]; }
	}
 
	vector<vector<pair<int, int>>> good_links(largest + 1);
	for (int i = 0; i < cards.size() - 1; i++) {
		// obtener todas las cartas relevantes con las que esta carta podría conectarse
		good_links[cards[i + 1] % cards[i]].push_back({i, i + 1});
		for (int at = 2 * cards[i]; at <= largest; at += cards[i]) {
			int good_mod = next_largest[at];
			good_links[cards[good_mod] % cards[i]].push_back({i, good_mod});
		}
	}
 
	long long total_cost = 0;
	DisjointSets linked_cards(cards.size());
	for (int c = 0; c <= largest; c++) {
		for (const pair<int, int> &link : good_links[c]) {
			bool result = linked_cards.unite(link.first, link.second);
			total_cost += c * result;
		}
	}
 
	cout << total_cost << endl;
}