Traffic Lights

Solución en video

Por Abhiraj Mallangi

Nota: la solución en video puede no coincidir con las demás soluciones. Código en C++.

Solución 1

Explicación

Creemos un conjunto y un multiconjunto. El conjunto guardará las posiciones de los semáforos, mientras que el multiconjunto llevará cuenta de los “huecos” entre las luces. El multiconjunto se va expandiendo porque se añaden más luces, y solo hay que imprimir la longitud del pasaje más largo sin semáforos después de cada adición (es decir, el elemento máximo de ese multiconjunto). Este elemento es el último por defecto.

Nótese que, al colocar un semáforo nuevo en la calle, esa luz parte el hueco entre dos luces adyacentes en dos trozos más pequeños, así que también hay que quitar la longitud de ese hueco del multiconjunto y añadir dos longitudes nuevas al multiconjunto.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	int street_len;
	int light_num;
	cin >> street_len >> light_num;
 
	set<int> lights{0, street_len};
	multiset<int> dist{street_len};
	for (int l = 0; l < light_num; l++) {
		int pos;
		cin >> pos;
 
		auto it1 = lights.upper_bound(pos);
		auto it2 = it1;
		--it2;
 
		dist.erase(dist.find(*it1 - *it2));
		dist.insert(pos - *it2);
		dist.insert(*it1 - pos);
		lights.insert(pos);
 
		auto ans = dist.end();
		--ans;
		cout << *ans << " ";
	}
}

Solución 2 - Ir hacia atrás

Explicación

Empezaremos intentando hallar el hueco máximo una vez añadidos todos los semáforos. Este es el último número que imprimiremos, así que lo añadiremos al final de nuestro arreglo de salida. Luego quitaremos semáforos en el orden inverso al que se añadieron, y hallaremos el hueco que crea cada eliminación.

Este hueco es simplemente la distancia entre las dos coordenadas de la calle (ya sea un semáforo o el inicio o el fin de la calle) junto a un semáforo dado guardado en nuestro conjunto, así que podemos usar el conjunto para hallar estos valores y restarlos para obtener el hueco.

Pero este hueco puede no ser el hueco máximo. Lo compararemos con el hueco que hallamos una vez añadidos todos los semáforos, y pondremos el hueco máximo al mayor valor. Luego pondremos el siguiente elemento más bajo del arreglo de salida a este valor, que representará el mayor hueco antes de añadir el semáforo que acabamos de quitar.

Implementación 1

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

C++Java


#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int street_len;
	int light_num;
	std::cin >> street_len >> light_num;
	vector<int> lights(light_num);
	for (int &l : lights) { std::cin >> l; }
	// Initialize the set with beginning and ending values
	std::set<int> street_pos{0, street_len};
	for (int l : lights) { street_pos.insert(l); }
 
	vector<int> gaps(light_num);
	int prev = 0;
	int max_gap = 0;
	// Find the longest passage once all the streetlights are added
	for (int p : street_pos) {
		max_gap = std::max(max_gap, p - prev);
		prev = p;
	}
	gaps.back() = max_gap;
 
	/*
	 * Remove the streetlights in reverse order to how they were added, then
	 * find the gap created by removing each. Find the biggest current gap, and
	 * add it to the next lowest index in answer.
	 */
	for (int i = light_num - 1; i > 0; i--) {
		street_pos.erase(lights[i]);
		auto high_it = street_pos.upper_bound(lights[i]);
		int high = *high_it;
		int low = *(--high_it);
		max_gap = std::max(max_gap, high - low);
		gaps[i - 1] = max_gap;
	}
 
	for (int i = 0; i < gaps.size() - 1; i++) { cout << gaps[i] << ' '; }
	cout << gaps.back() << endl;
}


import java.io.*;
import java.util.*;
 
public class TrafficLights {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
 
		int streetLength = io.nextInt();
		int lightNum = io.nextInt();
 
		// Using an array to read values since we can't get values from sets in
		// Java
		int[] opArray = new int[lightNum];
		NavigableSet<Integer> streetPositions = new TreeSet<>();
		// Initialize the set with beginning and ending values
		streetPositions.add(0);
		streetPositions.add(streetLength);
 
		for (int i = 0; i < lightNum; i++) {
			int nextTrafficLight = io.nextInt();
			opArray[i] = nextTrafficLight;
			streetPositions.add(nextTrafficLight);
		}
 
		int[] gapsArray = new int[lightNum];
		int prev = 0;
		int maxGap = 0;
		// Find the longest passage once all the streetlights are added
		for (int i : streetPositions) {
			maxGap = Math.max(i - prev, maxGap);
			prev = i;
		}
 
		gapsArray[lightNum - 1] = maxGap;
		/*
		 * Remove the streetlights in reverse order to how they were added,
		 * then find the gap created by removing each. Find the biggest
		 * current gap, and add it to the next lowest index in answer.
		 */
		for (int i = lightNum - 1; i > 0; i--) {
			streetPositions.remove(opArray[i]);
			int low = streetPositions.lower(opArray[i]);
			int high = streetPositions.higher(opArray[i]);
			maxGap = Math.max(maxGap, high - low);
			gapsArray[i - 1] = maxGap;
		}
 
		//  Use StringBuilder to print out the array quicker
		StringBuilder sb = new StringBuilder();
		for (int i : gapsArray) { sb.append(i).append(" "); }
		io.println(sb);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Implementación 2

La solución anterior usa un conjunto ordenado. Aunque facilita la implementación, también añade un factor extra $\log n$ a la complejidad temporal. Para quitarlo, podemos usar una lista doblemente enlazada .

C++


#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int street_len;
	int light_num;
	std::cin >> street_len >> light_num;
	vector<int> lights(light_num);
	for (int &l : lights) { std::cin >> l; }
 
	vector<std::pair<int, int>> sorted_lights(light_num);
	for (int l = 0; l < light_num; l++) { sorted_lights[l] = {lights[l], l}; }
	std::sort(sorted_lights.begin(), sorted_lights.end());
 
	// Given the light position, this array stores its position in
	// sorted_lights.
	vector<int> new_pos(light_num);
	for (int l = 0; l < light_num; l++) { new_pos[sorted_lights[l].second] = l; }
 
	struct Light {
		int prev, next;
		int pos;
	};
	vector<Light> light_ll(light_num + 2);
	// First, we set our "lights" on the edges of the street.
	light_ll[0] = {-1, 1, 0};
	light_ll[light_num + 1] = {light_num, -1, street_len};
	for (int l = 0; l < light_num; l++) {
		light_ll[l + 1] = {l, l + 2, sorted_lights[l].first};
	}
 
	// Find the longest passage once all the streetlights are added
	vector<int> gaps(light_num);
	int max_gap = 0;
	for (int l = 0; l <= light_num; l++) {
		max_gap = std::max(max_gap, light_ll[l + 1].pos - light_ll[l].pos);
	}
	gaps.back() = max_gap;
 
	// Remove the streetlights in reverse order like as we did in the above
	// solution.
	for (int l = light_num - 1; l > 0; l--) {
		Light to_del = light_ll[new_pos[l] + 1];
		Light &left = light_ll[to_del.prev];
		Light &right = light_ll[to_del.next];
		// Re-assign the references to the next & previous node
		left.next = to_del.next;
		right.prev = to_del.prev;
 
		max_gap = std::max(max_gap, right.pos - left.pos);
		gaps[l - 1] = max_gap;
	}
 
	for (int i = 0; i < gaps.size() - 1; i++) { cout << gaps[i] << ' '; }
	cout << gaps.back() << endl;
}