GCD and MST

Explicación

Como en el algoritmo de Kruskal , generamos nuestro MST agregando aristas de forma voraz. Excepto las aristas entre dos elementos adyacentes cualesquiera del arreglo que cuestan $p$ , una arista solo existe entre $i$ y $j$ si el máximo común divisor de todos los elementos en $[i, j]$ es igual al mínimo del rango $[i, j]$ .

Como el costo de estas aristas es el elemento mínimo del rango, iteremos por todos los elementos del arreglo en orden ascendente. De esta forma, garantizamos que siempre agregamos aristas de costo mínimo. Sea el elemento actual $a[k]$ . Hay una arista entre $k$ y $k - 1$ si $a[k]$ divide a $a[k - 1]$ . En ese caso, podemos ir más allá a $a[k - 2]$ y así sucesivamente hasta que $a[k]$ ya no divida a $a[k - i]$ , o cuando los dos elementos ya están conectados. Aplicamos la misma operación en la otra dirección ( $k + 1$ , …).

Detenemos la iteración cuando el costo de la arista (= el valor del elemento) es mayor que $p$ . Para todos los componentes que aún no están conectados, podemos simplemente conectarlos con costo $p$ . Si contamos el número de aristas $c$ ya agregadas, y como un MST tiene $N - 1$ aristas, podemos agregar $p \cdot (N - 1 - c)$ a la respuesta.

Como los componentes conexos son siempre un segmento en el arreglo, solo tenemos que considerar $\mathcal{O}(N)$ aristas.

Implementación

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

C++Python


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
 
/** Solves a single test case. */
void solve() {
	int n, p;
	cin >> n >> p;
	vector<int> arr(n);
	vector<int> indices(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		indices[i] = i;
	}
 
	// i < j implies arr[indices[i]] <= arr[indices[j]]
	sort(indices.begin(), indices.end(),
	     [&](const int i, const int j) { return arr[i] < arr[j]; });
 
	ll ans = 0;
	int edges_remaining = n - 1;
	// is_connected[i] == true if there is an edge between i and i+1
	vector<bool> is_connected(n, false);
	for (int i = 0; i < n; i++) {
		int j = indices[i];
		int val = arr[j];
		/*
		 * if the edge costs more than p, then connect the rest with edges of
		 * type 2 which cost p
		 */
		if (val >= p) { break; }
 
		// try to add an edge (j, indices[i]) to the left
		while (j > 0 && !is_connected[j - 1] && arr[j - 1] % val == 0) {
			edges_remaining--;
			ans += val;
			is_connected[j - 1] = true;
			j--;
		}
 
		// try to add an edge (indices[i], j) to the right
		j = indices[i];
		while (j < n - 1 && !is_connected[j] && arr[j + 1] % val == 0) {
			edges_remaining--;
			ans += val;
			is_connected[j] = true;
			j++;
		}
	}
 
	// the edges that still have to be added have the cost p
	ans += (ll)edges_remaining * p;
 
	cout << ans << endl;
}
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) { solve(); }
}


for _ in range(int(input())):
	N, P = map(int, input().split())
	weights = list(map(int, input().split()))
 
	# sort indices by weight
	order = sorted(list(range(N)), key=lambda x: weights[x])
	cost, edges_remaining = 0, N - 1
	is_connected = [False] * N
 
	for ind in order:
		# if the edge costs at least p, then connect
		# the rest with edges of type 2 which cost p
		if weights[ind] >= P:
			break
 
		# try to add an edge (j, ind) while expanding left
		j = ind
		while j > 0 and not is_connected[j - 1] and weights[j - 1] % weights[ind] == 0:
			cost += weights[ind]
			edges_remaining -= 1
			is_connected[j - 1] = True
			j -= 1
 
		# try to add an edge (ind, j) while expanding right
		j = ind
		while j < N - 1 and not is_connected[j] and weights[j + 1] % weights[ind] == 0:
			cost += weights[ind]
			edges_remaining -= 1
			is_connected[j] = True
			j += 1
 
	# the edges that still have to be added have the cost p
	cost += edges_remaining * P
 
	print(cost)