https://community.topcoder.com/stat?c=problem_statement&pm=10579
https://apps.topcoder.com/forums/?module=Thread&threadID=671561&start=0
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
https://apps.topcoder.com/forums/?module=Thread&threadID=671561&start=0
The basic observation required is that if A needs access to B, and B needs access to C, then there is no need for A to import C since it will automatically get access via B. Thus, the modules that A must import are those it needs access to, minus those it will get access to through its dependencies.
public class ImportsList { public int[] importsCount(String[] requires) { int N = requires.length; long[] reqMasks = new long[N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (requires[i].charAt(j) == 'Y') reqMasks[i] |= 1 << j; int[] ans = new int[N]; for (int i = 0; i < N; i++) { long impMask = reqMasks[i]; for (int j = 0; j < N; j++) if ((reqMasks[i] & (1 << j)) != 0) impMask &= ~reqMasks[j]; ans[i] = Long.bitCount(impMask); } return ans; } }
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.
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.
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;
}
