Skip to Content
CTRL K

Cowpatibility

Análisis oficial (C++) 

Pista

En vez de intentar hallar el número de pares incompatibles, ¡intenta hallar el número de pares compatibles!

Esto se conoce como conteo complementario .

Solución

Explicación

Como hay un total de N(N−1)2\frac{N(N-1)}{2} pares de vacas, si podemos contar el número de pares compatibles, ¡podemos restarlo del total para obtener nuestra respuesta!

¡Podemos usar PIE (principio de inclusión-exclusión)  para calcular el número de pares compatibles! Tendremos que sumar todos los pares de vacas que comparten un sabor en común, restar las vacas que comparten dos sabores en común, y así sucesivamente…

Para entender por qué esto funciona, imaginemos que solo tenemos tres sabores de helado y que algunas vacas comparten más de un sabor. Si solo contáramos los pares de vacas con un sabor, los pares de vacas que comparten dos sabores se sobrecontarían, como se muestra en la animación de abajo:

Para evitar considerar conjuntos reordenados de los mismos sabores, ordenaremos de antemano los sabores favoritos de cada vaca.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
const int FLAVORS = 5;
 
int main() {
	freopen("cowpatibility.in", "r", stdin);
	freopen("cowpatibility.out", "w", stdout);
 
	long long n;
	cin >> n;
 
	vector<array<int, FLAVORS>> cows(n);
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < FLAVORS; j++) { cin >> cows[i][j]; }
 
		// sort flavors to avoid double counting
		sort(cows[i].begin(), cows[i].end());
	}
 
	// common[i][j] = the number of cows that share i flavors (j) in common
	vector<map<array<int, FLAVORS>, int>> common(FLAVORS);
 
	for (int i = 0; i < n; i++) {
		common[4][cows[i]]++;
 
		// iterate over all subsets
		for (int a = 0; a < FLAVORS; a++) {
			common[0][{cows[i][a]}]++;
			for (int b = a + 1; b < FLAVORS; b++) {
				common[1][{cows[i][a], cows[i][b]}]++;
				for (int c = b + 1; c < FLAVORS; c++) {
					common[2][{cows[i][a], cows[i][b], cows[i][c]}]++;
					for (int d = c + 1; d < FLAVORS; d++) {
						common[3][{cows[i][a], cows[i][b], cows[i][c], cows[i][d]}]++;
					}
				}
			}
		}
	}
 
	long long compatible = 0;
	// use PIE to count the number of compatible pairs
	// (see explanation above)
	for (int i = 0; i < FLAVORS; i++) {
		for (auto &[k, v] : common[i]) {
			if (i % 2 == 0) {
				compatible += (long long)v * (v - 1) / 2;
			} else {
				compatible -= (long long)v * (v - 1) / 2;
			}
		}
	}
 
	cout << (n * (n - 1) / 2) - compatible << endl;
}
from itertools import combinations
from collections import defaultdict
 
FLAVORS = 5
 
with open("cowpatibility.in", "r") as read:
	n = int(read.readline().strip())
	cows = []
 
	for _ in range(n):
		flavors = list(map(int, read.readline().strip().split()))
		flavors.sort()  # Sort to avoid double counting
		cows.append(flavors)
 
# common[i][j] = the number of cows that share i flavors (j) in common
common = [defaultdict(int) for _ in range(FLAVORS)]
 
for flavors in cows:
	common[4][tuple(flavors)] += 1
 
	# iterate over all subsets
	for size in range(1, FLAVORS):
		for subset in combinations(flavors, size):
			common[size - 1][subset] += 1
 
compatible = 0
# use PIE to count the number of compatible pairs
# (see explanation above)
for i in range(FLAVORS):
	for subset, count in common[i].items():
		if i % 2 == 0:
			compatible += count * (count - 1) // 2
		else:
			compatible -= count * (count - 1) // 2
 
res = n * (n - 1) // 2 - compatible
print(res, file=open("cowpatibility.out", "w"))
Fundamentos