USACO 2017 US Open Contest Silver Division - Bovine Genomics

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main observation you need to find is the fact that the number of columns is small, so we can brute force every triple of columns. However, we need to process the rows effectively, and this can be done by either storing a codification of the triplet of letters, or using a hashmap to find the matches from one group in the other.

Source code

The source code in C++ can be seen below.

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

using namespace std;

const map<char, int> GENOME_ID{{'A', 0}, {'T', 1}, {'C', 2}, {'G', 3}};

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

    int cow_num;
    int genome_len;
    cin >> cow_num >> genome_len;

    vector<vector<int>> spotted(cow_num, vector<int>(genome_len));
    for (int s = 0; s < cow_num; s++) {
        string genome;
        cin >> genome;
        for (int g = 0; g < genome_len; g++) {
            spotted[s][g] = GENOME_ID.at(genome[g]);
        }
    }

    vector<vector<int>> plain(cow_num, vector<int>(genome_len));
    for (int p = 0; p < cow_num; p++) {
        string genome;
        cin >> genome;
        for (int g = 0; g < genome_len; g++) {
            plain[p][g] = GENOME_ID.at(genome[g]);
        }
    }

    int valid_sets = 0;
    for (int a = 0; a < genome_len; a++) {
        for (int b = a + 1; b < genome_len; b++) {
            for (int c = b + 1; c < genome_len; c++) {
                vector<bool> spotted_ids(64);
                for (int sc = 0; sc < cow_num; sc++) {
                    int total = (spotted[sc][a] * 16 + spotted[sc][b] * 4 + spotted[sc][c] * 1);
                    spotted_ids[total] = true;
                }

                bool valid = true;
                for (int pc = 0; pc < cow_num; pc++) {
                    int total = (plain[pc][a] * 16 + plain[pc][b] * 4 + plain[pc][c] * 1);
                    if (spotted_ids[total]) {
                        valid = false;
                        break;
                    }
                }

                valid_sets += valid;
            }
        }
    }

    cout << valid_sets << '\n';
    return 0;
}