We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Kingdom Division
  5. Discussions

Kingdom Division

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 48 Discussions, By:

votes

Please Login in order to post a comment

  • l0gic_b0mb
    5 years ago+ 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 .
    
    52|
    Permalink
    View more Comments..
  • DelhitePKD
    5 years ago+ 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.

    34|
    Permalink
  • ShubhamAvasthi
    4 years ago+ 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;
    }
    
    14|
    Permalink
    View more Comments..
  • xinwzh
    4 years ago+ 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;
    }
    
    10|
    Permalink
  • airibo
    5 years ago+ 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).

    7|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature