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. All Contests
  2. ProjectEuler+
  3. Project Euler #186: Connectedness of a network.
  4. Discussions

Project Euler #186: Connectedness of a network.

Problem
Submissions
Leaderboard
Discussions

Sort 11 Discussions, By:

votes

Please Login in order to post a comment

  • StormBreaker77
    5 years ago+ 1 comment

    i cant understand the problem, someone please help!

    12|
    Permalink
  • mayanksheth671
    5 years ago+ 2 comments

    I dont understand what actually is required to do in the program. Can i receive some help?

    5|
    Permalink
  • sivakfil
    2 years ago+ 1 comment

    I have a solution in python3 that I think is using correct data structure and is quite optimized. However, test case 20 is always timing out nad test case 19 is saying wrong answer. Is there anyone with similar issues?

    2|
    Permalink
  • APovalyaev
    11 months ago+ 0 comments

    I am considering initial use-case: 000000 1 Before the PM number is met for the second time (call number 622573) almost all the previous calls have been made between "independent" users. In other words, all of them are parts of groups within size 2. So, there is no one big group of frends which include 10000 users/friends of PM. SO, It looks like there is an issue. OR I've not got something. Here is my code:

    # Enter your code here. Read input from STDIN. Print output to STDOUT
    Sk_cache = dict()
    
    def Sk(k):
        global Sk_cache
        if k in Sk_cache:
            return Sk_cache[k]
        res = 0
        if k <= 55:
            res = (100003 - 200003*k + 300007*(k**3)) % (10**6)
        else:
            res = (Sk(k-24) + Sk(k-55)) % (10**6)
        Sk_cache[k] = res
        return res
    
    NUMBER, p = map(int, input().rstrip().split())
    
    groups = 0
    number2group = dict() # number -> a
    group_cnt = dict() # a -> int
    group_connection = set() # (a,b) 
    
    number_found = False
    target_number_group = 0
    cur_p = 0
    
    #print("NUMBER {} p {}".format(NUMBER, p))
    
    i = 1
    calls = 0
    while (not number_found or cur_p < p*(10**4)) and i <= 2*10**6:
        calls += 1
        cur_number_from = Sk(2*calls-1)
        cur_number_to = Sk(2*calls)
        #print("call N{} from {} to {}".format(calls, cur_number_from, cur_number_to))
        if cur_number_from == NUMBER or cur_number_to == NUMBER:
            number_found = True
        
        number_from_group = 0
        number_to_group = 0
        if cur_number_from is number2group:
            #print("Already grouped 1")
            number_from_group = number2group[cur_number_from]
        if cur_number_to is number2group:
            #print("Already grouped 2")
            number_to_group = number2group[cur_number_to]
            
        #if number_from_group != number_to_group and number_from_group != 0 and number_to_group != 0:
        #    print("Connection found!")
            
        if number_from_group != number_to_group and number_from_group != 0 and number_to_group != 0 and (number_from_group, number_to_group) not in group_connection:
            group_connection.add((number_from_group, number_to_group))
            group_connection.add((number_to_group, number_from_group))
            prev_cnt = group_cnt[number_from_group]
            group_cnt[number_from_group] += group_cnt[number_to_group]
            group_cnt[number_to_group] += prev_cnt
            
        if number_from_group == 0 and number_to_group != 0:
            #print("Group extension 1")
            number_from_group = number_to_group
            number2group[cur_number_from] = number_to_group
            group_cnt[number_to_group] += 1
            
        if number_from_group != 0 and number_to_group == 0:
            #print("Group extension 2")
            number_to_group == number_from_group
            number2group[cur_number_to] = number_from_group
            group_cnt[number_from_group] += 1
        
        if number_from_group == 0 and number_to_group == 0 and cur_number_from != cur_number_to:
            groups += 1
            number2group[cur_number_to] = groups
            number2group[cur_number_from] = groups
            group_cnt[groups] = 2
            number_to_group = groups
            number_from_group = groups
            
        #if number_to_group != 0:
        #    if group_cnt[number_to_group] > 2:
        #        print("group {} number {}".format(number_to_group, group_cnt[number_to_group]))
        #if number_from_group != 0:
        #    if group_cnt[number_from_group] > 2:
        #        print("group {} number {}".format(number_from_group, group_cnt[number_from_group]))
    
        if cur_number_from == NUMBER or cur_number_to == NUMBER:
            number_found = True
            target_number_group = number2group[cur_number_from]
            source_number_group = number2group[cur_number_to]
            #print("call N{} from {} to {} groups {}, {} total_groups {}".format(calls, cur_number_from, cur_number_to, target_number_group, source_number_group, groups))
         
        if target_number_group != 0:
            cur_p = group_cnt[target_number_group]
            #print("{}".format(cur_p))
            
            
        i += 2
        
        
    if number_found and cur_p >= p*(10**4):
        print("{}".format(calls))
        #print("target group count = {}".format(group_cnt[target_number_group]))
        #print("target group number = {}".format(target_number_group))
        #print("group connection {}".format(len(group_connection)))
    
    
    

    `

    0|
    Permalink
  • muharamismail123
    2 years ago+ 0 comments

    how

    0|
    Permalink
Load more conversations

Need Help?


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