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

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Deforestation
  5. Discussions

Deforestation

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 16 Discussions, By:

recency

Please Login in order to post a comment

  • thecodingsoluti2
    10 months ago+ 0 comments

    Here is Deforestation problem solution in Python Java C++ and c programming - https://programs.programmingoneonone.com/2021/07/hackerrank-deforestation-problem-solution.html

    0|
    Permalink
  • cafelatte
    11 months ago+ 0 comments

    Just another Python solution:

    from functools import reduce
    from operator import xor
    
    def deforestation(n, tree):
        root = build_tree(n,tree)
        return 'Alice' if grundy(root) else 'Bob'
    
    def build_tree(n,edges):
        neighbours = [set() for _ in range(n+1)]
        for u,v in edges:
            neighbours[u].add(v)
            neighbours[v].add(u)
        def get_branch(parent,me):
            return [get_branch(me,c) for c in neighbours[me] if c !=parent]
        return [get_branch(1,c) for c in neighbours[1]]
        
    def grundy(family):
        return reduce(xor, (1+grundy(branch) for branch in family),0) 
    
    0|
    Permalink
  • anubhabaranwal21
    2 years 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
  • shehanjayalath
    3 years ago+ 0 comments

    Haskell Solution

    module Main where
    
    import qualified Data.Vector.Mutable as M
    import qualified Data.Vector as V
    import Data.Bits
    import Control.Monad.ST
    import Data.List
    
    main :: IO ()
    main = do
      t <- fmap read getLine :: IO Int
      sequence_ (replicate t run)
      where
        run = do
          n <- fmap read getLine :: IO Int
          pairs <- sequence . replicate (n - 1) $ fmap (map read . words) getLine :: IO [[Int]]
          putStrLn (calc (getEdges n pairs))
        getEdges n pairs = runST $ do
          e <- M.replicate (n + 1) []
          sequence_ [f e u v | [u, v] <- pairs]
          V.freeze e
          where
            f e u v = do
              M.modify e (u:) v
              M.modify e (v:) u
    
    calc :: V.Vector [Int] -> String
    calc e = if f 0 1 == 0 then "Bob" else "Alice"
      where
        f :: Int -> Int -> Int
        f w u = foldl' xor 0 [1 + f u v | v <- e V.! u, v /= w]
    
    0|
    Permalink
  • SaurabhS_1206
    3 years ago+ 0 comments

    A straghtforward Hackenbush and Colon principle question.

    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