HackerRank The Story of a Tree Problem Solution

HackerRank The Story of a Tree Problem Solution

Yashwant Parihar,

One day Bob drew a tree, T, with n nodes and n – 1 edges on a piece of paper. He soon discovered that parent of a node depends on the root of the tree.

Learning the fact, Bob invented an exciting new game and decided to play it with Alice. The rules of the game is described below:

  1. Bob picks a random node to be the tree’s root and keeps the identity of the chosen node a secret from Alice. Each node has an equal probability of being picked as the root.
  2. Alice then makes a list of g guesses, where each guess is in the form u v and means Alice guesses that parent(v) = u is true. It’s guaranteed that an undirected edge connecting u and v exists in the tree.
  3. For each correct guess, Alice earns one point. Alice wins the game if she earns at least k points (i.e., at least k of her guesses were true).

Alice and Bob play a games. Given the tree, Alice’s guesses, and the value of k for each game, find the probability that Alice will win the game and print it on a new line as a reduced fraction in the format p/q.
Input Format
The first line contains an integer, q, denoting the number of different games. The subsequent lines describe each game in the following format:

  1. The first line contains an integer, n, denoting the number of nodes in the tree.
  2. Then – 1 subsequent lines contain two space-separated integers, u and v, defining an undirected edge between nodes u and v.
  3. The next line contains two space-separated integers describing the respective values of g (the number of guesses) and k (the minimum score needed to win).
  4. Each of the g subsequent lines contains two space-separated integers, u and v. indicating Alice guesses parent(v) = u.

Sample Input 0

2
4
1 2
1 3
3 4
2 2
1 2
3 4
3
1 2
1 3
2 2
1 2
1 3

Sample Output 0

1/2
1/3

Explanation 0
Alice and Bob play the following g = 2 games:

  1. Alice makes two guesses, (1 2) and (3 4), meaning she guessed that parent(2) = 1 and parent (4) = 3. To win the game, at least k = 2 of her guesses must be true. In the diagrams below, you can see that at least 2 guesses are true if the root of the tree is either node 1 or 3:

There are 4 nodes in total and the probability of picking node 1 or 3 as the root is 2, which reduces to 1/2

  1. In this game, Alice only wins if node 1 is the root of the tree. There are 3 nodes in total, and the probability of picking node 1 as the root is 1/3
HackerRank The Story of a Tree Problem Solution
HackerRank The Story of a Tree Problem Solution

The Story of a Tree C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

struct s_node {
    int *child;
    int len;
    int count;
    int visit;
    int *parent;
    int size;
};

int gcd(int a, int b) {
    int tmp;
    while (b != 0) {
        tmp = b;
        b = a % b;
        a = tmp;
    }
    return (a);
}

void insert(struct s_node **tab, int u, int v) {
    int *tmp = malloc(sizeof(int) * (tab[u]->len + 1));
    if (tab[u]->len > 0)
        memcpy(tmp, tab[u]->child, sizeof(int) * tab[u]->len);
    tmp[tab[u]->len] = v;
    if (tab[u]->len > 0)
        free(tab[u]->child);
    tab[u]->child = tmp;
    (tab[u]->len)++;
    //for (int i = 0; i < tab[u]->len; i++) {
    //    printf("%d ", tab[u]->child[i]);
    //}
    //printf("\n");
}

int check_root(struct s_node **tab, int n, int **queries, int g, int k, int root, int *parent) {
    int count = 0;
 //   parent_set(tab, root, -1, parent);
    //printf("root %d\n", root);
    //for (int i = 0; i < n; i++) {
    //    printf("%d ", parent[i]);
    //}
    //printf("\n");
    for (int i = 0; i < g; i++) {
        if (parent[queries[i][1]] == queries[i][0]) {
            count++;
        }
    }
    if (count >= k)
        return (1);
    return (0);
}

int check_all(struct s_node **tab, int n, int **queries, int g, int k, int *parent) {
    //int sum = 0;
    //for (int i = 0; i < n; i++) {
    //    sum += tab[i]->visit;
    //    printf("%d\n", tab[i]->visit);
    //}
    //printf("\nsum = %d, n = %d\n", sum, n);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (tab[i]->visit && check_root(tab, n, queries, g, k, i, parent)) {
            count += tab[i]->visit;
        }
    }
    return (count);
}

int is_query(int **queries, int g, int idx) {
    for (int i = 1; i < g; i++) {
        if (queries[i][1] == idx)
            return (1);
    }
    return (0);
}

int score(struct s_node **tab, int n, int **queries, int g, int idx, int idx_parent, int *parent, int fail) {
    int sc = 0;
    //printf("node %d, visit %d, parent %d\n", idx, tab[idx]->visit, tab[idx]->parent);
    parent[idx] = fail;
    int arr[tab[idx]->len];
    for (int i = 0; i < tab[idx]->len; i++) {
        arr[i] = 0;
    }
    if (tab[idx]->visit == 1) {
        for (int i = 0; i < tab[idx]->size; i++) {
                if (tab[idx]->parent[i] == idx_parent) {
                    sc++;
                    fail -= 1;
                    parent[idx] -= 1;
                } else {
                    //parent[idx] += 1;
                    for (int j = 0; j < tab[idx]->len; j++) {
                        if (tab[idx]->child[j] == tab[idx]->parent[i]) {
                            arr[j] += 1;
                        }
                    }
                }
        }
    }
    //printf("fail = %d\n", fail);
    for (int i = 0; i < tab[idx]->len; i++) {
        if (tab[idx]->child[i] != idx_parent) {
            sc += score(tab, n, queries, g, tab[idx]->child[i], idx, parent, fail + arr[i]);
        }
    }
    return (sc);
}

void check(struct s_node **tab, int n, int **queries, int g, int k, int *parent) {
    int count = 0;
    for (int i = 0; i < g; i++) {
        tab[queries[i][1]]->visit = 1;
        int *tmp = malloc(sizeof(int) * (tab[queries[i][1]]->size + 1));
        if (tab[queries[i][1]]->size > 0)
            memcpy(tmp, tab[queries[i][1]]->parent, sizeof(int) * tab[queries[i][1]]->size);
        tmp[tab[queries[i][1]]->size] = queries[i][0];
        if (tab[queries[i][1]]->size > 0)
            free(tab[queries[i][1]]->parent);
        tab[queries[i][1]]->parent = tmp;
        tab[queries[i][1]]->size += 1;
    }
    int sc = score(tab, n, queries, g, 0, -1, parent, 0);
    //printf("score %d\n", sc);
    //for (int i = 0; i < n; i++) {
    //    printf("%d ", parent[i]);
    //}
    //printf("\n");
    for (int i = 0; i < n; i++) {
        if (sc + parent[i] >= k)
            count++;
    }
    int common = gcd(count, n);
    count /= common;
    n /= common;
    if (count == 0)
        printf("0/1\n");
    else
        printf("%d/%d\n", count, n);
}

int check_queries(struct s_node **tab, int n, int **queries, int g) {
    int u, v, found;
    for (int i = 0; i < g; i++) {
        u = queries[i][0];
        v = queries[i][1];
        found = 0;
        for (int j = 0; j < tab[u]->len; j++) {
            if (tab[u]->child[j] == v)
                found = 1;
        }
        if (!found)
            return (0);
    }
    return (1);
}

int main(){
    int q;
    struct s_node **tab;
    int *parent;
    int **queries;
    scanf("%d",&q);
    for(int a0 = 0; a0 < q; a0++){
        int n; 
        scanf("%d",&n);
        tab = malloc(sizeof(struct s_node *) * n);
        for (int i = 0; i < n; i++) {
            tab[i] = malloc(sizeof(struct s_node));
            memset(tab[i], 0, sizeof(struct s_node));
        }
        for(int a1 = 0; a1 < n-1; a1++){
            int u; 
            int v; 
            scanf("%d %d",&u,&v);
            u--;
            v--;
            //printf("insert %d %d\n", u, v);
            insert(tab, u, v);
            //printf("insert %d %d\n", v, u);
            insert(tab, v, u);
        }
        parent = malloc(sizeof(int) * n);
        memset(parent, 0, sizeof(int) * n);
        int g; 
        int k;
        scanf("%d %d",&g,&k);
        queries = malloc(sizeof(int *) * g);
        for (int i = 0; i < g; i++) {
            queries[i] = malloc(sizeof(int) * 2);
        }
        for(int a1 = 0; a1 < g; a1++){
            int u; 
            int v; 
            scanf("%d %d",&u,&v);
            u--;
            v--;
            queries[a1][0] = u;
            queries[a1][1] = v;
        }
        
        //if (check_queries(tab, n, queries, g))
            check(tab, n, queries, g, k, parent);
        //else
            //printf("0/1\n");
        
        for (int i = 0; i < n; i++) {
            free(tab[i]->child);
            free(tab[i]);
        }
        free(tab);
        free(parent);
        for (int i = 0; i < g; i ++) {
            free(queries[i]);
        }
        free(queries);
    }
    return 0;
}

The Story of a Tree C++ Solution

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <time.h>
#include <cassert>
#include <map>
#include <set>
#include <stack>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <bitset>
#include <ctype.h>

#include <complex>

//#include <unordered_map>
//#include <unordered_set>
#define ll long long
#define ullong unsigned long long int
#define pb push_back
#define mp make_pair
#define endl "\n"

#define forit(it, x) for (__typeof(x.begin()) it = x.begin(); it != x.end(); it++)

#define f first
#define s second
#define all(x) x.begin(), x.end()
#define prev qweqewqewqwe

#define pii pair <int, int>

using namespace std;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
vector<int> a[MAXN];
int LG[MAXN], RG[MAXN];
int ptr;
void dfs(int x, int p) {
    ptr++;
    LG[x] = ptr;
    for (int i = 0 ; i <a[x].size(); i++) {
        int to = a[x][i];
        if (to != p) {
            dfs(to, x);
        }
    }
    RG[x] = ptr;

}
int tree[4 * MAXN];
int p[4 * MAXN];

void build(int x, int l, int r) {
    p[x] = 0;
    if (l == r) {
        tree[x] = 0;
    } else {
        int mid = (l + r) / 2;
        build(x + x, l, mid);
        build(x+x+1, mid + 1, r);
        tree[x] = 0;
    }
}
inline void upd(int x, int l, int r) {
    tree[x] += p[x] * (r - l + 1);
    if (l != r) {
        p[x + x] += p[x];
        p[x+x+1] += p[x];
    }
    p[x] = 0;
}
void upd(int x, int l, int r, int TL, int TR, int val) {
    upd(x, l, r);
    if (r < TL || TR < l) {
        return;
    }
    if (TL <= l && r <= TR) {
        p[x] += val;
        upd(x, l, r);
    } else {
        int mid = (l + r) / 2;
        upd(x + x, l, mid, TL, TR, val);
        upd(x+x+1, mid + 1, r, TL, TR, val);
        tree[x] = tree[x + x] + tree[x + x +1];
    }
}

int ans = 0;
void calc(int x, int l, int r, int k) {
    upd(x, l, r);
    if (l == r) {
        ans += (tree[x] >= k);
    } else {
        int mid = (l + r) / 2;
        calc(x + x, l, mid, k);
        calc(x+x+1, mid + 1, r, k);
        tree[x] = 0;
    }
}
inline void solve() {
    ptr = 0;
    int n;
    scanf("%d", &n);
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        a[i].clear();
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u].pb(v);
        a[v].pb(u);
    }
    dfs(1, -1);
    int g, k;
    scanf("%d%d", &g, &k);

    for (int i = 1; i <= g; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        // parent[v] = u;
        if (LG[u] <= LG[v]) {
            upd(1, 1, n, 1, n, +1);
            upd(1, 1, n, LG[v], RG[v], -1);
        } else {
            //cerr << LG[v] << ' ' << RG[v] << '\n';
            //upd(1, 1, n, 1, n, -1);
           // cerr << u << ' ' << endl;
            upd(1, 1, n, LG[u], RG[u], +1);
        }
    }
    ans = 0;
    calc(1, 1, n, k);
    if (ans == 0) {
        printf("0/1\n");
        return;
    }
    int gcd = __gcd(ans, n);
    printf("%d/%d\n", ans / gcd, n / gcd);
    
}
int main() {
#ifdef DEBUG
    double beg = clock();
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    //ios_base::sync_with_stdio(0);cin.tie(0);
    int games;
    scanf("%d", &games);
    for (int i = 1; i <= games; i++) {
        solve();
    }
    
#ifdef DEBUG
    double end = clock();
    fprintf(stderr, "\n*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
#endif
    return 0;
}

The Story of a Tree C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{
    class Node
    {
        public int count { get; set; }
        public bool counted { get; set; }
    }

    public static string storyOfATree(int n, List<List<int>> edges, int k, List<List<int>> guesses)
    {
        var graph = new Dictionary<int, Node>[n];

        foreach (var edge in edges)
        {
            var p1 = edge[0] - 1;
            var p2 = edge[1] - 1;

            graph[p1] = graph[p1] ?? new Dictionary<int, Node>();
            graph[p2] = graph[p2] ?? new Dictionary<int, Node>();

            graph[p1].Add(p2, new Node());
            graph[p2].Add(p1, new Node());
        }

        foreach (var guess in guesses)
        {
            var parent = guess[0] - 1;
            var child = guess[1] - 1;

            graph[parent][child].count = 1;
        }

        var numberOfWins = 0;
        var visited = new int[n];

        for (int i = 0; i < n; i++)
        {
            var visitedFlas = i + 1;
            visited[i] = visitedFlas;

            int curWins = Count(graph, i, visited, visitedFlas);

            numberOfWins += curWins >= k ? 1 : 0;
        }

        return Reduce(numberOfWins, n);
    }

    private static int Count(Dictionary<int, Node>[] graph, int rootNode, int[] visited, int visitedFlag)
    {
        var count = 0;

        foreach (var node in graph[rootNode])
        {
            if (visited[node.Key] != visitedFlag)
            {
                visited[node.Key] = visitedFlag;

                if (!node.Value.counted)
                {
                    node.Value.counted = true;
                    node.Value.count += Count(graph, node.Key, visited, visitedFlag);
                }

                count += node.Value.count;
            }
        }

        return count;
    }

    public static string Reduce(int numberOfWins, int numberOfAll)
    {
        if (numberOfWins == 0) return "0/1";

        var div = 2;

        while (div <= numberOfWins)
        {
            if (numberOfWins % div == 0 && numberOfAll % div == 0)
            {
                numberOfWins /= div;
                numberOfAll /= div;
            }
            else
            {
                div++;
            }
        }

        return numberOfWins + "/" + numberOfAll;
    }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int q = Convert.ToInt32(Console.ReadLine().Trim());

        for (int qItr = 0; qItr < q; qItr++)
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());

            List<List<int>> edges = new List<List<int>>();

            for (int i = 0; i < n - 1; i++)
            {
                edges.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(edgesTemp => Convert.ToInt32(edgesTemp)).ToList());
            }

            string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

            int g = Convert.ToInt32(firstMultipleInput[0]);

            int k = Convert.ToInt32(firstMultipleInput[1]);

            List<List<int>> guesses = new List<List<int>>();

            for (int i = 0; i < g; i++)
            {
                guesses.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(guessesTemp => Convert.ToInt32(guessesTemp)).ToList());
            }

            string result = Result.storyOfATree(n, edges, k, guesses);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

The Story of a Tree Java Solution

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class Solution {
    
    static int N, K;
    static int num;
    static LinkedList<Integer>[] adj;
    static HashSet<Integer>[] outdegree;
    static HashSet<Integer>[] indegree;
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int q = input.nextInt();
        
        for (int Q = 0; Q < q; Q++) {
            N = input.nextInt();
            num = 0;
            adj = new LinkedList[N]; outdegree = new HashSet[N]; indegree = new HashSet[N];
            for (int i = 0; i < N; i++) {
                adj[i] = new LinkedList<Integer>();
                outdegree[i] = new HashSet<Integer>();
                indegree[i] = new HashSet<Integer>();
            }
            for (int i = 0; i < N - 1; i++) {
                int v = input.nextInt() - 1;
                int w = input.nextInt() - 1;
                adj[v].add(w);
                adj[w].add(v);
            }
            int g = input.nextInt();
            K = input.nextInt();
            for (int G = 0; G < g; G++) {
                int u = input.nextInt() - 1;
                int v = input.nextInt() - 1;
                indegree[u].add(v);
                outdegree[v].add(u);
            }
            
            int v = 0;
            walk(v, new boolean[N], init(v));
            int gcd = GCD(N, num);
            System.out.println((num / gcd) + "/" + (N / gcd));
        }
    }
    
    static int GCD(int a, int b) {
        if (a < b)
            return GCD(b, a);
        if (b == 0)
            return a;
        else
            return GCD(b, a % b);
    }
    
    static void walk(int v, boolean[] visited, int amount) {
        visited[v] = true;
        if (amount >= K) num++;
        for (int w : adj[v]) {
            if (!visited[w]) {
                int temp = amount;
                if (indegree[v].contains(w)) temp--;
                if (outdegree[v].contains(w)) temp++;
                walk(w, visited, temp);
            }
        }
    }
    
    static int init(int v) {
        return dfs(v, new boolean[N]);
    }
    
    static int dfs(int v, boolean[] visited) {
        visited[v] = true;
        int k = 0;
        for (int w : adj[v]) {
            if (!visited[w]) {
                k += dfs(w, visited);
                if (indegree[v].contains(w)) k++;
            }
        }
        return k;
    }
}

The Story of a Tree 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();
}

The Story of a Tree Python Solution

#!/usr/bin/env python3
from fractions import Fraction
adj = []
guess = set()
visit = []
np = []
base = 0

def rec(node, point):
    global base
    visit[node] = True
    np[node] = point
    for a in adj[node]:
        if visit[a]: continue
        positive = (node, a) in guess
        negative = (a, node) in guess
        if positive and negative:
            base = base + 1
            rec(a, point)
        elif positive:
            base = base + 1
            rec(a, point - 1)
        elif negative:
            rec(a, point + 1)
        else:
            rec(a, point)

for q in range(int(input())):
    n = int(input())
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        u, v = input().split()
        u, v = [int(u) - 1, int(v) - 1]
        adj[u].append(v)
        adj[v].append(u)

    g, k = input().split()
    g, k = [int(g), int(k)]

    guess = set()
    for i in range(g):
        u, v = input().split()
        guess.add((int(u) - 1, int(v) - 1))

    visit = [False] * n
    np = [0] * n
    base = 0
    rec(0, 0)

    count = 0
    for p in np:
        if p + base >= k:
            count = count + 1

    if count == 0:
        print("0/1")
    elif count == n:
        print("1/1")
    else:
        print(Fraction(count, n))
c C# C++ HackerRank Solutions java javascript python

Leave a Reply