Stuck in a Rut

Solución en video

Nota: la solución en video puede no ser la misma que las demás soluciones. Código en C++.

Explicación

Supongamos que tenemos una vaca que viaja en horizontal en $(x_h, y_h)$ y otra que viaja en vertical en $(x_v,y_v)$ . Se intersectarán en $(x_v,y_h)$ siempre que $x_h\lt x_v$ y $y_v\lt y_h$ . Si una vaca llega primero a este punto, la que llega después se detendrá.

Sin embargo, las vacas pueden detenerse antes de alcanzar intersecciones posibles con otras vacas. Por eso hay que ordenar las vacas para procesarlas de forma que se evite este problema. Ordenamos las vacas que van al este por valores verticales crecientes, y las que van al norte por valores horizontales crecientes. El orden garantiza que, una vez que encontramos una colisión potencial, todas las vacas que podrían haber sido detenidas ya lo habrían sido. Luego podemos comprobar cada par de vacas según los siguientes criterios:

Si alguna de las dos vacas ya se detuvo, podemos saltar este par.
Si sus caminos no se intersectan, podemos saltar este par.
Si ninguna se ha detenido y sí se intersectan, detenemos la vaca que está más lejos de la intersección.

Implementación

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

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	vector<int> x_coordinates(n);
	vector<int> y_coordinates(n);
	vector<int> east_cows;
	vector<int> north_cows;
 
	for (int i = 0; i < n; i++) {
		char direction;
		cin >> direction >> x_coordinates[i] >> y_coordinates[i];
		if (direction == 'E') {
			east_cows.push_back(i);
		} else {
			north_cows.push_back(i);
		}
	}
 
	// ordenar las vacas del este por coordenada y
	sort(east_cows.begin(), east_cows.end(),
	     [&](int a, int b) { return y_coordinates[a] < y_coordinates[b]; });
	// ordenar las vacas del norte por coordenada x
	sort(north_cows.begin(), north_cows.end(),
	     [&](int a, int b) { return x_coordinates[a] < x_coordinates[b]; });
 
	vector<bool> stopped(n);
	vector<int> amount_stopped(n);
	for (int j : east_cows) {  // recorrer todos los pares de vacas
		for (int k : north_cows) {
			/*
			 * asegurarnos de que tanto la vaca del este como la del norte
			 * no estén detenidas; una colisión solo es posible
			 * si la x de la vaca del norte es mayor
			 * que la x de la vaca del este y la y de la vaca del este
			 * es mayor que la y de la vaca del norte
			 */
			if ((!stopped[j]) && (!stopped[k]) &&
			    (x_coordinates[k] > x_coordinates[j]) &&
			    (y_coordinates[j] > y_coordinates[k])) {
				if ((x_coordinates[k] - x_coordinates[j]) >
				    (y_coordinates[j] - y_coordinates[k])) {
					// la vaca del norte detiene a la del este
					// marcar la vaca del este como detenida
					stopped[j] = true;
 
					// sumar la cantidad de vacas que detiene la del este + 1
					amount_stopped[k] += (1 + amount_stopped[j]);
				} else if ((x_coordinates[k] - x_coordinates[j]) <
				           (y_coordinates[j] - y_coordinates[k])) {
					// la vaca del este detiene a la del norte
					// marcar la vaca del norte como detenida
					stopped[k] = true;
 
					// sumar la cantidad de vacas que detiene la del norte + 1
					amount_stopped[j] += (1 + amount_stopped[k]);
				}
				// si la diferencia en x y la diferencia en y son iguales,
				// dejar que las vacas sigan como indica el enunciado
			}
		}
	}
 
	for (int i = 0; i < n; i++) { cout << amount_stopped[i] << '\n'; }
}


import java.io.*;
import java.util.*;
 
public class StuckInARut {
	static int[] xCoordinates;
	static int[] yCoordinates;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
 
		List<Integer> eastCows = new ArrayList<>();
		List<Integer> northCows = new ArrayList<>();
		xCoordinates = new int[n];
		yCoordinates = new int[n];
 
		for (int i = 0; i < n; i++) {
			StringTokenizer line = new StringTokenizer(br.readLine());
			String direction = line.nextToken();
			if (direction.equals("E")) {
				eastCows.add(i);
			} else {
				northCows.add(i);
			}
			xCoordinates[i] = Integer.parseInt(line.nextToken());
			yCoordinates[i] = Integer.parseInt(line.nextToken());
		}
 
		// ordenar las vacas del este por coordenada y
		eastCows.sort(Comparator.comparingInt(j -> yCoordinates[j]));
		// ordenar las vacas del norte por coordenada x
		northCows.sort(Comparator.comparingInt(j -> xCoordinates[j]));
 
		boolean[] stopped = new boolean[n];
		int[] amountStopped = new int[n];
		for (int j : eastCows) {  // recorrer todos los pares de vacas
			for (int k : northCows) {
				/*
				 * asegurarnos de que tanto la vaca del este como la del norte
				 * no estén detenidas; una colisión solo es posible
				 * si la x de la vaca del norte es mayor
				 * que la x de la vaca del este y la y de la vaca del este
				 * es mayor que la y de la vaca del norte
				 */
				if ((!stopped[j]) && (!stopped[k]) &&
				    (xCoordinates[k] > xCoordinates[j]) &&
				    (yCoordinates[j] > yCoordinates[k])) {
					if ((xCoordinates[k] - xCoordinates[j]) >
					    (yCoordinates[j] - yCoordinates[k])) {
						// la vaca del norte detiene a la del este
						// marcar la vaca del este como detenida
						stopped[j] = true;
 
						// sumar la cantidad de vacas que detiene la del este + 1
						amountStopped[k] += (1 + amountStopped[j]);
					} else if ((xCoordinates[k] - xCoordinates[j]) <
					           (yCoordinates[j] - yCoordinates[k])) {
						// la vaca del este detiene a la del norte
						// marcar la vaca del norte como detenida
						stopped[k] = true;
 
						// sumar la cantidad de vacas que detiene la del norte + 1
						amountStopped[j] += (1 + amountStopped[k]);
					}
					// si la diferencia en x y la diferencia en y son iguales,
					// dejar que las vacas sigan como indica el enunciado
				}
			}
		}
 
		for (int i = 0; i < n; i++) { System.out.println(amountStopped[i]); }
	}
}