I Would Walk 500 Miles

Solución 1: algoritmo de Prim

Para este problema, queremos maximizar el mínimo del número de millas que dos vacas están dispuestas a caminar, de ahora en adelante referido como $M$ . Consideremos un árbol de expansión mínima (MST) de las $N$ vacas. Al agregar la $i$ -ésima arista al MST, implica que todas las aristas entre las $N - i$ componentes restantes tienen pesos mayores o iguales que esta arista agregada, o, en otras palabras, $M$ es igual al peso de esta arista agregada.

En el caso de partir las vacas en $K$ grupos, quitamos las $K - 1$ aristas del MST que tienen el peso máximo. $M$ es entonces igual al peso del mínimo de esas aristas quitadas. Si las aristas del MST están ordenadas en orden ascendente, $M$ sería el peso de la $(N - K + 1)$ -ésima arista del MST.

Como la implementación típica del algoritmo de Kruskal requiere tiempo $\mathcal{O}(N^2 \log N)$ para un grafo denso como en nuestro caso, usamos en cambio el algoritmo de Prim con búsqueda lineal del vértice más cercano. Cada barrido solo toma tiempo $\mathcal{O}(N)$ , y solo tenemos que hacer $N$ barridos.

Implementación

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

C++Java


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll MOD = 2019201997LL;
const ll FACTOR1 = 2019201913LL;
const ll FACTOR2 = 2019201949LL;
 
/**
 * @return the number of miles cow a + 1 and b + 1 are willing to walk to see
 * each other
 */
ll calc_length(ll a, ll b) {
	a++, b++;
	return (a * FACTOR1 + b * FACTOR2) % MOD;
}
 
/**
 * Prim's Algorithm for dense graph to build the MST by scanning
 * @return the edge lengths in the MST
 */
vector<ll> prim(int N) {
	vector<ll> dist(N, MOD);
	vector<bool> visited(N, false);
 
	for (int i = 0; i < N; i++) {
		// find the nearest node to the current MST
		int min_dist_node = -1;
		for (int j = 0; j < N; j++) {
			if (!visited[j] && (min_dist_node < 0 || dist[j] < dist[min_dist_node])) {
				min_dist_node = j;
			}
		}
 
		// add this node to the MST
		visited[min_dist_node] = true;
 
		// update the distances between the MST and other unconnected nodes
		for (int j = 0; j < N; j++) {
			if (!visited[j]) {
				dist[j] = min(
				    dist[j], calc_length(min(min_dist_node, j), max(min_dist_node, j)));
			}
		}
	}
	return dist;
}
 
int main() {
	freopen("walk.in", "r", stdin);
	freopen("walk.out", "w", stdout);
 
	int N, K;
	cin >> N >> K;
 
	vector<ll> mst = prim(N);
	sort(mst.begin(), mst.end());
	cout << mst[N - K] << endl;
}


import java.io.*;
import java.util.*;
 
public class Walk {
	static final long MOD = 2019201997L;
	static final long FACTOR1 = 2019201913L;
	static final long FACTOR2 = 2019201949L;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("walk.in"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		br.close();
 
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
 
		long[] mst = prim(N);
		Arrays.sort(mst);
 
		PrintWriter pr = new PrintWriter("walk.out");
		pr.println(mst[N - K]);
		pr.close();
	}
 
	/**
	 * @return the number of miles cow a + 1 and b + 1 are willing to walk to
	 *     see
	 * each other
	 */
	public static long calcLength(long a, long b) {
		a++;
		b++;
		return (a * FACTOR1 + b * FACTOR2) % MOD;
	}
 
	/**
	 * Prim's Algorithm for dense graph to build the MST by scanning
	 * @return the edge lengths in the MST
	 */
	public static long[] prim(int N) {
		long[] dist = new long[N];
		boolean[] visited = new boolean[N];
		for (int i = 0; i < N; i++) { dist[i] = MOD; }
 
		for (int i = 0; i < N; i++) {
			// find the nearest node to the current MST
			int minDistNode = -1;
			for (int j = 0; j < N; j++) {
				if (!visited[j] && (minDistNode < 0 || dist[j] < dist[minDistNode])) {
					minDistNode = j;
				}
			}
 
			// add this node to the MST
			visited[minDistNode] = true;
 
			// update the distances between the MST and other unconnected nodes
			for (int j = 0; j < N; j++) {
				if (!visited[j]) {
					dist[j] = Math.min(dist[j], calcLength(Math.min(minDistNode, j),
					                                       Math.max(minDistNode, j)));
				}
			}
		}
		return dist;
	}
}

Solución 2: algoritmo de Kruskal y radix sort en dos pasadas

Como alternativa, también podemos usar el algoritmo de Kruskal para construir nuestro MST. Nótese que solo el paso de ordenar todas las aristas toma demasiado tiempo. Si logramos ordenar todas las aristas en tiempo lineal, también podríamos resolverlo con el algoritmo de Kruskal.

Para ordenar estas aristas, podemos aplicar un radix sort en dos pasadas. En particular, primero usamos ordenamiento por conteo para ordenar los primeros 16 bits ( $[0, 2^{16})$ ) de los pesos. Luego, en la segunda iteración, ordenamos los 16 bits restantes ( $[2^{16}, 2^{32})$ ). Después del proceso de ordenamiento, aplicamos el algoritmo de Kruskal sin modificar sobre las aristas y $M$ es igual al peso de la $(N - K + 1)$ -ésima arista más larga del MST.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
 
// BeginCodeSnip{DSU}
struct DSU {
	int size;
	vector<int> dsu;
	DSU(int s) : size(s), dsu(s, -1) {}
	int find(int x) {
		if (dsu[x] < 0) return x;
		return dsu[x] = find(dsu[x]);
	}
	bool unite(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return false;
		if (dsu[a] > dsu[b]) swap(a, b);
		dsu[a] += dsu[b];
		dsu[b] = a;
		return true;
	}
};
// EndCodeSnip
 
const ll MOD = 2019201997LL;
const ll FACTOR1 = 2019201913LL;
const ll FACTOR2 = 2019201949LL;
 
/** @return the number of miles cow a and b are willing to walk to see each
 * other */
ll calc_length(ll a, ll b) { return (a * FACTOR1 + b * FACTOR2) % MOD; }
 
/**
 * Performs a two-pass radix sort on all the edges in the complete graph between
 * all cows
 * @return a in ascending order sorted list of all edges
 */
vector<pair<int, int>> calc_sorted_edges(int N) {
	const int MAX_COMP = 1 << 16;
	vector<int> count(MAX_COMP, 0);
	int edges_count = N * (N - 1) / 2;
	vector<pair<int, int>> pass_1(edges_count);
	vector<pair<int, int>> pass_2(edges_count);
 
	// first pass of the radix sort on [0, 1 << 16)
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			count[calc_length(i, j) & (MAX_COMP - 1)]++;
		}
	}
	for (int i = 1; i < MAX_COMP; i++) { count[i] += count[i - 1]; }
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			pass_1[--count[calc_length(i, j) & (MAX_COMP - 1)]] = {i, j};
		}
	}
 
	// second pass of the radix sort on [1 << 16, 1 << 32)
	count.assign(1 << 16, 0);
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) { count[calc_length(i, j) >> 16]++; }
	}
	for (int i = 1; i < MAX_COMP; i++) { count[i] += count[i - 1]; }
	for (int i = edges_count - 1; i >= 0; i--) {
		auto &[a, b] = pass_1[i];
		pass_2[--count[calc_length(a, b) >> 16]] = pass_1[i];
	}
 
	return pass_2;
}
 
int main() {
	freopen("walk.in", "r", stdin);
	freopen("walk.out", "w", stdout);
 
	int N, K;
	cin >> N >> K;
 
	vector<pair<int, int>> edges = calc_sorted_edges(N);
	// length of edges of the MST
	vector<ll> edge_lens;
	// Kruskal's Algorithm to construct the MST
	DSU dsu(N + 1);
	for (int i = 0; i < N * (N - 1) / 2; i++) {
		auto &[a, b] = edges[i];
		if (dsu.unite(a, b)) { edge_lens.push_back(calc_length(a, b)); }
	}
 
	cout << edge_lens[N - K] << endl;
}

Solución 3: matemáticas

Como este problema tiene sus raíces en optimizar una expresión de peso dada, estamos motivados a usar matemáticas.

Primero, podemos usar aritmética modular para hallar una expresión directa del residuo modular. El objetivo es hallar una expresión del residuo modular que involucre solo operaciones básicas que podremos optimizar con técnicas matemáticas. Usando propiedades de la aritmética modular (números negativos en aritmética modular), consideramos la expresión $\pmod{2019201997}$ para reducir los números:

2019201913x+2019201949y \equiv - 84 x - 48 y \pmod {2019201997}

Como $x,y$ están acotados por $N \leq 7500,$ esta expresión siempre dará un valor negativo cuyo valor absoluto no supera el módulo $2019201997.$ Así, podemos hallar fácilmente una expresión del residuo modular a partir de aquí si simplemente desplazamos hacia arriba por el módulo $2019201997$ una vez:

(2019201913x+2019201949y) \mod 2019201997 = 2019201997 - 84 x - 48 y.

Ahora, resta optimizar esta expresión. Formalmente, debemos hallar una $K$ -partición de las vacas tal que

\min\limits_{x,y \, \text{in different groups}} (2019201997 - 84 x - 48 y)

se maximice.

Ahora, analicemos el comportamiento de la función: para $x,y$ grandes, la expresión se vuelve pequeña, y para $x,y$ pequeños, la expresión se vuelve grande.

Pero recordando la condición de que $x,y$ deben estar en grupos distintos para contribuir a la respuesta, esto significa que $x,y$ grandes deberían estar juntos en el mismo grupo (para evitar de forma voraz que la expresión se vuelva pequeña) y $x,y$ pequeños deberían estar en grupos distintos (para hacer de forma voraz que la expresión sea grande). Esto lleva a la siguiente estrategia voraz:

Hacer un grupo con todas las vacas más grandes que quepan y $k-1$ grupos con todas las vacas más pequeñas. Por supuesto, las $k-1$ vacas más pequeñas son simplemente $1 \dots k-1,$ así que esto significa que las otras $n-(k-1)$ vacas estarán en el grupo grande.

Ahora que hemos identificado el agrupamiento óptimo, podemos hallar la respuesta volviendo a la pregunta: queremos minimizar la expresión. Para minimizar la expresión, deberíamos elegir de forma voraz las vacas más grandes que están en grupos distintos (ya que $x,y$ grandes hacen la expresión más pequeña). Claramente, esto significa que deberíamos tomar la vaca $n,$ la vaca más grande del grupo de vacas grandes, y $k-1,$ la vaca más grande que no está en el grupo de vacas grandes.

Recordemos que el enunciado del problema requiere $x < y,$ así que tenemos $x = k - 1, y = n.$ Nuestra respuesta es tan fácil como sustituir estos valores en la expresión del residuo modular $2019201997 - 84 x - 48 y:$

2019201997 - 84 (k-1) - 48 n

En retrospectiva, esta solución es equivalente a ejecutar el algoritmo de MST de Kruskal a mano cuando analizamos la expresión del peso de las aristas y usamos lógica voraz para crear el agrupamiento óptimo. (Así que las soluciones anteriores hallarán exactamente el mismo agrupamiento.)

Implementación

Complejidad temporal: $\mathcal{O}(1)$

Implementación de Senpat:

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("walk.in", "r", stdin);
	freopen("walk.out", "w", stdout);
	int N, K;
	cin >> N >> K;
	long long answer = 2019201997LL - 48LL * N - 84LL * (K - 1LL);
	cout << answer << endl;
}


import java.io.*;
import java.util.*;
 
public class Walk {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("walk.in"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		br.close();
 
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		long answer = 2019201997L - 48L * N - 84L * (K - 1L);
 
		PrintWriter pr = new PrintWriter("walk.out");
		pr.println(answer);
		pr.close();
	}
}