# “ACM ICPC Team” challenge

I'm attempting this question on HackerRank, which states the follows:

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.

In my code below, I replaced $N$ with ppl and $M$ with topics.

ppl, topics = map(int, input().split())
knowledge = []

max_group = 0
max_topic = 0

for x in range(ppl):
inp = input()
x = [int(i) for i in inp]
knowledge.append(x)

for x in range(ppl):
for y in range(x+1, ppl):
current_topic = 0

for z in range(topics):
if knowledge[x][z] | knowledge[y][z] == 1:
current_topic += 1

if current_topic == max_topic:
max_group += 1
elif current_topic > max_topic:
max_topic = current_topic
max_group = 1

print(max_topic)
print(max_group)


The solution above should return the correct outputs (passed three test cases), but there are simply way too many loops (5, if I am correct). What are some ways that I can reduce the amount of loops and bring the run-time down?

I don't see a better than $(O(N^2M))$ (that is, brute force) solution; however an asymptotic constant could be improved significantly.

First, I recommend to represent an individual knowledge as an integer rather than a list. This way computing a team knowledge is a matter of a single bitwise or, and a number of topics covered is the amount of bits set.

To obtain an integer representation of knowledge, recall that int() takes base as a second argument:

    for _ in range(ppl):
knowledge.append(int(input(), 2))


Then analyze a combined team of x, y knowledge as

    team_topics = bit_count(knowledge[x] | knowledge[y])


There are many ways to implement bit_count. Here is a good place to start.

Observations not related to performance:

• Naming is not particularly good. I expect current_topic to be a loop index running through topics, not the count of topics covered by team. Similarly, max_topic is named as if it represents the maximal index in topics table.

• Dummy loop variable (x in the input loop) is by convention denoted by _. Seeing _ the reader knows it is dummy, and doesn't look for how it might be used in the code.

Use int(input(),2) to convert those binary numbers into its decimal equivalent

for x in range(ppl):
knowledge.append(int(input(),2))


It's better to use count()

Here is the code:

ppl, topics = map(int, input().split())
knowledge = []
pairs_list=[]

for x in range(ppl):
knowledge.append(int(input(),2))

for x in range(ppl):
for y in range(x+1, ppl):
pairs_list.append(bin(knowledge[x] | knowledge[y]).count('1'))

print(max(pairs_list))
print(pairs_list.count(max(pairs_list)))