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.
- Prepare
- Algorithms
- Game Theory
- Deforestation
- Discussions
Deforestation
Deforestation
+ 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 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 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 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 comments A straghtforward Hackenbush and Colon principle question.
Load more conversations
Sort 16 Discussions, By:
Please Login in order to post a comment