Projects [CodeNation]

projects.cpp

/* QUESTION
 * N employees are given, you have to divide them into teams of two.
 * If n is odd the last person will form a one man team.
 * Problem is all employees are not compatible with each other and if both are compatible with each other then only a team can be formed.
 * Aij ='C' if employee i is compatible with employee j, Aij = 'X' otherwise.
 * Aii ='C' if employee i can work as one man team, Aii = 'X' otherwise.
 * find the maximum no of valid teams that can be formed. constraints: T <=20, N<=18.
 */

#include <bits/stdc++.h>

using namespace std;

const int N = 18;

int n;
char matrix[N][N];

int compatible(int mask);
int compatible_zero(int mask);
int compatible_one(int mask);

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> matrix[i][j];
		}
	}
	int max_projects = 0;
	if (n % 2 == 0) {
		for (int mask = 1; mask < (1 << n); ++mask) {
			max_projects = max(max_projects, compatible(mask));
		}
	} else {
		for (int mask = 1; mask < (1 << n); mask <<= 1) {
			max_projects = max(max_projects, compatible(mask));
		}
	}
	cout << max_projects << endl;
}

int compatible(int mask)
{
	return compatible_zero(mask) + compatible_one(mask);
}

int compatible_zero(int mask)
{
	for (int i = 0; i < n; ++i) {
		if (!(mask & (1 << i))) {
			for (int j = i + 1; j < n; ++j) {
				if (!(mask & (1 << j)) && matrix[i][j] == 'X') {
						return 0;
				}
			}
		}
	}
	return 1;
}

int compatible_one(int mask)
{
	if ((mask & (mask - 1)) == 0) {
		for (int i = 0; i < n; ++i) {
			if (mask & (1 << i)) {
				return matrix[i][i] == 'C';
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (mask & (1 << i)) {
			for (int j = i + 1; j < n; ++j) {
				if (mask & (1 << j) && matrix[i][j] == 'X') {
					return 0;
				}
			}
		}
	}
	return 1;
}