Cellular Network

Solución 1 - Búsqueda binaria

Explicación

Para cada ciudad, hallamos la torre más cercana a su izquierda y a su derecha con búsqueda binaria. Luego calculamos la distancia a ambas torres y nos quedamos con la menor para obtener el radio mínimo de la ciudad. El mayor de esos valores es nuestra respuesta.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n, m;
	cin >> n >> m;
	vector<int> cities, towers;
 
	for (int i = 0; i < n; i++) {
		int city;
		cin >> city;
		cities.push_back(city);
	}
 
	for (int i = 0; i < m; i++) {
		int tower;
		cin >> tower;
		towers.push_back(tower);
	}
 
	int min_r = 0;
	for (int i = 0; i < n; i++) {
		int tower_right =
		    lower_bound(begin(towers), end(towers), cities[i]) - begin(towers);
		int tower_left = tower_right - 1;
 
		int min_r_for_this_city = INT_MAX;
		if (tower_right < m) {
			assert(towers[tower_right] >= cities[i]);
			min_r_for_this_city =
			    min(min_r_for_this_city, towers[tower_right] - cities[i]);
		}
		if (tower_left >= 0) {
			assert(towers[tower_left] <= cities[i]);
			min_r_for_this_city =
			    min(min_r_for_this_city, cities[i] - towers[tower_left]);
		}
 
		min_r = max(min_r, min_r_for_this_city);
	}
 
	cout << min_r << endl;
}


import java.io.*;
import java.util.*;
 
public class CellularNetwork {
	static final int TWO_BILLION = 2000000000;
 
	// devuelve el primer índice del arreglo que es >= value,
	// o towers.length si no existe tal índice
	static int firstAtLeast(int[] towers, int value) {
		int low = 0, high = towers.length;
		while (low < high) {
			int mid = (low + high) / 2;
			if (towers[mid] >= value) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}
		return low;
	}
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();
 
		int[] cities = new int[n];
		int[] towers = new int[m];
 
		for (int i = 0; i < n; i++) { cities[i] = io.nextInt(); }
 
		for (int i = 0; i < m; i++) { towers[i] = io.nextInt(); }
 
		int minR = 0;
		for (int i = 0; i < n; i++) {
			int towerRight = firstAtLeast(towers, cities[i]);
			int towerLeft = towerRight - 1;
 
			int minRForThisCity = TWO_BILLION;
			// nos aseguramos de que el índice exista realmente;
			// si no, devolverá la longitud del
			// arreglo, que es igual a m
			if (towerRight < m) {
				minRForThisCity =
				    Math.min(minRForThisCity, towers[towerRight] - cities[i]);
			}
			if (towerLeft >= 0) {
				minRForThisCity =
				    Math.min(minRForThisCity, cities[i] - towers[towerLeft]);
			}
 
			minR = Math.max(minR, minRForThisCity);
		}
 
		io.println(minR);
		io.close();
	}
	// CodeSnip{Kattio}
}


def first_at_least(value: int) -> int:
	"""
	:return el primer índice del arreglo que es >= value, o len(arr)
	si no existe tal índice
	"""
	lo = 0
	hi = len(towers)
	while lo < hi:
		mid = (lo + hi) // 2
		if towers[mid] > value:
			hi = mid
		else:
			lo = mid + 1
 
	return lo
 
 
n, m = map(int, input().split())
cities = list(map(int, input().split()))
towers = list(map(int, input().split()))
 
min_r = 0
for i in range(n):
	tower_right = first_at_least(cities[i])
	tower_left = tower_right - 1
 
	min_r_for_this_city = float("inf")
	if tower_right < m:
		min_r_for_this_city = min(min_r_for_this_city, towers[tower_right] - cities[i])
 
	if tower_left >= 0:
		min_r_for_this_city = min(min_r_for_this_city, cities[i] - towers[tower_left])
 
	min_r = max(min_r, min_r_for_this_city)
 
print(min_r)

Solución 2 - Dos punteros

Explicación

Para cada ciudad, hay que hallar la distancia mínima a una torre, lo que llamamos emparejamiento. Observemos que si la posición de una torre $T$ es mayor que la de una ciudad $C$ , entonces ninguna torre con coordenada mayor que la de $T$ puede emparejarse para dar la distancia mínima con $C$ . Además, si una ciudad $C_1$ tiene posición menor que $C_2$ , entonces ninguna torre con posición menor que la de la torre de $C_1$ puede dar la distancia mínima para $C_2$ . Estos dos detalles nos permiten usar dos punteros para resolver el problema.

Guardamos dos punteros, uno para la ciudad actual y otro para la torre actual. Empezamos en la primera ciudad y la primera torre, ambas con la coordenada más chica. Calculamos la distancia entre la ciudad y torres con coordenadas cada vez mayores hasta que la coordenada de la torre actual es mayor que la de la ciudad actual. Una de esas distancias debe ser la distancia mínima de la ciudad a todas las torres. Luego empezamos el proceso para la siguiente ciudad y dejamos el puntero en la torre actual. Repetimos este proceso para todas las ciudades en orden de posición. El máximo de todas las distancias mínimas entre una ciudad y una torre será nuestra respuesta.

Implementación

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

C++PythonJava


#include <iostream>
#include <vector>
 
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;
 
int dist[MAX_N];
 
int main() {
 
	for (int i = 0; i < MAX_N; i++) { dist[i] = 2 * MOD; }
 
	int n, m;
	int res = 0;
	int j = 0;
	std::cin >> n >> m;
	std::vector<int> cities(n), towers(m);
 
	for (int &x : cities) { std::cin >> x; }
	for (int &x : towers) { std::cin >> x; }
 
	for (int i = 0; i < n; i++) {
		while (j < (m - 1) && towers[j + 1] <= cities[i]) { j++; }
		dist[i] = std::min(dist[i], std::abs(cities[i] - towers[j]));
	}
 
	j = m - 1;
	for (int i = n - 1; i >= 0; i--) {
		while (j > 0 && towers[j - 1] >= cities[i]) { j--; }
		dist[i] = std::min(dist[i], std::abs(cities[i] - towers[j]));
	}
 
	for (int i = 0; i < n; i++) { res = std::max(res, dist[i]); }
 
	std::cout << res << '\n';
}


n, m = map(int, input().split())
 
# Sacamos todas las ciudades y torres duplicadas
cities = sorted(list(set(map(int, input().split()))))
towers = sorted(list(set(map(int, input().split()))))
 
"""
Empezamos en la primera ciudad. Para cada ciudad, calculamos la distancia a las torres
hasta que la posición de la torre elegida es mayor que la de la ciudad. (Porque
entonces la distancia solo aumenta). Luego continuamos con la siguiente ciudad
empezando en la torre actual. Elegimos la distancia mínima a una torre para
cada ciudad, y el máximo de esas será nuestra respuesta.
"""
 
max_dist = 0
city_ptr = 0
tower_ptr = 0
while city_ptr < len(cities):
	city_tower_min_dist = abs(cities[city_ptr] - towers[tower_ptr])
 
	while tower_ptr + 1 < len(towers):
		tower_ptr += 1
		new_dist = abs(cities[city_ptr] - towers[tower_ptr])
		if new_dist < city_tower_min_dist:
			city_tower_min_dist = new_dist
		else:
			tower_ptr -= 1
			break
 
	max_dist = max(city_tower_min_dist, max_dist)
	city_ptr += 1
 
print(max_dist)


import java.io.*;
import java.util.*;
 
public class CellularNetwork2 {
	static final int MOD = 1000000007;
	static final int MAXIMUM_SIZE = 100000;
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int m = io.nextInt();
		int[] dist = new int[MAXIMUM_SIZE];
 
		Arrays.fill(dist, 2 * MOD);
 
		int[] a = new int[n];
		int[] b = new int[m];
 
		for (int i = 0; i < n; i++) { a[i] = io.nextInt(); }
 
		for (int i = 0; i < m; i++) { b[i] = io.nextInt(); }
 
		int pointer1 = 0;
 
		// puntero de izquierda a derecha
		for (int i = 0; i < n; i++) {
			while (pointer1 < (m - 1) && b[pointer1 + 1] <= a[i]) {
				// seguimos incrementando
				pointer1++;
			}
			dist[i] = Math.min(dist[i], Math.abs(a[i] - b[pointer1]));
		}
 
		pointer1 = m - 1;
 
		// puntero de derecha a izquierda
		for (int i = n - 1; i >= 0; i--) {
			while (pointer1 > 0 && b[pointer1 - 1] >= a[i]) { pointer1--; }
			dist[i] = Math.min(dist[i], Math.abs(a[i] - b[pointer1]));
		}
 
		int answer = 0;
		// el máximo del arreglo es la respuesta
		for (int i = 0; i < n; i++) { answer = Math.max(answer, dist[i]); }
 
		io.println(answer);
		io.close();
	}
	// CodeSnip{Kattio}
}