Why Did the Cow Cross the Road III

Explicación

Veamos la grilla como un grafo, donde cada celda es un vértice, y cada borde entre dos celdas que no contiene un camino es una arista. Para que dos vacas necesiten cruzar un camino para llegar una a la otra, deben pertenecer a dos componentes conexas distintas del grafo.

Hacemos flood fill para hallar cada componente conexa y el número de vacas dentro de ella. Para un par de componentes conexas, cada par posible de vacas entre estas componentes debe cruzar un camino para llegar a la otra. Así, la respuesta es la suma de productos por pares entre el número de vacas en cada componente.

Implementar esta solución de forma naive toma $\mathcal{O}(N^4)$ de tiempo, ya que computamos productos por pares con hasta $\mathcal{O}(N^2)$ componentes. Esto se puede optimizar a $\mathcal{O}(N^2)$ , como se describe abajo:

Optimizar las sumas de productos por pares

Sea $\mathrm{C}$ el arreglo indexado desde 0 que contiene el número de vacas en cada componente conexa. De forma naive, implementaríamos la suma de productos por pares así:

C++Python


int distant_pairs = 0;
for (int i = 0; i < C.size(); i++) {
	for (int j = 0; j < i; j++) { distant_pairs += C[i] * C[j]; }
}


distant_pairs = 0
for i in range(len(C)):
	for j in range(i):
		distant_pairs += C[i] * C[j]

Usando la propiedad distributiva, podemos factorizar $\mathrm C[i]$ del bucle interno, y hacer el resto con una variable temporal que representa la suma de prefijos, así:

C++Python


int distant_pairs = 0;
int prefix_sum = 0;
for (int i = 0; i < C.size(); i++) {
	distant_pairs += C[i] * prefix_sum;
	prefix_sum += C[i];
}


distant_pairs = 0
prefix_sum = 0
for i in range(len(C)):
	distant_pairs += C[i] * prefix_sum
	prefix_sum += C[i]

Esto hará que la complejidad temporal sea lineal en el número de componentes conexas, dejando nuestra complejidad temporal final en $\mathcal O(N^2)$ .

Implementación

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

C++JavaPython

Notemos que usar set aquí agrega un factor extra $\log R$ a la complejidad temporal.


#include <bits/stdc++.h>
using namespace std;
 
struct Road {
	int sr, sc;
	int er, ec;
};
 
/** para usar el struct en un set, hay que implementar un comparador. */
inline bool operator<(const Road &r1, const Road &r2) {
	return tie(r1.sr, r1.sc, r1.er, r1.ec) < tie(r2.sr, r2.sc, r2.er, r2.ec);
}
 
/** @return los 4 vecinos cardinales de una posición */
vector<pair<int, int>> neighbors(int r, int c) {
	return {{r + 1, c}, {r - 1, c}, {r, c + 1}, {r, c - 1}};
}
 
int main() {
	freopen("countcross.in", "r", stdin);
 
	int side_len;
	int cow_num;
	int road_num;
	cin >> side_len >> cow_num >> road_num;
 
	set<Road> roads;
	for (int r = 0; r < road_num; r++) {
		int sr, sc;
		int er, ec;
		cin >> sr >> sc >> er >> ec;
		// agregamos un camino que bloquea el movimiento en ambas direcciones
		roads.insert(Road{--sr, --sc, --er, --ec});
		roads.insert(Road{er, ec, sr, sc});
	}
 
	vector<vector<bool>> has_cow(side_len, vector<bool>(side_len));
	for (int cow = 0; cow < cow_num; cow++) {
		int r, c;
		cin >> r >> c;
		has_cow[--r][--c] = true;
	}
 
	vector<vector<bool>> visited(side_len, vector<bool>(side_len));
 
	// devuelve el # de vacas que una posición puede alcanzar y las marca como visitadas
	function<int(int, int, int, int)> connected_cow_num;
	connected_cow_num = [&](int r, int c, int prev_r, int prev_c) -> int {
		// comprobamos si estamos fuera de los límites,
		if (r < 0 || c < 0 || r >= side_len ||
		    c >= side_len
		    // en un lugar al que ya fuimos,
		    || visited[r][c]
		    // o si acabamos de cruzar un camino
		    || roads.count(Road{r, c, prev_r, prev_c})) {
			return 0;
		}
 
		visited[r][c] = true;
		int cow_num = has_cow[r][c];
		for (const auto &[nr, nc] : neighbors(r, c)) {
			cow_num += connected_cow_num(nr, nc, r, c);
		}
		return cow_num;
	};
 
	vector<int> cow_components;
	for (int r = 0; r < side_len; r++) {
		for (int c = 0; c < side_len; c++) {
			if (!visited[r][c]) {
				int comp_sz = connected_cow_num(r, c, r, c);
				if (comp_sz != 0) { cow_components.push_back(comp_sz); }
			}
		}
	}
 
	int distant_pairs = 0, prefix_sum = 0;
	for (int i = 0; i < cow_components.size(); i++) {
		distant_pairs += cow_components[i] * prefix_sum;
		prefix_sum += cow_components[i];
	}
 
	freopen("countcross.out", "w", stdout);
	cout << distant_pairs << endl;
}


import java.io.*;
import java.util.*;
 
public class CountCross {
 
	// BeginCodeSnip{Road Class}
	private static class Road {
		int sr, sc;
		int er, ec;
 
		public Road(int sr, int sc, int er, int ec) {
			this.sr = sr;
			this.sc = sc;
			this.er = er;
			this.ec = ec;
		}
 
		@Override
		public int hashCode() {
			return Objects.hash(sr, sc, er, ec);
		}
 
		@Override
		public boolean equals(Object o) {
			if (!(o instanceof Road)) { return false; }
			Road r = (Road)o;
			return sr == r.sr && sc == r.sc && er == r.er && ec == r.ec;
		}
	}
	// EndCodeSnip
 
	private static int sideLen;
	private static Set<Road> roads = new HashSet<>();
	private static boolean[][] hasCow;
	private static boolean[][] visited;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("countcross");
 
		sideLen = io.nextInt();
		int cowNum = io.nextInt();
		int roadNum = io.nextInt();
 
		for (int r = 0; r < roadNum; r++) {
			int sr = io.nextInt() - 1;
			int sc = io.nextInt() - 1;
			int er = io.nextInt() - 1;
			int ec = io.nextInt() - 1;
			roads.add(new Road(sr, sc, er, ec));
			roads.add(new Road(er, ec, sr, sc));
		}
 
		hasCow = new boolean[sideLen][sideLen];
		for (int c = 0; c < cowNum; c++) {
			hasCow[io.nextInt() - 1][io.nextInt() - 1] = true;
		}
 
		visited = new boolean[sideLen][sideLen];
		List<Integer> cowComponents = new ArrayList<>();
		for (int r = 0; r < sideLen; r++) {
			for (int c = 0; c < sideLen; c++) {
				if (!visited[r][c]) {
					int compSz = connectedCowNum(r, c, r, c);
					if (compSz != 0) { cowComponents.add(compSz); }
				}
			}
		}
 
		int distantPairs = 0, prefixSum = 0;
		for (int i = 0; i < cowComponents.size(); i++) {
			distantPairs += cowComponents.get(i) * prefixSum;
			prefixSum += cowComponents.get(i);
		}
 
		io.println(distantPairs);
		io.close();
	}
 
	/**
	 * @return el # de vacas que una posición puede alcanzar y las marca como visitadas
	 */
	private static int connectedCowNum(int r, int c, int prevR, int prevC) {
		// comprobamos si estamos fuera de los límites,
		if (r < 0 || c < 0 || r >= sideLen ||
		    c >= sideLen
		    // en un lugar al que ya fuimos,
		    || visited[r][c]
		    // o si acabamos de cruzar un camino
		    || roads.contains(new Road(r, c, prevR, prevC))) {
			return 0;
		}
 
		visited[r][c] = true;
		int cowNum = hasCow[r][c] ? 1 : 0;
		for (int[] n : neighbors(r, c)) { cowNum += connectedCowNum(n[0], n[1], r, c); }
		return cowNum;
	}
 
	/** @return los 4 vecinos cardinales de una posición */
	private static int[][] neighbors(int r, int c) {
		return new int[][] {{r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1}};
	}
 
	// CodeSnip{Kattio}
}


from typing import List, Tuple
 
 
def neighbors(r: int, c: int) -> List[Tuple[int, int]]:
	""":return: los 4 vecinos cardinales de una posición"""
	return [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
 
 
with open("countcross.in") as read:
	side_len, cow_num, road_num = [int(i) for i in read.readline().split()]
 
	roads = set()
	for _ in range(road_num):
		sr, sc, er, ec = [int(i) - 1 for i in read.readline().split()]
		roads.add((sr, sc, er, ec))
		roads.add((er, ec, sr, sc))
 
	has_cow = [[False for _ in range(side_len)] for _ in range(side_len)]
	for _ in range(cow_num):
		r, c = [int(i) - 1 for i in read.readline().split()]
		has_cow[r][c] = True
 
visited = [[False for _ in range(side_len)] for _ in range(side_len)]
 
 
def connected_cow_num(r: int, c: int, prev_r: int, prev_c: int) -> int:
	""":return: el # de vacas que una posición puede alcanzar y las marca como visitadas"""
	# comprobamos si estamos fuera de los límites,
	if (
		r < 0
		or c < 0
		or r >= side_len
		or c >= side_len
		# en un lugar al que ya fuimos,
		or visited[r][c]
		# o si acabamos de cruzar un camino
		or (r, c, prev_r, prev_c) in roads
	):
		return 0
 
	visited[r][c] = True
	cow_num = has_cow[r][c]
	for nr, nc in neighbors(r, c):
		cow_num += connected_cow_num(nr, nc, r, c)
	return cow_num
 
 
cow_components = []
for r in range(side_len):
	for c in range(side_len):
		if not visited[r][c]:
			comp_sz = connected_cow_num(r, c, r, c)
			if comp_sz != 0:
				cow_components.append(comp_sz)
 
distant_pairs = 0
prefix_sum = 0
for i in range(len(cow_components)):
	distant_pairs += cow_components[i] * prefix_sum
	prefix_sum += cow_components[i]
 
print(distant_pairs, file=open("countcross.out", "w"))