Candy Machine

Análisis oficial (C++) 

Explicación

Observación

Podemos pensar en las ranuras de salida como posiciones en la recta numérica. Consideremos un vagón que empieza a moverse en el tiempo $0$. Entonces, ese vagón puede atrapar un caramelo $c_i$ $(s_i, t_i)$ si su posición en el tiempo $0$ está dentro del rango $[s_i - t_i, s_i + t_i]$. Definamos este rango como el rango de posiciones aceptables del vagón para $c_i$ en el tiempo $0$. Con cada segundo que pasa, este rango se reduce en $1$ unidad a la izquierda y a la derecha de $s_i$. En general, el rango de posiciones aceptables del vagón para $c_i$ en el tiempo $t$ (donde $t \leq t_i$) es:

En el tiempo $t_i$ este rango se ha reducido a un solo punto, $s_i$.

Un vagón puede atrapar un caramelo $c_j$ $(s_j, t_j)$ antes que $c_i$, si el rango de posiciones aceptables del vagón para $i$ en el tiempo $t_j$ incluye $s_j$ (ya que el vagón estará en $s_j$ para atrapar $j$). Sin embargo, en el tiempo $t_j$ el rango de posiciones aceptables del vagón de $c_i$ se habrá reducido a

Pero $s_j$ necesita estar dentro de este rango, por lo tanto:

Esto es equivalente a decir que el rango de posiciones aceptables del vagón de $c_j$ está totalmente contenido dentro del rango de $c_i$.

Por lo tanto, hemos concluido que dos caramelos pueden ser atrapados por el mismo vagón si (y solo si) sus rangos de posiciones aceptables del vagón están anidados.

Hallar el mínimo número de vagones

Podemos pensar en cada caramelo como su rango de posiciones aceptables del vagón en el tiempo 0 $[s - t, s + t]$ (notamos que cada caramelo corresponde a un rango único y viceversa). Podemos concluir que un vagón puede atrapar una secuencia de caramelos $c_1, c_2, ..., c_k$, si forman una secuencia de rangos anidados. Se sigue que el mínimo número de vagones necesarios es la secuencia más larga de rangos no anidados.

Dos rangos $[l_1, r_1]$, $[l_2, r_2]$ que no están anidados cumplen: $$l_1 < l_2 \implies r_1 < r_2$$.

Si ordenamos los caramelos por el extremo izquierdo de sus rangos de modo que

entonces una secuencia de rangos no anidados correspondería a una secuencia creciente de extremos derechos. Por lo tanto, el mínimo número de vagones requeridos correspondería a la longitud de la secuencia creciente más larga de extremos derechos.

Asignar los caramelos a los vagones

Siguiendo el algoritmo de búsqueda binaria descrito en el módulo de LIS, podemos asignar los caramelos con la misma longitud de LIS al mismo vagón. Los rangos que tienen la misma longitud de LIS no pueden estar anidados. Si lo estuvieran, podríamos usar el rango interior para aumentar la LIS del exterior en 1.

Implementación

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

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> pi;
 
int main() {
	int n;
	cin >> n;
	vector<pi> candies(n);
	for (int i = 0; i < n; i++) {
		int s, t;
		cin >> s >> t;
		candies[i] = make_pair(s - t, s + t);
	}
 
	/*
	 * Ordenamos los segmentos por extremo izquierdo
	 * NOTA: Es importante ordenar segmentos con el mismo punto izquierdo por
	 * punto derecho decreciente para que cuenten como anidados
	 */
	sort(candies.begin(), candies.end(), [](const pi &a, const pi &b) -> bool {
		return (a.first == b.first ? a.second > b.second : a.first < b.first);
	});
 
	vector<int> lis(n + 1, INT_MAX);
	lis[0] = 0;
	vector<vector<pi>> candies_caught(n + 1);
	for (int i = 0; i < n; i++) {
		int r_point = candies[i].second;
 
		int l = 0;  // Condición: lis[l] < r_point
		int r = n;  // Condición: lis[r] >= r_point
		while (r > l + 1) {
			int mid = (l + r) / 2;
			if (lis[mid] < r_point) {
				l = mid;
			} else {
				r = mid;
			}
		}
		lis[l + 1] = r_point;
		// Los caramelos con la misma longitud de LIS pueden ser atrapados por el mismo vagón
		candies_caught[l + 1].push_back(candies[i]);
	}
 
	int ans = 0;
	while (ans < n && lis[ans + 1] != INT_MAX) { ans++; }
 
	cout << ans << "\n";
	for (int len = 1; len <= ans; len++) {
		for (pi c : candies_caught[len]) {
			int s = (long long)(c.first + c.second) / 2;
			int t = (long long)(c.second - c.first) / 2;
 
			cout << s << " " << t << " " << len << "\n";
		}
	}
}