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.

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

    `