2015 - Circus

Explicación

Por conveniencia, asumimos que la posición $m$ tiene una cuerda. Además, podemos ordenar la lista de ubicaciones de cuerdas y reetiquetarlas de esa forma. Esto no afecta el problema, pero facilita pensarlo.

Según las condiciones del problema, cada salto consecutivo entre cuerdas no puede exceder la distancia del salto anterior. Si planteamos el problema como recorrer hacia afuera desde la cuerda en $m$, esta condición se invierte. Para ir de la cuerda en $m$ a otra cuerda, los saltos que damos deben tener longitudes no decrecientes.

Dada la condición de un camino válido, no hay caso en el que queramos llegar a la posición $m$ con más cuerda inicial de la requerida. Así, podemos modelar este problema como un problema de caminos más cortos desde una sola fuente, expandiendo hacia afuera desde la cuerda en $m$ para calcular las longitudes de cuerda requeridas. Calcular las distancias de forma naive toma tiempo $\mathcal{O}(N^2 \log{N})$.

Optimizar el cálculo de distancias

Sea $s[i]$ la longitud inicial de cuerda necesaria para llegar a $m$ desde la cuerda $i$. Si estamos en algún nodo $i$ y queremos actualizar nuestras distancias, nuestro código de Dijkstra para empujar a nodos nuevos podría verse algo así:

// i = el nodo actual
// s[i] = la longitud de cuerda para ir de i a m
for (int j = 0; j < n; j++) {
	if (abs(p[j] - p[i]) >= s[i]) { pq.push({abs(p[j] - p[i]), j}); }
}

Notamos que si ordenamos la lista de posiciones $p$, un prefijo y un sufijo de posiciones permitirán transiciones. Para usar esta propiedad, partimos nuestros cálculos de distancia en dos partes:

• $\text{dist}_l[i]$ es la longitud de cuerda necesaria para llegar a $m$, si el último salto vino de la izquierda.
• $\text{dist}_r[i]$ es la longitud de cuerda necesaria para llegar a $m$, si el último salto vino de la derecha.

Las direcciones de ambas definiciones de distancia son de alejarse de una cuerda anterior. Por ejemplo, si nos movemos de una cuerda en la posición $5$ a la posición $3$ en nuestro código de Dijkstra, actualizaríamos $\text{dist}_l$ para la cuerda en $3$.

Consideremos calcular $\text{dist}_l[i]$, siendo similar la lógica para calcular $\text{dist}_r[i]$. Observamos que:

• Si $i$ tiene un vecino a la izquierda, podemos potencialmente actualizar $\text{dist}_l[i-1]$ simplemente extendiendo el salto usado para obtener $\text{dist}_l[i]$.
• A partir del pseudocódigo de arriba, este tipo de transición es esencialmente lo mismo que manejar el prefijo de transiciones posibles de Dijkstra.

Con estas observaciones, podemos reducir la cantidad de aristas posibles de $\mathcal{O}(N^2)$ a $\mathcal{O}(N)$. El pseudocódigo de las transiciones es el siguiente:

// i = el nodo actual
// dist_l[i] = distancia si el salto anterior vino de la izquierda
// dist_r[i] = distancia si el salto anterior vino de la derecha
// asumimos que estamos procesando dist_l[i]
if (i > 0) { pq.push({dist_l[i] + (p[i] - p[i - 1])}); }
 
int next_left;  // siguiente nodo a la izquierda con dist. de salto >= dist_l[i]
pq.push({p[i] - p[next_left], next_left});
 
int next_right;  // siguiente nodo a la derecha con dist. de salto >= dist_l[i]
pq.push({p[next_right] - p[i], next_right});

Esto nos permite calcular la longitud mínima de cuerda para llegar a $m$ en tiempo $\mathcal{O}(N \log N)$.

Calcular minLength(d)

Partiendo de la cuerda temporal, terminamos saltando a alguna otra cuerda para llegar eventualmente a $m$. $\text{dist}[i]$ guarda la longitud mínima de cuerda para llegar a $m$ desde cualquier otra cuerda, así que podemos reutilizarla al calcular minLength.

Una forma naive de calcular nuestra respuesta se vería algo así:

int best = INF;
for (int i = 0; i < n; i++) {
	if (abs(p[i] - d) >= dist[i]) { best = min(best, p[i] - d); }
}

Sin pérdida de generalidad, asumimos que $p[i] \leq d$. Entonces, podemos reescribir la condición para actualizar nuestra mejor respuesta:

Como la distancia del salto es $d - p[i]$, buscamos el máximo $p[i]$ entre todos los $i$ que cumplen la condición de arriba. Para ello, podemos ordenar todas las cuerdas por $\text{dist}[i] + p[i]$ y calcular el valor máximo de prefijo de $p[i]$ para cada cuerda. Luego, para consultar el mejor valor, usamos búsqueda binaria para hallar el último $i$ que cumple la condición.

Usando una lógica similar para el caso en que $p[i] \geq d$, podemos responder cada consulta en tiempo $\mathcal{O}(\log N)$.

Implementación

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

#include <bits/stdc++.h>
using ll = long long;
 
constexpr int INF = 1e9;
 
std::map<int, int> best_f, best_r;
 
void init(int n, int m, int p[]) {
	// ordenamos puntos para lower bound y aristas fantasma
	std::sort(p, p + n);
 
	// dist[i] = {dist desde la izquierda, dist desde la derecha}
	std::vector<std::array<int, 2>> dist(n, {INF, INF});
	std::priority_queue<std::array<int, 3>> pq;
	for (int i = 0; i < n; i++) {
		// inicializamos dist izquierda con salto desde m
		pq.push({-(m - p[i]), i, 0});
	}
 
	while (!pq.empty()) {
		auto [t, u, f] = pq.top();
		pq.pop();
		t *= -1;
		if (dist[u][f] <= t) continue;
		dist[u][f] = t;
 
		// usamos la arista 'falsa'
		if (f == 0 && u > 0) {
			pq.push({-(t + p[u] - p[u - 1]), u - 1, 0});
		} else if (f == 1 && u + 1 < n) {
			pq.push({-(t + p[u + 1] - p[u]), u + 1, 1});
		}
 
		// saltamos hacia adelante al menos t
		int nxt = std::lower_bound(p, p + n, p[u] + t) - p;
		if (nxt < n) { pq.push({-(p[nxt] - p[u]), nxt, 1}); }
 
		// saltamos hacia atrás al menos t
		nxt = std::upper_bound(p, p + n, p[u] - t) - p - 1;
		if (nxt >= 0) { pq.push({-(p[u] - p[nxt]), nxt, 0}); }
	}
 
	for (int i = 0; i < n; i++) {
		// dist[i][0] = longitud mínima de cuerda para llegar al destino desde la cuerda i
		dist[i][0] = std::min(dist[i][0], dist[i][1]);
	}
 
	std::vector<int> ord(n);
	std::iota(ord.begin(), ord.end(), 0);
 
	// ordenamos puntos por ubicación de entrada decreciente para primeros saltos hacia adelante
	std::sort(ord.begin(), ord.end(), [&](int x, int y) -> bool {
		return p[x] - dist[x][0] > p[y] - dist[y][0];
	});
 
	int best = INF;
	for (int i : ord) {
		// hallamos el mínimo p[i] para el salto más corto
		best = std::min(best, p[i]);
		best_f[p[i] - dist[i][0]] = best;
	}
 
	// ordenamos puntos por ubicación de entrada creciente para primeros saltos inversos
	std::sort(ord.begin(), ord.end(), [&](int x, int y) -> bool {
		return p[x] + dist[x][0] < p[y] + dist[y][0];
	});
 
	best = -INF;
	for (int i : ord) {
		// hallamos el máximo p[i] para el salto más corto
		best = std::max(best, p[i]);
		best_r[p[i] + dist[i][0]] = best;
	}
 
	// permitimos salto directo a m
	best_f[m] = m;
}
 
int minLength(int d) {
	int best = INF;
 
	// hallamos el salto mínimo hacia adelante
	auto it = best_f.lower_bound(d);
	if (it != best_f.end()) { best = std::min(best, (it->second) - d); }
 
	// hallamos el salto mínimo inverso
	it = best_r.upper_bound(d);
	if (it != best_r.begin()) {
		--it;
		best = std::min(best, d - (it->second));
	}
 
	return best;
}