Kingdom Division
Kingdom Division
+ 10 comments You may try the following approach if you didn't get the editorial. Observe that if you know that answers (valid combinations) for the children of a node, you can calculate the answer for that node from the answers of it's children. - This can be done as following: Suppose a node has N children. If the child C1 is given color red (0), suppose number of valid combinations for that configuration (with child C1 as red) are C1r. If the child C1 is given color black (1), suppose number of valid combinations for that configuration (with child C1 as black) are C1b. Similarly the answer for ith child with color as red is Cir and with color as black is Cib. Then the answer for that parent node should be (C1r+C1b)*(C2r+C2b)*.........(CNr+CNb). This may seem right at the first glance but it's not always true, as we MAY have also added some invalid combinations while we calculated our answer for the parent node. What are these invalid combinations? Suppose the parent has color black, then we've also added the combinations in our answer for the parent node where C1 is red, C2 is red,.... CN is red, which are (C1r*C2r*C3r....CNr). BUT POINT 1 - These combinations are only invalid, if the parent's color is black and the color of parent's parent is red (as these combinations clearly leaves the parent(black) with no other black nodes directly connected to it, which are indeed invalid as the children with red color can then attack it's parent with black color) POINT 2 - Same combinations are valid, if the parent's color is black and the color of parent's parent is also black. So we have to maintain two things. What's the color of current node? Is the color of current node's parent same as the color of current node (which I've done as 2, if true, and 1 if false in my code)? So, if the color of node and node's parent are same, then don't subtract the 'potential' invalid combinations, else subtract them. Recursively calculate answer for each node using DFS. Memoise for 10^5. You may check out the this code https://pastebin.com/k1bs4uRQ .
+ 0 comments Problem tester's code is legendary. I bet, two nights after writing it, even he was not able to decode whatever he wrote.
Great work Hackerrank. The hell you guys even add code in the editorial if its unreadable.
+ 6 comments I believe the following code is much easier to understand than the editorial:-
enum{safe,unsafe}; vector<vector<long>> M,dp; vector<bool> vis; #define h 1000000007 void dfs(int x) { vis[x]=1; long sf=1,usf=1; for(auto y:M[x]) { if(vis[y]) continue; dfs(y); usf*=dp[y][safe],usf%=h; sf*=dp[y][safe]+dp[y][safe]+dp[y][unsafe],sf%=h; } sf-=usf,sf+=h,sf%=h; dp[x][safe]=sf; dp[x][unsafe]=usf; } // Complete the kingdomDivision function below. int kingdomDivision(int n, vector<vector<int>> roads) { M.clear(); M.resize(n); dp.clear(); dp.resize(n,vector<long>(2)); vis.clear(); vis.resize(n); for(auto x:roads) { x[0]--,x[1]--; M[x[0]].push_back(x[1]); M[x[1]].push_back(x[0]); } dfs(0); for(auto &x:dp) { for(auto &y:x) cerr<<y<<' '; cerr<<'\n'; } return (2*dp[0][safe])%h; }
+ 3 comments /* Idea: since it's a DP problem, see if we can build the configurations of a node based on its children. Answer is yes. For any node, there are two cases which are helpful to build the solution for its parent: (1) the node's subtree is a good configuration, excluding its parent; (2) the node's subtree is a nearly good configuration, it's good when its parent is included, i.e. the direct children of the node all have the same color, which is the opposite of the node (itself is bad, rest is good); when the parent of this node has the same color, the node becomes good, therefore, this nearly good configuration becomes good. So we need to save above two numbers for each node. Denote G1r to be the number of good configurations for node 1 when it is red, i.e. (1); Denote B1r to be the number of nearly good configurations for node 1 when it is red, i.e. (2); Obviouse by symmetry: G1r = G1b, B1r = B1b. Let's look at an example, we have 3 nodes: 1, 2, 3, 1 is head and the parent of 2 and 3. B1r = G2b * G3b: 1 is red, 2 and 3 are blue, this is by definition from (2) What's G1r then? Since for node 2 and 3, each has 4 numbers, let's do first attempt by naive multiplication rule: Version 1: G1r = (G2b + G2r + B2r + B2b) * (G3b + G3r + B3r + B3b) We realize: given 1 is red, B2b should be removed, because 1 being red doesn't save 2 from being a bad node, so does B3b, which gives: Version 2: G1r = (G2b + G2r + B2r) * (G3b + G3r + B3r) We then realize: G2b and G3b can not happen at the same time, otherwise 1 is connected to two blue nodes, making 1 a bad node Therefore, we have Version 3: G1r = (G2b + G2r + B2r) * (G3b + G3r + B3r) - G2b * G3b, which is the correct one. In the c++ code: G stands for Gnr/Gnb, B stands for Bnr/Bnb; */ const long MOD = long(1e9+7); struct Node { int a{0}; bool visited{false}; unordered_set<Node*> connected; Node(int m) : a(m) { } }; class Graph { private: vector<Node> nodes; public: Graph(int n) { for (int i=1; i<=n; i++) { nodes.push_back(Node(i)); } } void add_edge(int u, int v) { nodes[u-1].connected.insert(&nodes[v-1]); nodes[v-1].connected.insert(&nodes[u-1]); } long count(); void solve(Node *n, vector<long long> &G, vector<long long> &B, vector<int> &P); // ATTN: long long instead of long void set_parents(Node *n, vector<int> &P); void set_visited_all(bool b) { for (auto &n : nodes) n.visited = b; } }; void Graph::set_parents(Node *node, vector<int> &P) { node->visited = true; for (auto n : node->connected) { if (n->visited) continue; P[n->a] = node->a; if (n->connected.size() > 1) set_parents(n, P); } } void Graph::solve(Node *node, vector<long long> &G, vector<long long> &B, vector<int> &P) { node->visited = true; if (P[node->a] && node->connected.size() == 1) { // ATTN: leaf node, be careful when head has only one child B[node->a] = 1; G[node->a] = 0; return; } for (auto n : node->connected) { if (n->visited) continue; if (G[n->a] == -1) solve(n, G, B, P); } B[node->a] = 1; G[node->a] = 1; for (auto n : node->connected) { if (n->a == P[node->a]) // skip parent continue; B[node->a] *= G[n->a]%MOD; // ATTN: do MOD as we go G[node->a] *= (2*G[n->a]+B[n->a])%MOD; B[node->a] %= MOD; G[node->a] %= MOD; } G[node->a] -= B[node->a]; while (G[node->a] < 0) // ATTN: be careful when G < B G[node->a] += MOD; } long Graph::count() { size_t n = nodes.size(); vector<long long> G(n+1,-1), B(n+1, -1); vector<int> P(n+1,0); int a = rand() % n; a = 0; set_parents(&nodes[a], P); set_visited_all(false); solve(&nodes[a], G, B, P); return 2*G[a+1] % MOD; }
+ 1 comment Suggessions for guys who understand and know the recurrent formulation but still could not get accepted for all test cases. 1) Don't use recursion: Your code may get crushed because of stack overflow and why use it when we have non-recursion solution. 2) Avoid using division: In your optimized recurrent formula(dp formula) you may come up with divisions. So avoid using them (don't optimize too much). Because after each operation we take modulo by 10^9+7. Modulo is not invariant to division operation. In other words modulo DOES give a sh.t to division operation.
Now I will explain how we can avoid using recursion. Use BFS to build the tree. Usually one uses queue to store the traversing order in BFS. This queue is the key here to avoid recursion. Just traverse the queue in inverse order and it guarantees that you encounter all child nodes before their parent node. So when you encounter a node from that queue, you already have solution for child nodes (you already have encountered child nodes before).
Sort 48 Discussions, By:
Please Login in order to post a comment