USACO 2017 US Open Contest Bronze Division - Bovine Genomics

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Simulate the process and for each letter, you want to make sure it doesn't show up in both of the sets at the same time.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ifstream cin("cownomics.in");
    ofstream cout("cownomics.out");

    int n, m;
    cin >> n >> m;

    vector<vector<char> > v(n+n+1, vector<char> (m+1));

    for(int i = 1; i <= n+n; i++)
        for(int j = 1; j <= m; j++)
            cin >> v[i][j];

    int cnt = 0;
    for(int pos = 1; pos <= m; pos++)
    {
        set<char> spotty, plain;
        for(int i = 1; i <= n; i++)
            spotty.insert(v[i][pos]);
        for(int i = n+1; i <= n+n; i++)
            plain.insert(v[i][pos]);
        if(spotty.find('A') != spotty.end() && plain.find('A') != plain.end())
            continue;
        if(spotty.find('C') != spotty.end() && plain.find('C') != plain.end())
            continue;
        if(spotty.find('G') != spotty.end() && plain.find('G') != plain.end())
            continue;
        if(spotty.find('T') != spotty.end() && plain.find('T') != plain.end())
            continue;
        cnt++;
    }
    cout << cnt;
    return 0;
}

with open("cownomics.in", "r") as fin:
    n, m = map(int, fin.readline().split())
    genome = [fin.readline().strip() for _ in range(2 * n)]

cnt = 0
for pos in range(m):
    spotty = {genome[i][pos] for i in range(n)}
    plain = {genome[i][pos] for i in range(n, 2 * n)}
    if not (spotty & plain):
        cnt += 1

with open("cownomics.out", "w") as fout:
    fout.write(str(cnt))