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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Roads in HackerLand
  5. Discussions

Roads in HackerLand

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 36 Discussions, By:

votes

Please Login in order to post a comment

  • nothidden_
    6 years ago+ 2 comments

    why Floyd Warshall Algorithm is not working here?

    9|
    Permalink
  • robert242
    5 years ago+ 1 comment

    For those that are using Java to solve this problem, do not use BigInteger for calculating your total distance. Look for another solution.

    6|
    Permalink
  • onecrane
    6 years ago+ 3 comments

    Edit - after discussing with @petrovovitch, I see that the shortcut I "discovered" is Kruskal's Minimum Spanning Tree algorithm, and has nothing to do with the edge weights being distinct or being powers of 2 - but either way, it does work. Subsequently counting edge use, as he suggests, is how I solved it as well.

    6|
    Permalink
  • pyduper
    3 years ago+ 0 comments

    We have to calculate minimum distance between all the nodes. 1. First we built the MST using kruskal algo, and then 2. count the number of time each edge is used (using DFS traversal start from any vertex) 3. And then multiply the cost of the edge with it.

    from collections import defaultdict
    
    n, m = map(int, input().split())
    
    edges = []
    parent = [i for i in range(n)]
    
    for _ in range(m):
    	a, b, c = map(int, input().split())
    	edges.append((a-1, b-1, c))
    
    def find(i):
    	while i != parent[parent[i]]:
    		parent[i] = parent[parent[i]]
    		i = parent[i]
    	return i 
    
    def union(x, y):
    	p_x = find(x)
    	p_y = find(y)
    	parent[p_y] = p_x
    
    def is_connected(x, y):
    	p_x = find(x)
    	p_y = find(y)
    	return p_x == p_y
    
    # build MST
    tree = defaultdict(list)
    
    edges.sort(key = lambda x:x[2])
    for a, b, c in edges:
    	if not is_connected(a, b):
    		union(a, b)
    		tree[a].append((b, c))
    		tree[b].append((a, c))
    
    ans = [0]*(2*m)
    
    # Run DFS to count the number of times an edge is used
    # as weights of all edges is different, hence each weight maps to a particular children
    def dfs(src, p = -1):
    	total = 1
    	for v, c in tree[src]:
    		if v != p:
    			children = dfs(v, src)
    			
    			# children => nodes right to edge, n - children => nodes left to edge
    			ans[c] += (n - children)*children	
    			
    			total += children
    	return total
    	
    dfs(0)
    
    res = 0
    for i in range(len(ans)):
    	res += ans[i] * (1 << i)
    
    print(str(bin(res))[2:])
    
    3|
    Permalink
  • mdakan
    6 years ago+ 2 comments

    With Python 3, I'm using Kruskal's algorithm to find the minimum spanning tree and then summing the edges as described by other posts here. This times out on test cases 11+, so I tried the Floyd-Warshall algorithm and that timed out even earlier. What can I do to optimize my solution enough to pass more cases?

    3|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature