Analysis: Breed Assignment by Fatih Gelgi

A straightforward idea is to try all possibilities using recursion. Our recursive function needs only one parameter; cow x. In the function, we assign a breed to cow x if there is no conflict with the cows previously assigned breeds, and then we recurse on cow x+1. By checking validity as we go, we prune our search early on whenever we detect a conflict, and therefore avoid searching too many irrelevant possibilities. Relationships can be stored as a matrix or a list. In matrix notation, mat[i][j] specifies if there is a relationship between cow i and j -- for instance, 'S' for same breed and 'D' for different breeds. Note that, mat[i][j] = mat[j][i] since relationships are symmetric.

The running time is technically O(K 3^N) in the worst case, since we try all possibilities (3^N) and check at most K relationships for each breed assignment for each cow. Note however that for most cases, we will be able to detect and prune away conflicts very quickly, since we break whenever we find a conflict; we therefore expect the actual running time not to be nearly as bad as the worst case above; O(3^N) is probably a more reasonable bound, since if there are no constraints we can certainly generate all possibilities. Below is some sample code:

#include <fstream>
#define MAX 16
using namespace std;

int n,breed[MAX];
char mat[MAX][MAX];

int rec(int x)
{
	if (x>n) return 1;

	int cnt=0;
	// try all breeds for cow x
	for (int i=1; i<=3; i++)
	{
		// check if there is a conflict with the breed assignments
		//		of the cows before x
		int conflict=0;
		for (int j=1; j<x; j++)
			if ((mat[x][j]=='S' && breed[j]!=i) ||
				(mat[x][j]=='D' && breed[j]==i))
			{
				conflict=1;
				break;
			}
		// assign breed i to cow x if there is no conflict
		if (!conflict)
		{
			breed[x]=i;
			cnt+=rec(x+1);
			breed[x]=0;
		}
	}

	return cnt;
}

int main()
{
	ifstream fin("assign.in");
	int k;
	fin >> n >> k;
	// read relationships into a matrix
	for (int i=0; i<k; i++)
	{
		char c;
		int x,y;
		fin >> c >> x >> y;
		mat[x][y]=c;
		mat[y][x]=c;
	}
	fin.close();

	ofstream fout("assign.out");
	fout << rec(1) << endl;
	fout.close();
}

Storing relationships in an array as a list will be slightly faster. Steven has also a nice trick that fixes the first cow's breed during the recursive search and multiplies the answer by 3. Notice that, we get same number of breed assignments when another breed is assigned to the first cow. Below is Steven's code:

#include <cstdio>

using namespace std;

const int MAXK = 55;
const int MAXN = 20;

char reltype[MAXK];
int rel1[MAXK];
int rel2[MAXK];

int assign[MAXN];

int N, K;

bool check() {
    for(int i = 0; i < K; ++i) {
	int b1 = assign[rel1[i]];
	int b2 = assign[rel2[i]];
	if (reltype[i] == 'S') {
	    if (b1 != b2) return false;
	} else {
	    if (b1 == b2) return false;
	}
    }
    return true;
}

int ans = 0;
void dfs(int cur) {
    if (cur == N + 1) {
	if (check()) {
	    ++ans;
	}
	return;
    }
    
    for(int i = 1; i <= 3; ++i) {
	assign[cur] = i;
	dfs(cur + 1);
    }
}

int main() {
    freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	
	scanf("%d %d", &N, &K);
	// store relationships into three arrays
	for(int i = 0; i < K; ++i) {
	    scanf(" %c %d %d", reltype + i, rel1 + i, rel2 + i);
	}
	
	assign[1] = 1; // symmetry; lock cow 1's breed, then multiply ans by 3.
	dfs(2);
	
	ans *= 3;
	printf("%d\n", ans);
}

Finally, it is worth noting that one can easily generate all combinations of breed assignments in a very straightforward manner without recursion by simply counting through all N-digit numbers in base 3. That is, loop over all integers x from 0 to 3^N - 1, and then take the base-3 representation of x to be one potential breed assignment.