USACO Bronze 2017 US Open - Bovine Genomics

Authors: Mrinall Umasudhan, Ananth Kashyap, Ben Dodge, Aadit Ambadkar, Jay Fu

Edit This Page

Official Analysis (C++)

Video Solution

By Jay Fu

Video Solution Code

Solution 1 - Brute force

We'll iterate through every character in every genome. For each character index, we'll find if there are any characters that appear in the genome of both a spotted and plain cow at that index. If there are, this position isn't a possible solution, so we can end this part of our search and move on to the next position to save on runtime. If there aren't, this is a possible solution.

Implementation

Time Complexity: O(MN2)\mathcal O(MN^2)

C++

#include <fstream>
#include <iostream>
#include <vector>


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


int main() {
	std::ifstream read("cownomics.in");

Java

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


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


		int n = io.nextInt();
		int m = io.nextInt();

Python

with open("cownomics.in", "r") as read:
	n, m = map(int, read.readline().split())


	# Each genome and the individual characters in each genome
	spotted_cows = [read.readline() for _ in range(n)]
	plain_cows = [read.readline() for _ in range(n)]


poss_positions = 0
# Iterate through every character
for i in range(m):

Solution 2 - Hashset

Implementation

Time Complexity: O(NM)\mathcal{O}(NM)

C++

#include <fstream>
#include <iostream>
#include <set>
#include <vector>


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


int main() {

Java

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


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


		int n = io.nextInt();
		int m = io.nextInt();

Python

with open("cownomics.in", "r") as read:
	n, m = map(int, read.readline().split())


	spotted_cows = [read.readline() for _ in range(n)]
	plain_cows = [read.readline() for _ in range(n)]


poss_positions = 0
for i in range(m):
	seen = set()
	for j in range(n):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum