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. Game Theory
  4. Deforestation
  5. Discussions

Deforestation

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 14 Discussions, By:

votes

Please Login in order to post a comment

  • cbuff
    5 years ago+ 1 comment

    cool link to understand hackenbush and colon principle

    6|
    Permalink
  • dkhos17
    3 years ago+ 1 comment

    cbuff's link and dingma129's post is really helpful, thnx^^ but if u need code:

    int gr[501];
    
    int dfs(int u, int p, vector<vector<int>>& G){
        for(auto ch : G[u]){
            if(ch != p) gr[u] ^= dfs(ch,u,G);
        }
        return u == 1 ? gr[u] : ++gr[u];
    }
    
    
    string deforestation(int n, vector<vector<int>> tree) {
        memset(gr, 0, sizeof(gr));
        vector<vector<int>> G(n+1);
        for(auto p : tree){
            G[p[0]].push_back(p[1]);
            G[p[1]].push_back(p[0]);
        }
        return dfs(1,-1,G) ? "Alice" : "Bob";
    }
    
    2|
    Permalink
  • dingma129
    4 years ago+ 0 comments

    just a useful quick note about computing the nimber for such a game:

    When played with a forest of “trees” (Colon Principle): When branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their nim sum.

    reference: http://web.mit.edu/sp.268/www/nim.pdf page 19

    2|
    Permalink
  • simha0994
    6 years ago+ 3 comments

    Can anyone explain why Alice will select 3->4? Why can't he choose 1->2 or 1->3??

    2|
    Permalink
  • anubhabaranwal21
    12 months ago+ 0 comments

    import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

    public class Solution {

    static int[] a,b;//0-index
    static int[] c;//1-index
    static int[] d;//1-index
    static int n;
    
    public static void main(String[] args) throws IOException{
        new Solution().run();
    }
    
    public static void dfscol(int root){
        d[root]=1;
        for(int i=0;i<n-1;i++){
            if(a[i]==root && d[b[i]]==0){
                dfscol(b[i]);
                c[root]++;
            }
            if(b[i]==root && d[a[i]]==0){
                b[i]=a[i]; 
                a[i]=root;
                dfscol(b[i]);
                c[root]++;
            }
        }
        return;
    }
    
    public static int dfs(int root){
        if(root > 0 && root <=n){
            if(c[root]==0) {//leaf
                return 0;
            }
            else {//c[root]>0
                int count =0;
                for(int i=0;i<n-1;i++){
                    if(a[i]==root){
                        count^=(int)(1+dfs(b[i]));
                    }
                }
                return count;
            }
        }
        return 0;
    }
    
    public void run() throws IOException{
       Scanner in = new Scanner(System.in);
       BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = in.nextInt();
        int i,u,v, counter;
        a = new int[501];
        b = new int[501];
        c = new int[501];
        d = new int[501];
    
        for(int tt =0;tt<t;tt++){
            Arrays.fill(c,0);
            Arrays.fill(d,0);
    
            n = in.nextInt();//n<=500
            counter = 0;
    
            for(i=0;i<n-1;i++){
                u = in.nextInt();//n<=500 
                v = in.nextInt();//n<=500
                a[i]=u;
                b[i]=v;
            }
    
            d[1]=1;
            dfscol(1);
    
            //dfs
            counter = dfs(1);
            //System.out.println("Node "+1+": "+counter);
            if(counter>0) log.write("Alice\n");
            else log.write("Bob\n");
        }
        log.flush();
    

    } }

    0|
    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