114B – PFAST Inc.

A brute-force problem with some bit-wise tricks.
You have a list of names. Some of them don’t get along. Find the largest sought team. Make sure your output is sorted!
The basic idea is that you generate all possible teams and exclude the ones that have “bad combinations”. All of this is done bit-wise. As you see, the maximum team has 16 members so each combination can be represented by an integer. Each set bit of that integer indicates that a certain member is a part of that team. An example:

	n = 3;
	names = {"x", "y", "z"}
	team = 5	// 510 = 1012 which means "x", "z" are in the team

So, we need:

• An array (names) that holds all the names. This array must be sorted for the output to be easy.
• A hash map (nameToInt) that maps each name to an integer for simplicity’s sake. Bit-wise tweaks are now easier.
• An integer array (forbidden) that holds forbidden combinations.
• A method (nSetBits(i)) that counts the number of set bits in an integer / the number of members in a team.
• Read the names, sort them, give each one a representative integer, read forbidden combinations and store them, generate all possible combinations, exclude the bad ones and maximize the number of members.

C++ implementation:

#include <algorithm>
#include <iostream>
#include <string>
#include <map>
using namespace std;

#define N (16 + 1)
#define L (10 + 1)

map<string, int> nameToInt;
string names[N];
int n, m, forbidden[N * N], bestTeam;
string name;

int nSetBits(int i) {
	i = i - ((i >> 1) & 0x55555555);
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
	return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
	int i, j;
	cin >> n >> m;
	// names sort & map
	for (i = 0; i < n; names[i] = name, ++i)
		cin >> name;
	sort(names, names + n);
	for (i = 0; i < n; ++i)
		nameToInt[names[i]] = i;
	// forbidden teams
	for (i = 0; i < m; ++i) {
		forbidden[i] = 0;
		cin >> name;
		forbidden[i] |= 1 << nameToInt[name];
		cin >> name;
		forbidden[i] |= 1 << nameToInt[name];
	}
	// genearate all possible and maximize
	for (int i = (1 << n) - 1; i > 0; --i) {
		for (j = 0; j < m; ++j)
			if ((forbidden[j] & i) == forbidden[j])
				break;
		if (j == m && nSetBits(bestTeam) < nSetBits(i))
			bestTeam = i;
	}
	// print
	cout << nSetBits(bestTeam) << endl;
	for (i = 0; i < n; ++i)
		if (bestTeam & (1 << i))
			cout << names[i] << endl;
	return 0;
}