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. Matrix
  5. Discussions

Matrix

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 95 Discussions, By:

votes

Please Login in order to post a comment

  • goalboy
    4 years ago+ 4 comments

    Test case #11 input error: it's now

    5 4
    a = [[0,3,3,""],[1, 4, 4,"green"],[1, 3, 4,"green"],[0, 2, 5,""]]
    0 3 3
    1 4 4
    1 3 4
    0 2 5
    1
    3
    4
    
    56|
    Permalink
    View more Comments..
  • denis631
    4 years ago+ 9 comments

    It took me a while to understand what @zac_c_petit was saying, since I didn't know how to do it and DFS for every node sounded foolish.

    The idea is:

    • sort the edges in descending order.
    • For every edge pair:
      • Join if at most one component/group/set has a machine (you can figure this out in O(1) amortized time by augmenting disjoint set (same cost as for find))
      • else you need to destroy that road (add it to your total cost)

    Here's the code in Python (assuming we have already implemented augmented Disjoint Set)

    # Complete the minTime function below.
    def minTime(roads, machines):
        cities_set = DisjointSet()
        cost_to_separate_two_machines = 0
        
        for machine in machines:
            cities_set.make_set(machine, is_machine=True)
    
        ## sort edges. Greatest first
        sorted_edges = sorted(roads, key=lambda road: road[2], reverse=True)
        for node_a, node_b, cost in sorted_edges:
            if cities_set.has_machine_in(node_a) and cities_set.has_machine_in(node_b):
                cost_to_separate_two_machines += cost
            else:
                cities_set.union(node_a, node_b)
        
        return cost_to_separate_two_machines
    
    32|
    Permalink
    View more Comments..
  • zac_c_petit
    6 years ago+ 5 comments

    For those struggling, consider grouping cities by components as you add them, descending by weight (a component would be a group of connected cities). If a component has a machine in it, you know you cannot add another machine to that component.

    30|
    Permalink
    View more Comments..
  • kilicars
    5 years ago+ 4 comments

    As the former comments point out, this problem can be solved using disjoint sets and Kruskal algorithm (with small modifications)

    If you have no idea about these topics, I suggest you watching these very helpful videos:

    Disjoint sets

    Kruskal algorithm

    Then to strengthen your understanding you can solve this.

    Now you are ready for this challenge :)

    Good luck!

    24|
    Permalink
    View more Comments..
  • Voidminded
    2 years ago+ 0 comments

    Why don't you remove the wrong test case???

    16|
    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