by Nathan Pinsker

How do we tell if a position can explain spottiness? Let's turn that question around and ask the reverse: how do we tell if a position can't explain spottiness? The answer to this question is that if we come across two cows, one of which is spotted and one of which is not, that have the same base in their genome at that position, then that position isn't sufficient. This is because we won't be able to tell those two cows apart.

The way to solve this problem is to check each position individually to see whether it's sufficient to explain spottiness. For each of the $M$ possible positions, we check whether there's any base that appears at that position in both a spotty and a non-spotty cow. We do this by first iterating over every non-spotty cow, and recording whether we can find an A, C, G, or T at that position in the cow's genome. We do the same for the spotty cows, and check at each step if we've already found a non-spotty cow with the same base. If we find a spotty cow that shares a base with a non-spotty cow in this position, then this position isn't sufficient to explain spottiness. If we can't find any of these overlaps over any of the four bases, then the position can successfully be used.

Here's my code, modified a little from Brian's:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

int N, M;
string spotty[100], plain[100];

bool test_location(int j)
{
bool found_cow[2][4] = {0};
// found_cow[0] refers to spotty cows, and found_cow[1]
// refers to non-spotty cows.
for (int i=0; i<N; i++) {
if (spotty[i][j] == 'A') found_cow[0][0] = true;
if (spotty[i][j] == 'C') found_cow[0][1] = true;
if (spotty[i][j] == 'G') found_cow[0][2] = true;
if (spotty[i][j] == 'T') found_cow[0][3] = true;
}
for (int i=0; i<N; i++) {
if (plain[i][j] == 'A') found_cow[1][0] = true;
if (plain[i][j] == 'C') found_cow[1][1] = true;
if (plain[i][j] == 'G') found_cow[1][2] = true;
if (plain[i][j] == 'T') found_cow[1][3] = true;
}
for (int i = 0; i < 4; ++i) {
if (found_cow[0][i] && found_cow[1][i]) return false;
}
return true;
}

int main(void)
{
ifstream fin ("cownomics.in");
ofstream fout ("cownomics.out");
fin >> N >> M;
for (int i=0; i<N; i++) fin >> spotty[i];
for (int i=0; i<N; i++) fin >> plain[i];