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.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. The Story of a Tree
  5. Discussions

The Story of a Tree

  • mln19
     + 0 comments

    There is another working solution a little different from the suggested one. The main idea is that if we choose an arbitrary root node and calculate how many parent nodes were guessed correctly, then we can choose new root as the neighbour node of the current root and the only parent-child relation which can change is between these two nodes (old and new root). Algorithm contains several steps: 1. build a graph from the input data and assign guessed parents to the nodes 3. choose an arbitrary node as a root and perform DFS, chocking how many parents were guessed correctly 4. using the same root, perform another DFS. While processing a node we check how the number of guessed parents changes if the root of the tree was one of its child nodes

    class Result {

    /*
     * Complete the 'storyOfATree' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. 2D_INTEGER_ARRAY edges
     *  3. INTEGER k
     *  4. 2D_INTEGER_ARRAY guesses
     */

    public static class Graph {
        
        public List<Node> nodes = new ArrayList<>();
        
        public List<List<Node>> adj = new ArrayList<>();
    }
    
    public static class Node {
        
        public int id;
        
        public Node parent;
        
        public Set<Node> guessedParents = new HashSet<>();
        
        public boolean visited;
    }

    public static String storyOfATree(int n, List<List<Integer>> edges, int k, List<List<Integer>> guesses) {
        int alicesWins = 0;
        Graph graph = createGraph(n, edges, k, guesses);
        Node root = graph.nodes.get(1);

        int correctParents = dfsFillParents(graph, root);
        if (correctParents >= k)
            alicesWins++;
        clearVisited(graph);
        alicesWins += dfsCheckWins(graph, root, k, correctParents);

        int gcd = gcd(n, alicesWins);
        return alicesWins/gcd + "/" + n/gcd;
    }

    public static int dfsFillParents(Graph graph, Node node) {
        int correctParents = 0;
        node.visited = true;
        for (Node adj : graph.adj.get(node.id)) {
            if (!adj.visited) {
                adj.parent = node;
                if (adj.guessedParents.contains(adj.parent)) {
                    correctParents++;
                }
                correctParents += dfsFillParents(graph, adj);
            }
        }
        return correctParents;
    }

    public static int dfsCheckWins(Graph graph, Node node, int k, int correctParents) {
        int wins = 0;
        node.visited = true;
        for (Node adj : graph.adj.get(node.id)) {
            if (!adj.visited) {
                int correction = 0;

                if (adj.guessedParents.contains(adj.parent)) {
                    correction -= 1;
                }
                if (node.guessedParents.contains(adj)) {
                    correction += 1;
                }

                correctParents += correction;
                if (correctParents >= k) {
                    wins++;
                }

                wins += dfsCheckWins(graph, adj, k, correctParents);

                correctParents -= correction;
            }
        }
        return wins;
    }

    public static Graph createGraph(int n, List<List<Integer>> edges, int k, List<List<Integer>> guesses) {
        Graph graph = new Graph();

        // nodes
        for (int i=0; i<=n; ++i) {
            Node node = new Node();
            node.id = i;
            graph.nodes.add(node);
            graph.adj.add(new ArrayList<>());
        }

        // edges
        for (List<Integer> edge : edges) {
            int n1 = edge.get(0);
            int n2 = edge.get(1);
            graph.adj.get(n1).add(graph.nodes.get(n2));
            graph.adj.get(n2).add(graph.nodes.get(n1));
        }

        // guesses
        for (List<Integer> guess : guesses) { 
            int u = guess.get(0);
            int v = guess.get(1);
            graph.nodes.get(v).guessedParents.add(graph.nodes.get(u));
        }

        return graph;
    }

    public static void clearVisited(Graph graph) {
        graph.nodes.forEach(n -> n.visited = false);
    }

    public static int gcd(int major, int minor) {
        if (minor == 0)
            return major;
        return gcd(minor, major % minor);
    }
    
    public static void print(String s) {
        System.out.println(s);
    }
}