Thursday, August 27, 2009

TC SRM 447 D2 900 (ImportsList)

The problem statement can be viewed:
http://www.topcoder.com/stat?c=problem_statement&pm=10579

This problem asks us to calculate the minimum number of scripts to be used within an import list. For a given script A, it needs access to a set of scripts S1, S2, ..., Sn. The relationships are transitive, so if script A has access to script B and script B has access to script C then script A also has access to script C. We must choose a combination such that a given script has access to all its required scripts whilst also choosing the minimum number of scripts to be imported.

The first observation to make is that the graph is directed, so access does not flow both ways. In fact, given the current constraints there are no cycles in the graph hence we have a directed acyclic graph (DAG). This gives us a huge hint to topologically sort (or linearise) the graph before doing further operations. A topological sort can be achieved with a simple DFS and recording the finished nodes in reverse order. Alright let's assume we now have a linearised DAG - how do we choose the minimum amount? Recall that for an DAG we can order the vertices such that all edges go from left to right. Therefore for a vertex V, we can greedily consider vertices from left to right and keeping track of which vertices can be accessed if we access vertex W.

This works for several reasons. Let's consider two vertices: W and X. Let's say that vertex X is to the right of vertex W. If vertex X is reachable from vertex W then vertex W can access at least as much as vertex X since we can simply access vertex X from W using an arbitrary set of traversals. Let's say that vertex X is not reachable from vertex W, then there could be some scripts which we can access between vertex W and X which we need to fulfill the requirements. If there isn't, then we can simply not use vertex W and we will consider vertex X eventually. Therefore, the optimality follows through the linearised order since we consider the largest set and choosing so does not cause conflicts later on.

A very simple way to represent what is accessible from a given vertex is to use a bitmask. Then the implementation is as follows:


class ImportsList {
public:
vector <int> importsCount(vector <string>);
};

#define N 52
int visited[N];
int order[N];
int cycleDetect;
int adjmat[N][N];
int dfsIdx;

void dfs(int node) {
if (visited[node]) { if (visited[node] == 1) cycleDetect = 1; return; }
visited[node] = 1;
for (int i = 0; i < N; i++) {
if (adjmat[node][i]) {
dfs(i);
}
}
visited[node] = 2;
order[dfsIdx] = node;
dfsIdx--;
}

long long mask[N];
long long procMask[N];

vector <int> ImportsList::importsCount(vector <string> requires) {
vector<int> res(requires.size(),0);
for (int i = 0; i < requires.size(); i++) {
long long m = 0;
for (int j = 0; j < requires.size(); j++) {
if (requires[i][j] == 'Y') { adjmat[i][j] = 1; m += (1LL << j); }
}
mask[i] = m;
}
dfsIdx = requires.size()-1;
for (int i = 0; i < requires.size(); i++) {
if (!visited[i]) {
dfs(i);
}
}
// greedy based on topological sorting
for (int i = requires.size()-1; i >= 0; i--) {
long long m = mask[order[i]];
long long p = m;
int num = 0;
for (int j = i+1; j < requires.size() && m != 0; j++) {
if (adjmat[order[i]][order[j]] && (m & (1LL << order[j]))) {
num++;
p |= procMask[order[j]];
m = m & ~(procMask[orderj]]);
}
}
procMask[order[i]] = p;
res[order[i]] = num;
}
return res;
}

No comments:

Post a Comment