Remainder Game

Análisis oficial (C++) 

Explicación

Aplicar cualquier módulo dos veces es idéntico a aplicarlo una sola vez, incluso cuando se usan otros módulos, así que debemos comprar cada módulo a lo sumo una vez. Observamos que un módulo grande siempre cuesta más que cualquier combinación de módulos más pequeños, ya que el peor caso es comprar cada módulo más pequeño una vez:

Esto significa que debemos priorizar optimizar el módulo más grande usado a lo largo de todas las transformaciones $a_i \to b_i$, lo que motiva nuestra idea voraz: hallar el módulo más grande que debemos comprar, comprarlo exactamente una vez y repetir.

Para ello, construimos un grafo dirigido sobre los vértices $0, \ldots, 50$. Para cada valor $x$ y módulo $k$, construimos una arista $x \to x \bmod k$ con peso $k$. Un camino de $a_i$ a $b_i$ representa una secuencia de operaciones para convertir $a_i$ en $b_i$, y los módulos necesarios son los pesos de las aristas a lo largo del camino.

Definimos el peso de un camino de $u$ a $v$, $f(u, v)$, como el valor mínimo posible del peso máximo de arista en dicho camino. Así, al procesar una transformación $a_i \to b_i$, $f(a_i, b_i)$ es el umbral mínimo tal que el camino es factible usando solo operaciones $\leq f(a_i,b_i)$, de modo que $K = \max_i f(a_i, b_i)$ debe comprarse en la construcción voraz. Notamos que $f(u, v) = 0$ cuando $a_i$ puede alcanzar $b_i$ en el grafo.

Calculamos estas distancias con una variante de Floyd-Warshall, reemplazando la relajación estándar por:

Como se describió antes, es óptimo comprar el módulo necesario más grande. Para ello, calculamos $K = \max_i f(a_i, b_i)$. Si es imposible transformar algún par de $a_i$ y $b_i$, imprimimos -1. En caso contrario, compramos $K$ y ponemos a $0$ toda arista con peso $K$. Notamos que esto exige recalcular $f(a_i, b_i)$ más adelante.

Cada iteración compra de forma permanente un módulo, así que hay a lo sumo $50$ iteraciones.

Implementación

Complejidad temporal: $\mathcal{O}(M^4)$, donde $M=\max_i(a_i)$.

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_VAL = 50;
const int NUM_NODES = MAX_VAL + 1;
const int INF = 1e9;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n;
	cin >> n;
 
	vector<int> a(n), b(n);
	for (int &x : a) cin >> x;
	for (int &x : b) cin >> x;
 
	vector<vector<int>> dist(NUM_NODES, vector<int>(NUM_NODES, INF));
	for (int i = 0; i <= MAX_VAL; i++) {
		for (int j = 0; j <= MAX_VAL; j++) { dist[i][j] = INF; }
		dist[i][i] = 0;
	}
 
	// Agregamos una arista x -> x % k con peso k; la guardamos para búsqueda rápida después
	vector<vector<pair<int, int>>> edges_by_modulus(NUM_NODES);
	for (int x = 0; x <= MAX_VAL; x++) {
		for (int k = 1; k <= MAX_VAL; k++) {
			int y = x % k;
			dist[x][y] = min(dist[x][y], k);
			edges_by_modulus[k].push_back({x, y});
		}
	}
 
	long long ans = 0;
 
	while (true) {
		auto temp_dist = dist;
 
		// Floyd-Warshall de mínimo-del-máximo bajo los pesos actuales (parcialmente comprados)
		for (int mid = 0; mid <= MAX_VAL; mid++) {
			for (int i = 0; i <= MAX_VAL; i++) {
				for (int j = 0; j <= MAX_VAL; j++) {
					temp_dist[i][j] =
					    min(temp_dist[i][j], max(temp_dist[i][mid], temp_dist[mid][j]));
				}
			}
		}
 
		int largest_required = 0;
		for (int i = 0; i < n; i++) {
			if (temp_dist[a[i]][b[i]] == INF) {
				cout << -1 << "\n";
				return 0;
			}
 
			largest_required = max(largest_required, temp_dist[a[i]][b[i]]);
		}
 
		if (largest_required == 0) break;
 
		ans += (1LL << largest_required);
 
		// Marcamos toda arista que usa este módulo como gratuita para iteraciones futuras
		for (auto [from, to] : edges_by_modulus[largest_required]) {
			dist[from][to] = 0;
		}
	}
 
	cout << ans << '\n';
}