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. Rust & Murderer
  5. Discussions

Rust & Murderer

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 63 Discussions, By:

votes

Please Login in order to post a comment

  • cjerian
    7 years ago+ 7 comments

    I tried a variant of BFS where instead of creating the edges of the complement, each time I search the pe (primary edges) and take for j in notdiscovered where (i,j) != pe and (j,i) != pe. notdiscovered starts with all vertices. Instead of adding to discovered, I discard from notdiscovered. I found it was essential to do while q and notdiscovered. notdiscovered becomes empty very fast, and then everything is found already. Without that, it times out.

    14|
    Permalink
    View more Comments..
  • codedecode0111
    7 years ago+ 1 comment

    Editorial is very bad. It doesn't explain clearly the essesntial concepts.

    1. How to convert the graph to a complement graph efficiently? I was trying to put all the edges first in N2 approach. Like for node 1 put 2,3,4... , for node 2 put 1,3,4.... and so on. and then deleting the edges which was given as input. How not to do this is still not clear from the editorial.

    2. What is the relationship between L1 and L2? Was djikstra or any other single source path algorithm was used?

    It will be great if some more effort can be put on the editorials as they are the source of learning.

    11|
    Permalink
  • tyleri
    5 years ago+ 2 comments

    Here's my Python 3 solution. Hope it helps someone.

    tests = int(input())
    
    for _ in range(tests):
        [n, e] = [int(i) for i in input().split(" ")]
        dists = [1] * n
        roads = {}
        for _ in range(e):
            [n1, n2] = [int(i) for i in input().split(" ")]
            if n1 not in roads:
                roads[n1] = set()
            if n2 not in roads:
                roads[n2] = set()
            roads[n1].add(n2)
            roads[n2].add(n1)
        start_loc = int(input())
        not_visited = roads[start_loc] if start_loc in roads else set()
        newly_visited = set()
        curr_dist = 2
        while len(not_visited) > 0:
            for i in not_visited:
                diff = not_visited | roads[i]
                if len(diff) < n:
                    dists[i-1] = curr_dist
                    newly_visited.add(i)
            not_visited = not_visited - newly_visited
            newly_visited = set()
            curr_dist += 1
        del dists[start_loc-1]
        print(" ".join(str(i) for i in dists))
    
    9|
    Permalink
  • suburb4nfilth
    5 years ago+ 0 comments

    Will not give a solution but this can be solved without the complement graph. Check on google how to do BFS on complementary graph :)

    8|
    Permalink
  • daber
    7 years ago+ 1 comment

    Just bought test set #7. It's 35,5MB of data. Difficult to even find editor that is able open that. I also modified code to just read input. It took 3,5 sec just to read input for Scala (readLine split toInt). Last test set is a joke!

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