Sort by

recency

|

67 Discussions

|

8 months ago+ 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);
    }
}

8 months ago+ 0 comments

My JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function storyOfATree(n, edges, k, guesses) {
    const nodes = Array(n);
    for (let i = 0; i < n; i++) {
        nodes[i] = {
            neighbors: [],
        };
    }
    edges.forEach((e) => {
        nodes[e[0] - 1].neighbors.push(e[1] - 1);
        nodes[e[1] - 1].neighbors.push(e[0] - 1);
    });
    buildTree(nodes, 0);
    const guessMap = Array(n);
    for (let i = 0; i < n; i++) {
        guessMap[i] = [];
    }
    guesses.forEach((guess) => {
        guessMap[guess[1] - 1].push(guess[0] - 1);
    });
    countMatch(nodes, guessMap, 0);
    let p = 0;
    const queue = [0];
    while (queue.length > 0) {
        const i = queue.shift();
        const node = nodes[i];
        let c = node.count;

        if (node.parent !== undefined) {
            const parent = nodes[node.parent];
            c = parent.count;
            if (guessMap[i].indexOf(node.parent) >= 0) {
                c--;
            }
            if (guessMap[node.parent].indexOf(i) >= 0) {
                c++;
            }
        }
        node.count = c;
        if (c >= k) {
            p++;
        }
        node.children.forEach((j) => queue.push(j));
    }

    let q = n;
    let g = gcd(p, q);
    p = p / g;
    q = q / g;
    return `${p}/${q}`;
}

function gcd(a, b) {
    while (b !== 0) {
        const mod = a % b;
        a = b;
        b = mod;
    }
    return a;
}

function buildTree(nodes, idx) {
    const root = nodes[idx];
    root.children = [];
    root.neighbors.forEach((i) => {
        if (root.parent !== i) {
            nodes[i].parent = idx;
            root.children.push(i);
            buildTree(nodes, i);
        }
    });
}

function countMatch(nodes, guessMap, idx) {
    const root = nodes[idx];
    let count = 0;
    root.children.forEach((i) => {
        if (guessMap[i].indexOf(idx) >= 0) {
            count++;
        }
        count += countMatch(nodes, guessMap, i);
    });
    root.count = count;
    return count;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const q = parseInt(readLine(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const n = parseInt(readLine(), 10);
        let edges = Array(n - 1);

        for (let edgesRowItr = 0; edgesRowItr < n - 1; edgesRowItr++) {
            edges[edgesRowItr] = readLine().split(' ').map(edgesTemp => parseInt(edgesTemp, 10));
        }

        const gk = readLine().split(' ');

        const g = parseInt(gk[0], 10);

        const k = parseInt(gk[1], 10);

        let guesses = Array(g);

        for (let guessesRowItr = 0; guessesRowItr < g; guessesRowItr++) {
            guesses[guessesRowItr] = readLine().split(' ').map(guessesTemp => parseInt(guessesTemp, 10));
        }

        let result = storyOfATree(n, edges, k, guesses);

        ws.write(result + "\n");
    }

    ws.end();
}

10 months ago+ 0 comments

There are errors in the main function.Took a long time to debug this not realising there was an error in the way the inputs are taken. Replace the line:vector> guesses(q); with vector> guesses(g);. This should fix the error

1 year ago+ 0 comments

Hint:

The first thing to do is tranversing the tree to imagine how the tree is. Next, we notice that in the tree we've created above:

if u - v guess is correct. It means u is parent[v]. That guess is also correct for all nodes (except v's children as it will make the tree reverse)
if u - v guess is incorrect. It means v is parent[u]. That guess is only correct when root is u or u's children => To count how many win cases, i suggest to use dfs to reuse the number of win cases of parent nodes

1 year ago+ 0 comments

Guys, write a custom main function. The one given have some issues. as pointed out in earlier answer, the loop to read in guesses has a logical error. Personally this didn't fix my problem much so I simply wrote a new main function and it works.

In c++,

int main()
{
    int t;cin>>t;
    for(int i=0; i<t; i++){
        int n;cin>>n;
        vector<vector<int>> edges(n-1);
        for(int j=0, p, q;j<n-1;j++){
            cin >>p >> q;
            edges[j].push_back(p);
            edges[j].push_back(q);
        }
        int g,k;
        cin >>g>>k;
        vector<vector<int>> guesses(g);
        for(int j=0,p,q; j<g; j++){    
            cin >>p>>q;
            guesses[j].push_back(p);
            guesses[j].push_back(q);            
        }
        cout << storyOfATree(n, edges, k, guesses) << endl;
    }
}

Iam starting to hate this website. This took a lot of my time!!

Sort by

|

67 Discussions

|

Hint:

Cookie support is required to access HackerRank