Bovine Genomics Help

Debugging Help
#1

Problem Info

2017 Open Contest Silver #2 Bovine Genomics

My Work

C++ Code

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

int location(char gene) {
  if (gene == 'A') {
    return 0;
  }
  else if (gene == 'C') {
    return 1;
  }
  else if (gene == 'G') {
    return 2;
  }
  else {
    return 3;
  }
}

int main() {
  ifstream fin("cownomics.in");
  ofstream fout("cownomics.out");

  int N, M; fin >> N >> M; 

  int spotty[4][M], plain[4][M]; // made a 2D array to keep track of the DNAs
  string cow;


  // set everything to 0 to begin with
  for (int i = 0; i < M; i++) {
    spotty[0][i] = 0;
    spotty[1][i] = 0;
    spotty[2][i] = 0;
    spotty[3][i] = 0;
    plain[0][i] = 0;
    plain[1][i] = 0;
    plain[2][i] = 0;
    plain[3][i] = 0;
  }

  for (int i = 0; i < N; i++) {
    fin >> cow;

    for (int j = 0; j < M; j++) {
      spotty[location(cow[j])][j] = 1; // if at j-th string this occurs on a spotty cow, change it to 1
    }
  }

  for (int i = 0; i < N; i++) {
    fin >> cow;

    for (int j = 0; j < M; j++) {
      plain[location(cow[j])][j] = 1;
    }
  }

  int counter = 0; // keep track of the total number of ways
  int possibility[64] = {};
  int one = 1;

  for (int i = 0; i < M; i++) { // the first location
    for (int j = 0; j < i; j++) { // the second location, we only need to search from 0 to i because order does not matter
      for (int k = 0; k < j; k++) { // the third location
        for (int p = 0; p < 64; p++) { // reset all possibilities
          possibility[p] = 0;
        }
        one = 1; // reset the single cow possibility
        
        for (int a = 0; a < 4; a++) {
          for (int b = 0; b < 4; b++) {
            for (int c = 0; c < 4; c++) {
              if (spotty[a][i] && spotty[b][j] && spotty[c][k]) { // if the three-letters occurs at each position
                possibility[16*a + 4*b + c] = 1; // assign a unique value for each combination
              }
            }
          }
        }

        for (int a = 0; a < 4; a++) {
          for (int b = 0; b < 4; b++) {
            for (int c = 0; c < 4; c++) {
              if (plain[a][i] && plain[b][j] && plain[c][k] && possibility[16*a + 4*b + c]) { // if the three-letters occurs at each position in both spotty AND plain, it cannot be used to explain
                one = 0; // false
                break; // we don't need to search anymore (technically we can break out of three loops but I don't feel like making another variable/function)
              }
            }
          }
        }
        

        if (one) {
          counter++; // if it can be explained, then add the counter by 1
        }
      }
    }
  }

  fout << counter; // write the counter to the file

  return 0;
}

The code basically completely searches every group of three. If the same code does not repeat, increment counter by 1, and do nothing if it does. At the end, write the counter value to the file.

What I’ve Tried

I tried basically everything in trying to debug and I don’t see any logic errors. This question does appear at usaco.guide, but I can’t read java which is the only language the sol provides.

Question

I cannot get the sample test case right (repeated outputting 21 while the answer is 22) after trying everything. I manually downloaded the rest of the test cases and got 8/9 on those. Can someone help me debug? Thanks.

#2

From https://forum.usaco.guide/t/how-to-ask-for-help-on-a-problem/338:

The official analysis is in C++. Why not compare the triples your solution outputs with the ones that the official solution outputs?

#3

The official C++ Solution doesn’t run on my compiler for some reason. The following error is produced:

clang++-7 -pthread -std=c++17 -o main main.cpp mine.cpp
/tmp/mine-7ce63f.o: In function `main':
mine.cpp:(.text+0x70): multiple definition of `main'
/tmp/main-057111.o:main.cpp:(.text+0x0): first defined here
clang: error: linker command failed with exit code 1 (use -v to see invocation)
exit status 1
#4

What about this?

clang++-7 -pthread -std=c++17 -o main main.cpp

If you include the names of multiple cpp files they will be concatenated together, so it’s no wonder that you’re getting an error.

#5

Ok. I fixed the code. Thanks!