# HackerRank: ACM ICPC Team

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)

1. In the context of the above algorithm, in what ways can I make it more efficient?

2. Is there a better algorithm?

• Your code is considered too slow you say. How fast is it and how fast does it need to be? – Mast Dec 1 '15 at 10:09
• It would help reviewers to include the sample inputs and outputs here – janos Dec 1 '15 at 10:27
• @janos On each run, the above code will generate highest order test case. – blackened Dec 1 '15 at 10:28

You're spending a lot of time in item_value converting numbers to a binary string back to an int to get the sum. It would be a lot more expedient to just use str.count to get the number of 1s in the string. That saves you a lot of type conversions as well as a call to sum with a generator.

def item_value(e1, e2):
c = bin(int(e1, 2) | int(e2, 2))
return c[2:].count('1')


My results from this caused a reduction from 58.9s to 0.91s.

• Thank you. Just out of curiosity, is there a one-liner equivalent of your code? – blackened Dec 1 '15 at 10:46
• @blackened If you really want you could return bin(int(e1, 2) | int(e2, 2))[2:].count('1') but that feels cluttered to me. – SuperBiasedMan Dec 1 '15 at 10:47

If you even have to add a comment:

# n number of people


Just rename n to NUMBER_OF_PEOPLE, prefer meaningful names over comments, comments may get obsolete as there is no automatic check on them.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.2125910222530365, "perplexity": 2258.3727597028715}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-40/segments/1600400191160.14/warc/CC-MAIN-20200919075646-20200919105646-00138.warc.gz"}