HackerRank Roads in HackerLand problem solution

In this 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 (i.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.

HackerRank Roads in HackerLand problem solution in Python.

#!/bin/python3

p = list(range(10 ** 5))

def dsu_get(v):
    if p[v] != v: p[v] = dsu_get(p[v])
    
    return p[v]

def dsu_merge(u, v):
    u = dsu_get(u)
    v = dsu_get(v)
    p[u] = v
    
    return u != v

n, m = map(int, input().split())
e = []
for i in range(m):
    a, b, c = map(int, input().split())
    e += [(c, b - 1, a - 1)]

e.sort()

G = [[] for x in range(n)]
for c, a, b in e:
    if dsu_merge(a, b):
        G[a] += [(b, c)]
        G[b] += [(a, c)]

f = [0] * m
def dfs(v, par = -1):
    sz = 1
    for u, c in G[v]:
        if u == par: continue
        
        y = dfs(u, v)
        
        f[c] = y * (n - y)
        sz += y
    
    return sz

dfs(0)

ans = 0
for x in f[::-1]:
    ans *= 2
    ans += x

print(bin(ans)[2:])

Roads in HackerLand problem solution in Java.

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;
      }
    }
  }
}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

template<class T> inline T sqr(const T& a) {
  return a * a;
}

template<class T> inline int len(const T &c) {
  return static_cast<int>(c.size());
}

template<class T> inline void maximize(T &r, const T c) {
  r = max(r, c);
}

template<class T> inline void minimize(T &r, const T c) {
  r = min(r, c);
}

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const ld EPS = 1e-9;
const ld PI = 2 * acos(0.0);
const int N = 100100;

struct DSU {
  int size;
  vector<int> p;
  vector<int> w;

  DSU(int n) :
    size(n),
    p(n, -1),
    w(n, 1) {}

  int Parent(int v) {
    if (p[v] == -1)
      return v;
    return p[v] = Parent(p[v]);
  }

  void Union(int u, int v) {
    u = Parent(u);
    v = Parent(v);
    if (w[u] < w[v])
      swap(u, v);
    p[v] = u;
    w[u] += w[v];
  }
};

vector<pt> g[N];
vector<pt> tree[N];
li total;
int subt[N];
vector<li> ans;

int Dfs(int v, int prev, int w) {
  subt[v] = 1;
  for (pt &e : tree[v]) {
    if (e.first == prev)
      continue;
    subt[v] += Dfs(e.first, v, e.second);
  }
  if (w >= 0) {
    li used = (total - subt[v]) * subt[v];
    while (w >= len(ans)) {
      ans.push_back(0);
    }
    ans[w] += used;
  }
  return subt[v];
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  total = n;
  vector<pair<int, pt>> edges;
  for (int i = 0; i < m; ++i) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    --x, --y;
    edges.push_back({w, {x, y}});
    g[x].push_back({y, w});
    g[y].push_back({x, w});  
  }
  sort(edges.begin(), edges.end());

  DSU dsu(n);
  for (auto &e : edges) {
    int x = e.second.first;
    int y = e.second.second;
    int u = dsu.Parent(x);
    int v = dsu.Parent(y);
    if (u != v) {
      tree[x].push_back({y, e.first});
      tree[y].push_back({x, e.first});
      dsu.Union(u, v);
    }
  }

  Dfs(0, -1, -1);

  li r = 0;
  for (int i = 0; i < len(ans) || r; ++i) {
    while (i >= len(ans)) {
      ans.push_back(0);
    }
    r += ans[i];
    ans[i] = r & 1;
    r >>= 1;
  }
  bool started = false;
  for (int i = len(ans) - 1; i >= 0; --i) {
    bool on = ans[i] > 0;
    if (on) {
      started = true;
    }
    if (started) {
      putchar(on ? '1' : '0');
    }
  }
  if (!started) {
    puts("0");
  } else {
    puts("");
  }
  return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.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;
}