I made a solution to this problem from HackerRank :
You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.
Note Suppose a, b, and c are three different people, then (a,b) and (b,c) are counted as two different teams.
Input Format
The first line contains two integers, N and M, separated by a single space, where N represents the number of people, and M represents the number of topics. N lines follow. Each line contains a binary string of length M. If the ith line's jth character is 1, then the ith person knows the jth topic; otherwise, he doesn't know the topic.
My code is considered too slow (I think I am allowed 10 seconds, the code below takes more than 20 seconds when N and M are both 500):
import random
import itertools
import time
# n number of people
# m number of topics
n = 500
m = 500
"""
binary_string(n) and random_list(n_people, n_topic) just help
to generate test cases, irrelevant otherwise.
"""
def binary_string(n):
my_string = "".join(str(random.randint(0, 1)) for _ in range(n))
return my_string
def random_list(n_people, n_topic):
my_list = [binary_string(n_topic) for _ in range(n_people)]
return my_list
"""
the essential part is item_value(e1, e2)
and find_couples(comb_list)
"""
def item_value(e1, e2):
c = bin(int(e1, 2) | int(e2, 2))
return sum(int(i) for i in c[2:])
def find_couples(comb_list):
max_value = 0
counter = 0
for pair in itertools.combinations(comb_list, 2):
value = item_value(pair[0], pair[1])
if value == max_value:
counter += 1
elif value > max_value:
max_value = value
counter = 1
print(max_value)
print(counter)
return
topic = random_list(n, m)
print(topic)
start = time.time()
find_couples(topic)
end = time.time()
print(end - start)
In the context of the above algorithm, in what ways can I make it more efficient?
Is there a better algorithm?
