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. Jim and his LAN Party
  5. Discussions

Jim and his LAN Party

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 13 Discussions, By:

votes

Please Login in order to post a comment

  • vworld4u
    6 years ago+ 0 comments

    I solved the problem properly for all testcases, but it timed out for a single Testcase which took 13 secs on my machine. I am clueless about the kind of datastructure to select for this problem. But great problem to solve!

    5|
    Permalink
  • imran13
    6 years ago+ 1 comment

    I think,it can be solved using only disjoint set data structure,without any binary search.Although I got wrong answers in 2 test cases.

    1|
    Permalink
  • eugnik_heller
    6 years ago+ 0 comments

    Russian translation has mistake in the output format description Should be 'for every color', not 'for every edge'

    1|
    Permalink
  • TChalla
    1 year ago+ 0 comments

    Python3 solution

    import sys
    
    def read():
        l = sys.stdin.readline()
        if l[-1] == '\n': l = l[:-1]
        xs = filter(lambda x: len(x) > 0, l.split(' '))
        return map(int, xs)
    
    n, m, q = read()
    ps = list(map(lambda x: x - 1, read()))
    gs = [set() for ix in range(m)]
    for ix in range(len(ps)):
        gs[ps[ix]].add(ix)
    uf = []
    for ix in range(len(ps)):
        uf.append([ix, 0, set([ps[ix]])])
    res = []
    for ix in range(len(gs)):
        if len(gs[ix]) < 2:
            res.append(0)
        else:
            res.append(-1)
    
    def find(x):
        if uf[x][0] == x:
            return x
        r = find(uf[x][0])
        uf[x][0] = r
        return r
    
    def union(u, v, ix):
        ur = find(u)
        vr = find(v)
        ur, uh, us = uf[ur]
        vr, vh, vs = uf[vr]
        if uh > vh:
            uf[vr][0] = ur
            uf[ur][2] |= vs
            for g in vs:
                gs[g].discard(vr)
                gs[g].add(ur)
                if res[g] < 0 and len(gs[g]) == 1:
                    res[g] = ix + 1
        elif vh > uh:
            uf[ur][0] = vr
            uf[vr][2] |= us
            for g in vs:
                gs[g].discard(ur)
                gs[g].add(vr)
                if res[g] < 0 and len(gs[g]) == 1:
                    res[g] = ix + 1
        else:
            uf[vr][0] = ur
            uf[ur][1] += 1
            uf[ur][2] |= vs
            for g in vs:
                gs[g].discard(vr)
                gs[g].add(ur)
                if res[g] < 0 and len(gs[g]) == 1:
                    res[g] = ix + 1
    
    for ix in range(q):
        u, v = map(lambda x: x - 1, read())
        union(u, v, ix)
    for r in res:
        print(r)
    
    0|
    Permalink
  • mr_igogo88
    3 years ago+ 1 comment

    Did anyone manage to solve it in Python? Getting timeout for single TC...

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