HackerRank Roads in HackerLand Solution

In this post, we will solve HackerRank Roads in HackerLand Problem Solution.

John lives in HackerLand, a country with N cities and M bidirectional roads. Each of the roads has a distinct length, and each length is a power of two (l.e.. 2 raised to some exponent). It’s possible for John to reach any city from any other city. Given a map of HackerLand, can you help John determine the sum of the minimum distances between each pair of cities? Print your answer in binary representation.
Input Format
The first line contains two space-seperated integers denoting N (the number of cities) and M (the number of roads), respectively.
Each line i of the M subsequent lines contains the respective values of A, B, and C, as three space-separated integers. These values define a bidirectional road between cities A, and B, having length 2Ci

Output Format

Find the sum of minimum distances of each pair of cities and print the answer in binary representation.

Sample Input

Sample Output

Table of Contents

Roads in HackerLand C Solution

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

typedef struct _node{
    int vertex;
    int weight;
    struct _node * next;
}node;

typedef node * pnode;

pnode AL[200005];
int hsh[100005];
long long int ans[200105];

void insert(pnode *A,int v,int w){
    pnode p=(pnode)malloc(sizeof(node));
    p->vertex=v;
    p->weight=w;
    p->next=*A;
    *A=p;
    return;
}

int find(int i){
    if(hsh[i]==i)return i;
    hsh[i]=find(hsh[i]);
    return hsh[i];
}

int check(int i,int j){
    int hi=find(i),hj=find(j);
    if(hi==hj)return 0;
    if(hj<hi)hsh[hi]=hj;
    else hsh[hj]=hi;
    return 1;
}

int dfs(int i,int pre,int n){
    pnode p=AL[i];
    int count=1;
    int temp;
    while(p!=NULL){
        if(p->vertex!=pre){
            temp=dfs(p->vertex,i,n);
            ans[p->weight]=(long long int)(n-temp)*(long long int)temp;
            count+=temp;
        }
        p=p->next;
    }
    return count;
}

int main() {
    int n,m,edge[200005][2],i,j,k,u,v,w,mx;
    long long int longj;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&w);
        edge[w][0]=u-1;
        edge[w][1]=v-1;
    }
    for(i=0;i<n;i++)hsh[i]=i;
    for(i=0;i<n;i++)AL[i]=NULL;
    for(i=j=0;i<m&&j<n-1;i++){
        if(check(edge[i][0],edge[i][1])){
            insert(&AL[edge[i][0]],edge[i][1],i);
            insert(&AL[edge[i][1]],edge[i][0],i);
            j++;
        }
    }
    k=dfs(0,-1,n);
    mx=m;
    for(i=0;i<mx;i++){
        longj=ans[i];
        ans[i]=0;
        k=0;
        while(longj>0){
            ans[i+k]+=longj%2;
            k++;
            longj/=2;
            if(mx<i+k)mx=i+k;
        }
    }
    i=mx;
    while(i>0&&ans[i]==0)i--;
    for(;i>=0;i--)printf("%lld",ans[i]);
    return 0;
}

Roads in HackerLand C++ Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctype.h>
#include <deque>
#include <queue>
#include <cstring>
#include <set>
#include <list>
#include <map>
#include <random>
#include <unordered_map>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<bool> vb;
typedef std::vector<string> vs;
typedef std::vector<double> vd;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<int> > vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef std::vector<std::pair<int, int> > vpi;
typedef vector<vpi> vvpi;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;

const long long mod = 1000000007;

#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define forn(i, a, b) for(int i = a; i < b; i++)

#define pb push_back
#define mp make_pair
const int MAXN = 100000;
vector<int> lst[MAXN];
int parent[MAXN];

void make_set (int v) {
    lst[v] = vector<int> (1, v);
    parent[v] = v;
}

int find_set (int v) {
    return parent[v];
}

void union_sets (int a, int b) {
    a = find_set (a);
    b = find_set (b);
    if (a != b) {
        if (lst[a].size() < lst[b].size())
            swap (a, b);
        while (!lst[b].empty()) {
            int v = lst[b].back();
            lst[b].pop_back();
            parent[v] = a;
            lst[a].push_back (v);
        }
        
    }
}

vvpi nb;
vi ans(200100, 0);
vi used;
int n,m;
int dfs(int v) {
    used[v] = 1;
    int ssz = 1;
    for(auto u : nb[v]) {
        if(used[u.first]) continue;
        
        ll st = dfs(u.first);
        ssz+=st;
        
        ll r = st * (n-st);
        int cur = u.second;
        while(r>0) {
            if(r%2) ans[cur]++;
            r/=2;
            if(ans[cur] == 2) {
                ans[cur]=0;
                r++;
            }
            cur++;
        }
        
    }
    return ssz;
}

int main()
{
    vector<pair<int, pi>> e;
    scanf("%d %d", &n,&m);
    forn(i,0,m) {
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
        e.pb(mp(c, mp(a-1, b-1)));
    }
    nb.resize(n);
    forn(i,0,n) make_set(i);
    sort(all(e));
    
    for(auto u : e) {
        int a = u.second.first;
        int b = u.second.second;
        int x = find_set(a);
        int y = find_set(b);
        if(x==y) continue;
        int c = u.first;
        nb[a].pb(mp(b, c));
        nb[b].pb(mp(a, c));
        union_sets(a, b);

    }
    used=vi(n,0);
    dfs(0);
    while(ans.back()==0) ans.pop_back();
    reverse(all(ans));
    for(auto x:ans) printf("%d", x);
    
}

Roads in HackerLand C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    /*
     * Complete the roadsInHackerland function below.
     */
    static string roadsInHackerland(int n, int[][] roads) {
        var dset = new int[n];
        var adj = new int[n][];
        var dist = new int[n][];
        for(int i = 0; i < dset.Length; i++)
            dset[i] = i;
        Array.Sort(roads, (r1, r2) => r1[2] - r2[2]);
        foreach(var r in roads) {
            int v1 = r[0] - 1;
            int v2 = r[1] - 1;
            int p1 = find(dset, v1);
            int p2 = find(dset, v2);
            if(p1 != p2) {
                dset[p2] = p1;
                append(ref adj[v1], v2);
                append(ref adj[v2], v1);
                append(ref dist[v1], r[2]);
                append(ref dist[v2], r[2]);
            }
        }
        var total = new List<long>();
        dfs(total, 0, -1, adj, dist);
        int pos = 0;
        while(pos < total.Count) {
            long t = total[pos]/2;
            total[pos] %= 2;
            add(total, pos + 1, t);
            pos++;
        }
        total.Reverse();
        return string.Join("", total);
    }

    static int dfs(List<long> total, int curr, int parent, int[][] adj, int[][] dist) {
        int cTotal = 1;
        for(int i = 0; i < adj[curr].Length; i++)
            if(adj[curr][i] != parent) {
                int cnt = dfs(total, adj[curr][i], curr, adj, dist);
                cTotal += cnt;
                add(total, dist[curr][i], cnt*(adj.Length - (long)cnt));
            }
        return cTotal;
    }
    
    static void add(List<long> sum, int pow, long cnt) {
        if(cnt > 0) {
            while(sum.Count <= pow)
                sum.Add(0);
            sum[pow] += cnt;
        }
    }
    
    static int find(int[] dset, int v) {
        while(dset[v] != v) {
            var next = dset[v];
            dset[v] = dset[next];
            v = next;
        }
        return v;
    }
    
    static void append(ref int[] arr, int v) {
        Array.Resize(ref arr, (arr?.Length ?? 0) + 1);
        arr[arr.Length - 1] = v;
    }
    
    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

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

        int n = Convert.ToInt32(nm[0]);

        int m = Convert.ToInt32(nm[1]);

        int[][] roads = new int[m][];

        for (int roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {
            roads[roadsRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), roadsTemp => Convert.ToInt32(roadsTemp));
        }

        string result = roadsInHackerland(n, roads);

        textWriter.WriteLine(result);

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

Roads in HackerLand Java Solution

import java.io.*;
import java.util.*;

public class Solution {
  public static class Edge {
    public int node1, node2, power;
    long count;

    public Edge(int node1, int node2, int power) {
      this.node1 = node1;
      this.node2 = node2;
      this.power = power;
    }
  }

  public static class Node {
    public int id;

    public ArrayList<Edge> edges;

    public Node(int id) {
      this.id = id;
      edges = new ArrayList<>();
    }
  }

  static long[] results;
  static int N, M;
  static Node[] nodes;

  // disjoint set implementation
  static int[] forests;

  static int find(int node) {
    if (forests[node] < 0) return node;
    return forests[node] = find(forests[node]);
  }

  static void join(int root1, int root2) {
    if (forests[root2] < forests[root1]) forests[root1] = root2;
    else {
      if (forests[root1] == forests[root2]) forests[root1]--;
      forests[root2] = root1;
    }
  }

  // count edge uses
  static int descend(Node parent, Node node) {
    int total = 1;

    for (Edge edge : node.edges) {
      if (parent != null && (edge.node1 == parent.id || edge.node2 == parent.id)) continue;

      Node target;

      if (edge.node1 == node.id) target = nodes[edge.node2];
      else target = nodes[edge.node1];

      edge.count = descend(node, target);

      total += edge.count;
    }

    return total;
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    N = scanner.nextInt();
    M = scanner.nextInt();

    Edge[] edges = new Edge[M];

    results = new long[2 * M];

    nodes = new Node[N];
    for (int n = 0; n < N; n++) nodes[n] = new Node(n);

    for (int m = 0; m < M; m++) {
      int node1 = scanner.nextInt() - 1;
      int node2 = scanner.nextInt() - 1;
      int power = scanner.nextInt();
      edges[power] = new Edge(node1, node2, power);
    }

    ArrayList<Edge> bucket = new ArrayList<>();

    // build MST
    forests = new int[N];
    Arrays.fill(forests, -1);

    for (int m = 0; m < M; m++) {
      int n1 = edges[m].node1, n2 = edges[m].node2;
      if (find(n1) != find(n2)) {
        join(find(n1), find(n2));

        nodes[n1].edges.add(edges[m]);
        nodes[n2].edges.add(edges[m]);

        bucket.add(edges[m]);
      }
    }

    // calculate distances
    Node root = nodes[bucket.get(0).node1];

    descend(null, root);

    for (Edge edge : bucket) results[edge.power] = edge.count * (N - edge.count);

    // binary output
    long carry;
    long nm;

    long[] buffer = new long[2 * M];

    for (int i = 0; i < 2 * M; i++) {
      nm = results[i];
      int j = 0;
      while (nm != 0) {
        buffer[i + j] += nm % 2;
        nm /= 2;
        j++;
      }
    }

    carry = 0;
    Arrays.fill(results, 0);
    for (int i = 0; i < 2 * M; i++) {
      results[i] = (buffer[i] + carry) % 2;
      carry = (buffer[i] + carry) / 2;
    }

    boolean init = false;
    for (int i = 2 * M - 1; i >= 0; i--) {
      if (results[i] == 0 && init) System.out.print(0);
      else if (results[i] == 1) {
        System.out.print(1);
        init = true;
      }
    }
  }
}

Roads in HackerLand 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 roadsInHackerland(n, roads) {
    function calculateMST(roads) {
        function getRootArr(roads) {
            let rootArr = [], rootCountArr = [];
            for (let i = 1; i <= n; i++) {
                rootArr[i] = i;
                rootCountArr[i] = 1;
            }

            return [rootArr, rootCountArr];
        }

        function getRoot(rootArr, node) {
            while (node !== rootArr[node])
                node = rootArr[node];

            return node;
        }

        function setRoot(rootArr, node, root) {
            rootArr[node] = root;
        }

        let finalRoads = [], rootArr = getRootArr(roads)[0], rootCountArr = getRootArr(roads)[1];
        roads.sort((r1, r2) => r1[2] - r2[2]);
        for (let road of roads) {
            if (1 + finalRoads.length === n)
                break;

            let root0 = getRoot(rootArr, road[0]), root1 = getRoot(rootArr, road[1]);
            if (root0 !== root1) {
                finalRoads.push(road);
                if (rootCountArr[root1] < rootCountArr[root0]) {
                    setRoot(rootArr, root1, root0);
                    rootCountArr[root0] += rootCountArr[root1];
                }
                else {
                    setRoot(rootArr, root0, root1);
                    rootCountArr[root1] += rootCountArr[root0];
                }
            }
        }

        return finalRoads;
    }

    function calculateEdge2Count(mst) {
        function constructMstMap(mst) {
            function addToMap(map, node, nodeAndWeight) {
                let nodeAndWeightArr;
                if (map.has(node))
                    nodeAndWeightArr = map.get(node);
                else {
                    nodeAndWeightArr = [];
                    map.set(node, nodeAndWeightArr);
                }

                nodeAndWeightArr.push(nodeAndWeight);
            }

            let node2NodeWeight = new Map();
            for (let road of mst) {
                let node0 = road[0], node1 = road[1];
                addToMap(node2NodeWeight, node0, [node1, road[2]]);
                addToMap(node2NodeWeight, node1, [node0, road[2]])
            }

            return node2NodeWeight;
        }

        function dfs(node, edge2Count, visited) {
            let edges = node2NodeWeight.get(node).filter(nodeAndWeight => !visited.has(nodeAndWeight[0]));
            if (edges.length === 0)
                return 0;

            let childrenCount = 0;
            for (let road of edges) {
                let theOtherNode = road[0];
                visited.add(theOtherNode);
                let roadCount = dfs(theOtherNode, edge2Count, visited);
                roadCount++;   // count theOtherNode itself
                edge2Count.set(road, roadCount);
                childrenCount += roadCount;
            }

            return childrenCount;
        }

        let node = mst[0][0], edge2Count = new Map(), visited = new Set();
        visited.add(node);
        let node2NodeWeight = constructMstMap(mst);
        dfs(node, edge2Count, visited);

        return edge2Count;
    }

    let mst = calculateMST(roads), edge2Count = calculateEdge2Count(mst);
    const NODE_COUNT = mst.length + 1;
    let total = 0n;
    for (let kv of edge2Count) {
        let weight = kv[0][1], count = kv[1], times = count * (NODE_COUNT - count);
        total += (2n ** BigInt(weight)) * BigInt(times);
    }

    return total.toString(2);
}

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

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

    const n = parseInt(nm[0], 10);

    const m = parseInt(nm[1], 10);

    let roads = Array(m);

    for (let roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {
        roads[roadsRowItr] = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
    }

    let result = roadsInHackerland(n, roads);

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

    ws.end();
}

Roads in HackerLand Python Solution

#!/bin/python3
"""
    https://www.hackerrank.com/challenges/johnland/problem
"""
import os
import sys
import heapq as hq
import time

def find_other(t, i):
    """
        given a tuple (a,b) and 'i' equal to one of them, it returns
        the other value. i.e. if i==a, return 'b' and vice-versa
    """
    if i == t[0]:
        return t[1]
    elif i == t[1]:
        return t[0]
    else:
        return None


#
# Complete the roadsInHackerland function below.
#
def roadsInHackerland(n, roads):
    #
    # Write your code here.
    #
    #base_time = time.time()
    ### largest cost in the resulting MST. used to size the list
    max_cost = 0
    
    ### MST edges. key is tuple (i,j); i<j.  value is the edge'cost',
    edges_cost = dict()
    
    ### list of edges in which the node is part has in the resulting MST
    ### first entry is the number of 'unsolved' edges for the node
    MST_neigh = [[0, []] for _ in range(n)]
    
    ### nodes already added to graph
    added = set([0]);
    
    ### working heap list of tuples (distance, i, j)
    ws = []
    for j,dist in roads[0].items():
        ws.append((dist, 0, j))
    hq.heapify(ws)
    #ws.sort(reverse=True)

    while len(added) < n:
        ### retrive the smallest egde
        #dist,a,b = hq.heappop(ws)
        dist,a,b = hq.heappop(ws)
        
        if a > b:
            a,b = b,a
        if not a in added:
            i = a
        elif not b in added:
            i = b
        else:
            continue

        ### 'na' and 'nb' are calculated later
        edges_cost[(a,b)] = dist
        if dist > max_cost:
            max_cost = dist
        added.add(i)
        MST_neigh[a][0] += 1
        MST_neigh[b][0] += 1
        MST_neigh[a][1].append((a,b))
        MST_neigh[b][1].append((a,b))
        
        for j,dist in roads[i].items():
            if not j in added:
                #ws.append((dist, i, j))
                hq.heappush(ws, (dist, i, j))
        #hq.heapify(ws)
        

    #print("done w/ MST:   ", time.time()-base_time)
    #base_time = time.time()    
    ### find the number of nodes in subtrees on both sides of each edge 
    ### start with nodes having 1 unsolved edge
    
    ### number of nodes in each subtree on both side of an egde
    ### key: (i,j);  value dictionary of {i:nodes, j:nodes}
    edges_nodes = dict()
    
    ### list of nodes to process -add all nodes with 1 unsolved edge
    ws = []
    for node, item in enumerate(MST_neigh):
        if item[0] == 1:
            ws.append((node,item))
    
    while len(ws) > 0:
        me, item = ws.pop(0)
        tmp = 1                 # keeps track of number of nodes
        unsolved = None         # store the 1 unsolved edge
        
        ### avoid processing the very last edge twice
        if item[0] < 1:
            continue
        
        for edge in item[1]:    # walk the edge list
            if edge in edges_nodes:     # already solved
                tmp += edges_nodes[edge][find_other(edge, me)]
            else:
                unsolved = edge

        peer_node = find_other(unsolved, me)    # the other end of unsolved edge
        ### add to number of nodes per edge dict.
        edges_nodes[unsolved] = {me:tmp, peer_node:(n-tmp)}

        ### decrement the number of unsolved nodes
        item[0] -= 1        # this should end up 0
        MST_neigh[peer_node][0] -= 1
        
        ### if the other node only has one unsolved edge, add it to list
        if MST_neigh[peer_node][0] == 1:
            ws.append((peer_node, MST_neigh[peer_node]))

#    for item in enumerate(MST_neigh):
#        print(item)
#    for item in edges_cost.items():
#        print(item)
#    for item in edges_nodes.items():
#        print(item)
    #print("done w/ tree:  ", time.time()-base_time)
    #base_time = time.time()
        
    ### create a list holding the bit for each position
    ### largest number of times using an edge is (n/2)^2.
    ### that is 25Mil, which fits in 25 bits (24.575)
    res = [0] * (max_cost+25)
    
    for edge,i in edges_cost.items():
        ### number a times an edge is traveresed
        count = 1
        for num in edges_nodes[edge].values():
            count *= num
        while count > 0:
            if count & 1:
                res[i] += 1
            count >>= 1
            i += 1
#    print(res)
    ### reduce result's list elements to binary
    max_bit_set = 0
    for i in range(len(res)):
        if res[i] > 1:
            res[i+1] += (res[i]>>1)
            res[i] &= 1
        if (res[i] == 1):
            max_bit_set = i
    
    res = res[:max_bit_set+1]
    res.reverse()
    
    #print("done w/ binary:", time.time()-base_time)
    
    return "".join([str(i) for i in res])

if __name__ == '__main__':
    n, m = [int(i) for i in input().strip().split()]

    #base_time = time.time()
    roads = [dict() for _ in range(n)]

    for _ in range(m):
        i, j, dist = list(map(int, input().rstrip().split()))
        i,j = i-1, j-1
        if (not j in roads[i]) or (roads[i][j] > dist):
            roads[i][j] = dist
            roads[j][i] = dist

    #print("done reading:  ", time.time()-base_time)
    print(roadsInHackerland(n, roads))