Cow Evolution

Pista

Intentemos construir un conjunto mínimo de vacas que no puedan formar un árbol evolutivo válido. ¿Cómo se generaliza a distintos árboles?

Solución

Explicación

Primero, puede ayudar pensar en una instancia en la que no podemos formar un árbol evolutivo correcto. Sería una instancia tal que, no importa cómo formemos el árbol, sería inevitable que alguna característica evolucionara en dos lugares distintos del árbol. Resulta que el ejemplo malo mínimo se ve así:

\begin{align*} &\texttt{population1: A } \\ &\texttt{population2: B } \\ &\texttt{population3: A B} \end{align*}

En otras palabras, tenemos una población con solo el rasgo $A$ , una población con solo el rasgo $B$ , y una población con ambos. Si queremos construir un árbol a partir de esta entrada, habría que partir por $A$ o por $B$ en la raíz, pero entonces los dos subárboles restantes necesitarían ambos una arista que agregue la otra característica. Por ejemplo, si la raíz se parte en ramas " $A$ " y “no $A$ ”, entonces ambas ramas necesitarían contener una arista que agregue el rasgo $B$ .

Ayuda mirar las cosas desde el punto de vista de las características en lugar del de las poblaciones, así que “transponemos” la entrada de arriba:

\begin{align*} \texttt{A: population1 population3} \\ \texttt{B: population2 population3} \end{align*}

El problema fundamental acá es que hay poblaciones solo en $A$ , poblaciones solo en $B$ , y poblaciones en $A$ y $B$ . Si miramos el diagrama de Venn de los conjuntos $A$ y $B$ , la imagen se ve así:

Venn Diagram 1

Llamemos a esta situación un par de conjuntos que se “cruzan”. En general, dos conjuntos pueden ser disjuntos (sin superposición), anidados (uno dentro del otro) o cruzados (superposición pero no anidados). Si cualesquiera dos de las características $A$ y $B$ de nuestra instancia representan conjuntos que se cruzan como arriba, entonces no podemos construir un árbol correcto. Por otro lado, si todas las características representan conjuntos que no se cruzan (son disjuntos o anidados), entonces obtenemos un diagrama de Venn como este:

Venn Diagram 2

Si se mira esta imagen con cuidado, ojalá se vea un árbol formado por la estructura de anidamiento de los conjuntos:

Evolution tree diagram

Un árbol como este es fácil de convertir en un árbol evolutivo correcto: si tenemos tres hijos $A$ , $B$ y $C$ , podríamos simplemente hacer tres particiones secuenciales de dos vías que agregan las características $A$ , $B$ y $C$ .

Así que en realidad no hace falta construir un árbol evolutivo correcto; solo hay que comprobar si alguna de nuestras características representa conjuntos que se cruzan.

Nota matemática

En otras palabras, hay que comprobar si la familia de conjuntos dada es laminar o no.

Implementación

Complejidad temporal: $\mathcal{O}((\sum K)^3)$

C++JavaPython


#include <fstream>
#include <iostream>
#include <set>
#include <string>
#include <vector>
 
using std::cout;
using std::endl;
using std::set;
using std::string;
using std::vector;
 
int main() {
	std::ifstream read("evolution.in");
	int n;
	read >> n;
 
	vector<set<string>> cows;
	set<string> all_char_set;
	for (int c = 0; c < n; c++) {
		int char_num;
		read >> char_num;
		set<string> curr_cow;
		for (int i = 0; i < char_num; i++) {
			string characteristic;
			read >> characteristic;
			curr_cow.insert(characteristic);
		}
		all_char_set.insert(curr_cow.begin(), curr_cow.end());
		cows.push_back(curr_cow);
	}
 
	vector<string> all_chars(all_char_set.begin(), all_char_set.end());
 
	std::ofstream written("evolution.out");
	// Iteramos por cada par de características y comprobamos si el árbol es
	// evolutivamente correcto respecto de ese par
	for (int a = 0; a < all_chars.size(); a++) {
		for (int b = a + 1; b < all_chars.size(); b++) {
			bool both = false, only_a = false, only_b = false;
			for (const set<string> &c : cows) {
				bool has_a = c.count(all_chars[a]);
				bool has_b = c.count(all_chars[b]);
 
				if (has_a && has_b) {
					both = true;
				} else if (has_a && !has_b) {
					only_a = true;
				} else if (!has_a && has_b) {
					only_b = true;
				}
			}
 
			/*
			 * Si encontramos una vaca que tiene la característica a,
			 * otra vaca que tiene la característica b, y
			 * otra vaca con ambas características a y b, entonces
			 * el árbol no es evolutivamente correcto.
			 */
			if (only_a && only_b && both) {
				written << "no" << endl;
				return 0;
			}
		}
	}
 
	written << "yes" << endl;
}


import java.io.*;
import java.util.*;
 
public class Evolution {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("evolution.in"));
		int n = Integer.parseInt(read.readLine());
 
		List<Set<String>> cows = new ArrayList<>();
		Set<String> allCharSet = new HashSet<>();
		for (int c = 0; c < n; c++) {
			StringTokenizer chars = new StringTokenizer(read.readLine());
			int charNum = Integer.parseInt(chars.nextToken());
			Set<String> currCow = new HashSet<>();
			for (int i = 0; i < charNum; i++) { currCow.add(chars.nextToken()); }
			allCharSet.addAll(currCow);
			cows.add(currCow);
		}
		read.close();
 
		List<String> allChars = new ArrayList<>(allCharSet);
 
		PrintWriter written = new PrintWriter("evolution.out");
		// Iteramos por cada par de características y comprobamos si el árbol es
		// evolutivamente correcto respecto de ese par
		for (int a = 0; a < allChars.size(); a++) {
			for (int b = a + 1; b < allChars.size(); b++) {
				boolean both = false, onlyA = false, onlyB = false;
				for (Set<String> c : cows) {
					boolean hasA = c.contains(allChars.get(a));
					boolean hasB = c.contains(allChars.get(b));
 
					if (hasA && hasB) {
						both = true;
					} else if (hasA && !hasB) {
						onlyA = true;
					} else if (!hasA && hasB) {
						onlyB = true;
					}
				}
 
				/*
				 * Si encontramos una vaca que tiene la característica a,
				 * otra vaca que tiene la característica b, y
				 * otra vaca con ambas características a y b, entonces
				 * el árbol no es evolutivamente correcto.
				 */
				if (onlyA && onlyB && both) {
					written.println("no");
					written.close();
					System.exit(0);
				}
			}
		}
 
		written.println("yes");
		written.close();
	}
}


import sys
 
with open("evolution.in") as read:
	n = int(read.readline())
	cows = []
	all_chars = set()
	for _ in range(n):
		chars = set(read.readline().split()[1:])
		cows.append(chars)
		all_chars.update(chars)
 
all_chars = list(all_chars)
 
written = open("evolution.out", "w")
# Iteramos por cada par de características y comprobamos si el árbol es
# evolutivamente correcto respecto de ese par
for a in range(len(all_chars)):
	for b in range(a + 1, len(all_chars)):
		both, only_a, only_b = False, False, False
		for c in cows:
			has_a = all_chars[a] in c
			has_b = all_chars[b] in c
 
			if has_a and has_b:
				both = True
			elif has_a and not has_b:
				only_a = True
			elif has_b and not has_a:
				only_b = True
 
		"""
		Si encontramos una vaca que tiene la característica a,
		otra vaca que tiene la característica b, y
		otra vaca con ambas características a y b, entonces
		el árbol no es evolutivamente correcto.
		"""
		if only_a and only_b and both:
			print("no", file=written)
			sys.exit()
 
print("yes", file=written)

Solución en video

Video de YouTube (4YTijr0BbrA)