Friendly Spiders

Solución 1

Explicación

La primera observación que debemos hacer es que todas las arañas que comparten un factor común forman un grafo completo donde todos los pares de arañas de este grupo son amigas entre sí.

Así, podemos enumerar los factores primos de todas las arañas y llevar el registro, para cada factor, de las arañas que lo dividen, para guardar las aristas de forma eficiente. Dos arañas son amigas sii ambas están juntas en la lista de algún factor primo.

Sin embargo, hacer un BFS naive desde el nodo inicial tardará demasiado. Para optimizar esto, tenemos que hacer otra optimización: siempre es óptimo “usar” un primo a lo sumo una vez en nuestro camino.

Por ejemplo, tomemos el camino donde el número de patas es $15$ , $3$ y $9$ donde hemos usado el divisor común $3$ dos veces. Aquí, podemos recortar $3$ y pasar directamente de $15$ a $9$ .

Esto nos permite hacer un BFS optimizado desde la araña inicial manteniendo una lista global de factores primos visitados. Para cada araña, iteramos sobre sus factores primos y vemos cuáles no se han usado. Si un factor no se ha usado, entonces es un BFS estándar con backtracking.

Implementación

Complejidad temporal: $\mathcal{O}\left(n \left(\sqrt{A} + \log n\right)\right)$ , donde $A$ es el mayor número de patas entre las arañas.

C++Java


#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <vector>
 
using namespace std;
 
/** @return los factores primos de n */
set<int> primes(int n) {
	set<int> ret;
	while (n % 2 == 0) {
		n /= 2;
		ret.insert(2);
	}
 
	for (int i = 3; i * i <= n; i += 2) {
		while (n % i == 0) {
			n /= i;
			ret.insert(i);
		}
	}
 
	if (n > 2) { ret.insert(n); }
	return ret;
}
 
int main() {
	int spider_num;
	cin >> spider_num;
	map<int, vector<int>> trains;
	vector<set<int>> prime_factors(spider_num);
	for (int s = 0; s < spider_num; s++) {
		int spider;
		cin >> spider;
		prime_factors[s] = primes(spider);
		for (int f : prime_factors[s]) { trains[f].push_back(s); }
	}
 
	int start, end;
	cin >> start >> end;
	start--;
	end--;
 
	vector<int> frontier{start};
	set<int> taken;
	// Guarda el predecesor de cada araña para reconstruir el camino
	vector<int> come_from(spider_num, -1);
	come_from[start] = start;
	while (!frontier.empty()) {
		vector<int> next_up;
		for (int s : frontier) {
			for (int f : prime_factors[s]) {
				if (taken.count(f)) {
					// Ya usamos este factor antes, así que podemos saltarlo
					continue;
				}
				for (int ns : trains[f]) {
					if (come_from[ns] == -1) {
						come_from[ns] = s;
						next_up.push_back(ns);
					}
				}
				taken.insert(f);
			}
		}
		frontier = next_up;
	}
 
	if (come_from[end] == -1) {
		cout << -1 << endl;
		return 0;
	}
 
	// Reconstruir el camino haciendo backtracking desde el final hasta el inicio
	vector<int> path{end};
	while (path.back() != start) { path.push_back(come_from[path.back()]); }
	reverse(path.begin(), path.end());
 
	cout << path.size() << '\n';
	for (int i = 0; i < path.size(); i++) {
		cout << path[i] + 1 << " \n"[i == path.size() - 1];
	}
}


import java.io.*;
import java.util.*;
 
public class FriendlySpiders {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int spiderNum = Integer.parseInt(read.readLine());
 
		Map<Integer, List<Integer>> trains = new HashMap<>();
		Set<Integer>[] primeFactors = new HashSet[spiderNum];
		StringTokenizer spiderST = new StringTokenizer(read.readLine());
		for (int s = 0; s < spiderNum; s++) {
			int spider = Integer.parseInt(spiderST.nextToken());
			primeFactors[s] = primes(spider);
			for (int f : primeFactors[s]) {
				if (!trains.containsKey(f)) { trains.put(f, new ArrayList<>()); }
				trains.get(f).add(s);
			}
		}
 
		StringTokenizer query = new StringTokenizer(read.readLine());
		int start = Integer.parseInt(query.nextToken()) - 1;
		int end = Integer.parseInt(query.nextToken()) - 1;
 
		List<Integer> frontier = new ArrayList<>(Arrays.asList(start));
		Set<Integer> taken = new HashSet<>();
		// Guarda el predecesor de cada araña para reconstruir el camino
		int[] comeFrom = new int[spiderNum];
		Arrays.fill(comeFrom, -1);
		comeFrom[start] = start;
		while (!frontier.isEmpty()) {
			List<Integer> next_up = new ArrayList<>();
			for (int s : frontier) {
				for (int f : primeFactors[s]) {
					if (taken.contains(f)) {
						// Ya usamos este factor antes, así que podemos saltarlo
						continue;
					}
					for (int ns : trains.get(f)) {
						if (comeFrom[ns] == -1) {
							comeFrom[ns] = s;
							next_up.add(ns);
						}
					}
					taken.add(f);
				}
			}
			frontier = next_up;
		}
 
		if (comeFrom[end] == -1) {
			System.out.println(-1);
			return;
		}
 
		List<Integer> path = new ArrayList<>(Arrays.asList(end));
		while (path.get(path.size() - 1) != start) {
			path.add(comeFrom[path.get(path.size() - 1)]);
		}
		Collections.reverse(path);
 
		System.out.println(path.size());
		for (int i = 0; i < path.size(); i++) {
			System.out.print(path.get(i) + 1 + (i == path.size() - 1 ? "\n" : " "));
		}
	}
 
	private static Set<Integer> primes(int n) {
		Set<Integer> ret = new HashSet<>();
		while (n % 2 == 0) {
			n /= 2;
			ret.add(2);
		}
 
		for (int i = 3; i * i <= n; i += 2) {
			while (n % i == 0) {
				n /= i;
				ret.add(i);
			}
		}
 
		if (n > 2) { ret.add(n); }
		return ret;
	}
}

Solución 2

Explicación

Mantener todas las aristas posibles entre cualesquiera dos arañas es demasiado ineficiente.

Como los grafos completos de las arañas se agrupan por factores primos, construimos un grafo que agrupa arañas por factores primos. Hacemos esto creando nodos que representan factores primos, y conectándolos con las arañas divisibles por ese factor primo.

Ahora podemos observar que la longitud del camino en el problema original es la longitud del camino más corto sobre nuestro grafo reformulado, dividida por 2 más 1, contabilizando el nodo inicial.

El número de vértices es la cantidad de factores primos más la cantidad de nodos, que es a lo sumo el doble de $N$ . En cuanto al número de aristas, consideremos que cualquier entero $n$ tiene a lo sumo $\log{n}$ factores primos, ya que factorizar cada factor primo al menos divide $n$ a la mitad. Así, el número de aristas está acotado por $\mathcal{O}(N \log{N})$ .

Con estos parámetros para nuestro grafo alterado, el BFS ahora es factible.

Implementación

Complejidad temporal: $\mathcal O\left(N\frac{\log N}{\log\log N}+\frac A{\log A}+N\log\log A\right)$ donde $A=\max(a_i)$ . Para fines prácticos, esto está acotado por $\mathcal O(N\log N+A\log A)$ .

C++


#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
 
using namespace std;
 
constexpr int MAX_N = 300000;
constexpr int MAX_LEGS = 300000;
// Hay menos de 1e5 primos menores que 3e5
constexpr int MAX_PRIMES = 100000;
constexpr int MAX_NODES = MAX_N + MAX_PRIMES;
vector<int> adj[MAX_NODES + 1];
bool visited[MAX_NODES + 1];
int primes[MAX_LEGS + 1];          // primes[p] = nodo del grafo asociado al primo p
int smallest_prime[MAX_LEGS + 1];  // smallest_prime[i] = menor factor primo de i
int parent[MAX_NODES + 1];
 
int node_at;  // Mayor nodo agregado hasta ahora
 
/** Calcula el menor primo de cada número. */
void sieve() {
	for (int i = 2; i <= MAX_LEGS; i++) { smallest_prime[i] = i; }
	for (int i = 2; i * i <= MAX_LEGS; i++) {
		if (smallest_prime[i] == i) {
			for (int j = i * i; j <= MAX_LEGS; j += i) {
				if (smallest_prime[j] == j) smallest_prime[j] = i;
			}
		}
	}
}
 
/**
 * Factorizar un número y agregar las aristas relevantes al grafo
 * @param a El valor del nodo
 * @param i El id del nodo en el grafo
 */
void factorize(int a, int i) {
	while (a > 1) {
		int p = smallest_prime[a];
		if (a > 1 && a % p == 0) {
			// Nuevo factor primo encontrado: lo agregamos al grafo
			if (!primes[p]) { primes[p] = ++node_at; }
			adj[primes[p]].push_back(i);
			adj[i].push_back(primes[p]);
		}
		while (a > 1 && a % p == 0) { a /= p; }
	}
}
 
int main() {
	sieve();
	int n;
	cin >> n;
	node_at = n;
 
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		factorize(a, i);
	}
	int start, end;
	cin >> start >> end;
 
	// Hallar el camino usando BFS
	queue<pair<int, int>> q;
	visited[start] = true;
	q.push({start, 0});
	while (!q.empty()) {
		auto front = q.front();
		q.pop();
		int loc = front.first;
		int len = front.second;
 
		if (loc == end) {
			cout << len / 2 + 1 << endl;
			vector<int> points(1, loc);
 
			// Hacer backtracking para hallar el camino original
			int current = loc;
			while (current != start) {
				current = parent[current];
				points.push_back(current);
			}
			reverse(points.begin(), points.end());
 
			for (int i = 0; i < points.size(); i++) {
				if (i % 2 == 0) { cout << points[i] << ' '; }
			}
			cout << endl;
			return 0;
		}
 
		for (int next : adj[loc]) {
			if (!visited[next]) {
				visited[next] = true;
				parent[next] = loc;
				q.push(make_pair(next, len + 1));
			}
		}
	}
 
	// Si no se encuentra un camino, imprimir -1.
	cout << -1 << endl;
}