Project Euler #186: Connectedness of a network.
Project Euler #186: Connectedness of a network.
+ 1 comment i cant understand the problem, someone please help!
+ 2 comments I dont understand what actually is required to do in the program. Can i receive some help?
+ 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?
+ 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 comments how
Sort 11 Discussions, By:
Please Login in order to post a comment