Genetics

Explicación

Un método naive sería iterar por cada par de clones y calcular la cantidad de posiciones con genomas distintos en tiempo casi $\mathcal{O}(1)$ . Esto parece virtualmente imposible, así que probablemente deberíamos intentar un método distinto.

¿Y si de alguna forma lográramos comprobar cada clon contra todos los demás clones al mismo tiempo? De esta forma podríamos recorrer cada carácter y mantener una complejidad temporal $\mathcal{O}(N^2)$ .

Podemos precalcular para cada posición la cantidad de As, Ts, Cs y Gs que tienen todos los clones. Luego, al comprobar un solo sujeto, vemos cuántos de los demás genomas se han hallado en esa posición y sumamos todas las diferencias al final.

Sin embargo, esto trae otro problema: ¡no hay forma de comprobar a qué clon pertenece cada genoma! Si nuestro sujeto difiere de un clon en $k-1$ posiciones y de otro clon en $k+1$ posiciones, nuestro algoritmo actual no tendría idea de que no son el villano real, ya que la diferencia total de los dos sigue siendo $2k$ , la misma que si el sujeto diferiera de ambos en $k$ posiciones.

Para resolver este problema, podemos asignar a cada clon un peso aleatorio $R_i$ . Luego, en lugar de calcular solo la cantidad de clones con un cierto genoma en una cierta posición, calculamos la suma de los pesos de estos clones. Esto nos permite diferenciar entre una diferencia de genoma debida al clon $A$ versus una diferencia de genoma debida al clon $B$ .

Implementación

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

C++


#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
const vector<char> DNA{'A', 'T', 'C', 'G'};
 
int main() {
	int dna_num, seq_len;
	int diff_num;
	std::cin >> dna_num >> seq_len >> diff_num;
 
	vector<vector<char>> dna(dna_num, vector<char>(seq_len));
	for (int d = 0; d < dna_num; d++) {
		for (int i = 0; i < seq_len; i++) { std::cin >> dna[d][i]; }
	}
 
	// generamos pesos aleatorios de 32 bits para cada uno de los clones
	std::random_device rd;
	std::mt19937 gen(42069);
	std::uniform_int_distribution<> distr(1, INT32_MAX);
	vector<long long> weights(dna_num);
	for (int d = 0; d < dna_num; d++) { weights[d] = distr(gen); }
	// la suma de todos los pesos de los clones
	long long weight_sum = std::accumulate(weights.begin(), weights.end(), 0LL);
 
	/*
	 * dna_eq[d][j] = la suma de todos los pesos de los clones
	 * que tienen su j-ésima posición igual a DNA[d]
	 */
	vector<vector<long long>> dna_eq(DNA.size(), vector<long long>(seq_len));
	for (int d = 0; d < DNA.size(); d++) {
		for (int i = 0; i < dna_num; i++) {
			for (int j = 0; j < seq_len; j++) {
				dna_eq[d][j] += (dna[i][j] == DNA[d]) * weights[i];
			}
		}
	}
 
	for (int d = 0; d < dna_num; d++) {
		long long missed_amt = 0;
		for (int i = 0; i < DNA.size(); i++) {
			for (int j = 0; j < seq_len; j++) {
				if (dna[d][j] == DNA[i]) {
					/*
					 * tomamos todos los clones que NO comparten el mismo
					 * genoma en esta posición y hallamos la suma de sus pesos
					 */
					missed_amt += weight_sum - dna_eq[i][j];
				}
			}
		}
 
		// comprobamos si esto coincide con los requisitos del problema
		if (missed_amt == (weight_sum - weights[d]) * diff_num) {
			cout << (d + 1) << endl;
			break;
		}
	}
}