Video Solution

By Jay Fu

Official Editorial (C++)

Explanation

We need to loop over all possible sets of 3 distinct positions.

For each set of positions, we then go through all spotted cows and store their gene pattern at these three positions as an integer.

The way we do this is by interpreting the pattern as a base-4 integer. If we map A to 0, T to 1, C to 2, and G to 3, the gene pattern CTG would be the base-4 number $213$ (or $32 + 4 + 3 = 39$ in base 10).

The benefit of this approach is that it allows us to quickly check if two cows have the same pattern without doing a direct string comparison.

We then loop through the non-spotted cows, and create the integers the same way as above. If any integer appears in both a plain cow and a spotted cow, then the current set of positions isn't valid. Otherwise, we can add one to our answer.

Implementation

Time Complexity $\mathcal{O}(NM^3)$

Copy
#include <fstream>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

Copy
import java.io.*;
import java.util.*;

public class BovineGenomics {
	static final Map<Character, Integer> GENOME_ID = Map.ofEntries(
	    Map.entry('A', 0), Map.entry('T', 1), Map.entry('C', 2), Map.entry('G', 3));

	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("cownomics");

Copy
GENOME_ID = {"A": 0, "T": 1, "C": 2, "G": 3}

with open("cownomics.in") as read:
	cow_num, genome_len = [int(i) for i in read.readline().split()]

	spotted = []
	for _ in range(cow_num):
		genome_str = read.readline()
		genome = []
		for g in range(genome_len):