URL: http://www.topcoder.com/stat?c=problem_statement&pm=6095
This problem just asks us to find the maximum number of matches in a general graph (should be a straightforward reduction given the problem constraints). The most efficient way to solve this problem is to use a maximum matching algorithm (like Edmond's). However, this is not straightforward to code and certainly not required for a 350 pointer problem. Given the constraints, one easy way to implement a maximum matching algorithm is to use dynamic programming. We will be using a bitmask to efficiently keep track of the nodes that have already been matched so far.
For those new to bitmasks, here is a very short tutorial on it. As you may know, all decimal integer numbers (base 10) have a binary representation form (base 2). As a result, each bit inside a binary representation can represent up to 1-bit of information (duh). Besides representing numbers we can use each of these bits (0 or 1) as useful book-keeping information - in our case (and in many cases) we use them to mark whether or not we have visited or used a particular resource. So for example, the bit representation 01100 could mean we have used resource 2 and 3 (0-based index). Note that we go from left to right due to the fact that the left-most bit is also the most significant bit (MSB). This bit representation (01100) is simply known as 2^3 + 2^2 = 14 in decimal. Expanding on this, let's say in our problem we have used node 1, node 4 and node 5. This is represented as 2^5 + 2^4 + 2^1 = 32 + 16 + 2 = 50. There are several important bit operations we can use to manipulate and query the bits:
For starters, to get a '1' in the n-th position from the right (remember 0-based index) - you use the shift left operator '<<'. For example, 1 << 5 yields a bit representation equivalent to 0010 0000 (32).
To set a bit, we use the bitwise-OR operator denoted as '|'. The bitwise-OR operator works by applying the OR operation to each of the corresponding bits between two numbers. The OR operation is defined as:
0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1
For example to set the 5th bit (again 0-index) from the right, we first use the shift left operator to yield the correct number (i.e. 1 << 5). Let's say the bitmask before the operation is defined as 0100 0010 (68). Then applying 1 << 5 which has a representation of 0010 0000 (32) yields:
0100 0010 (68) OR 0010 0000 (32) Equals 0110 0010 (100)
To test whether a bit is set within a bitmask, we make use of the bitwise-AND operator denoted as '&'. The AND operation is defined as:
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1
We use a similar method as we did for setting a bit in a particular position, let's say we wanted to test if the 5th bit was set. We use the shift left operator to yield the correct number (i.e. 1 << 5). Then we simply apply the bitwise-AND operator to the bitmask we wanted to test. If our mask was 0110 0010 then it would return 0010 0000. However if our mask was 0100 0010, then it would return 0000 0000 as it has no bits both turned on at the same position. Thus, we can use this to test whether or not a bitmask contains a bit in a particular position, if it the result is positive after the AND operation then it is inside the bitmask, if it's zero then it isn't inside the bitmask.
There are other bitmasking techniques which won't be discussed here as they aren't used for this problem.
Back to the problem, given that there are only 18 nodes at maximum. We can easily create a bitmask that keeps track of which nodes we have currently used up (there are 2^18 = 262144 different combinations). So for the actual DP state, we can iteratively introduce more nodes to the set and choose any adjacent nodes which haven't been used so far. Therefore, the state is D(n,m) where n is the index of which node we are processing and m is the bitmask of which nodes we have already used up. Next, we need to define the recurrence relation as well as any base cases. The recurrence relation can be found by selecting from a set of valid decisions at a particular node.
The two available options are to:
- Not used the node in the maximum matching (in hopes that it increases the available nodes later on)
- Use the node along with another node which is adjacent to it (increases the number of matchings by 1 and decreases the available set)
We define the recurrence as: D(n,m) = max { 1 + D(n+1, m | (1 << k), D(n+1, m) } where k is the set of all unused nodes which are adjacent to n. Take note, we do not consider matching node n, if it's already been matched by the time we reach index n. Then applying a simple memoization we yield a working solution:
class SeparateConnections {
public:
int howMany(vector <string>);
};
int adjmat[19][19];
int memo[19][1<<19];
int sz;
int func(int idx, int mask) {
if (idx >= sz) return 0;
if (memo[idx][mask] != -1) return memo[idx][mask];
int res = 0;
if (!(mask & (1 << idx))) {
for (int i = idx+1; i < sz; i++) {
if (mask & (1 << i)) continue;
if (!adjmat[idx][i]) continue;
res >?= 1 + func(idx+1, mask | (1 << i));
}
}
res >?= func(idx+1, mask);
return memo[idx][mask] = res;
}
int SeparateConnections::howMany(vector <string> mat) {
int res = 0;
for (int i = 0; i < mat.size(); i++) {
for (int j = 0; j < mat.size(); j++) {
if (mat[i][j] == 'Y') adjmat[i][j] = adjmat[j][i] = 1;
}
}
sz = mat.size();
memset(memo,-1,sizeof(memo));
return res = func(0,0) * 2;
}
However, one can also use a general matching algorithm like Edmond's Blossoming/Shrinking Algorithm to solve the problem. See below for such an implementation (based on Pape and Conradt variation of Edmond's which is incorrect for a certain set of inputs, but it still passed system tests for this problem). No further explanation would be provided for this algorithm as I'll leave this for a later blog entry in which we build up our matching algorithms.
#define MAX_VERTICES 21
int adjmat[MAX_VERTICES+1][MAX_VERTICES+1];
int table[MAX_VERTICES+1][MAX_VERTICES+1];
int mate[MAX_VERTICES+1];
int level[MAX_VERTICES+1];
int grandparent[MAX_VERTICES+1];
bool checkAncestor(int currentNode, int checkNode) {
int v = grandparent[currentNode];
if (v < 0) return false; // not an ancestor
if (v == checkNode) return true; // ancestor
return checkAncestor(v, checkNode);
}
int augment(int curNode) {
// BFS an augmenting path
memset(level,1,sizeof(level));
memset(grandparent,-1,sizeof(grandparent));
queue<int> q;
q.push(curNode);
level[curNode] = 0;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int y = 1; y <= MAX_VERTICES; y++) {
// not part of an edge in G or seen the odd-vertex in T
if (!adjmat[x][y] || !level[y]) continue;
if (mate[y] == 0) {
// found an augmenting path
int next = 0;
while (true) {
mate[y] = x;
next = mate[x];
mate[x] = y;
if (grandparent[x] < 0) break;
x = grandparent[x];
mate[next] = x;
y = next;
}
return 1;
} else if (mate[y] != 0 && !checkAncestor(x,y) &&
mate[y] != x) {
// push the node into the alternating tree T
q.push(mate[y]);
grandparent[mate[y]] = x;
level[y] = 0;
}
}
}
return 0;
}
int maxMatching() {
int res = 0;
memset(mate,0,sizeof(mate)); // all currently unmatched
memset(grandparent,-1,sizeof(grandparent));
// start at the vertex i if it's single
while (true) {
int v = 0;
for (int i = 1; i < MAX_VERTICES; i++) {
if (!mate[i]) v += augment(i);
}
if (v == 0) break;
res += v;
}
return res;
}
int SeparateConnections::howMany(vector <string> mat) {
for (int i = 0; i < mat.size(); i++) {
for (int j = 0; j < mat.size(); j++) {
if (mat[i][j] == 'Y') adjmat[i+1][j+1] = adjmat[j+1][i+1] = 1;
}
}
return maxMatching() * 2;
}
No comments:
Post a Comment