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

Project Euler #186: Connectedness of a network.

Sort by

recency

|

11 Discussions

|

  • APovalyaev
     + 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)))

    `

  • sivakfil
     + 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?

  • muharamismail123
     + 0 comments

    how

  • Termii
     + 1 comment

    hey, I need help.

    I am more or less done, but I am stuck with 1 strange bug.

    I am counting how many numbers I have generated until the prime minister has enough "friends". If I divide that number by 2, I get the number of calls. My solution is 622573 calls (622572 would be right) for the test case.

    Thats why I subtract 1 from my "solution", but that way I only get 60 points (12/20 testcases correct). If I subtract 2 from my "solution", I get 35 points (7/20 testcases correct). As for testcase 20/20, I never got that one right.

    What could be my bug/misunderstanding of the problem??

    Edit: fixed it now. 100/100points. forgot to count the misdials ^^'

  • tmckanna1
     + 2 comments

    Can anyone who has finished this problem explain how they avoided overflowing their numbers when calculating for large k. I'm stuck on this.