Find all pairs of numbers such that the number of binary 1's in their OR is maximum

Question

So, I tried to solve this question and my code did not execute within time-limits. https://www.hackerrank.com/challenges/acm-icpc-team

Here's my code,

from itertools import combinations
nm =input().split()
n = int(nm[0])
m = int(nm[1])
mat=[]
z=[]
for i in range(n):
    mat.append(input())  
a=combinations(range(1,n+1),2)

for i in a:
    count=0
    for j in range(m):
        if mat[i[0]-1][j]=="0" and mat[i[1]-1][j]=="0":
            count=count+1  
    z.append(m-count)            
print(max(z))
print(z.count(max(z)))

How can I improve it?

Answer 1

Needless for loop usage

for loops in Python are heavy. Using for loops needlessly leads to performance loss. For instance, rather than doing this:

for j in range(m):
    if mat[i[0]-1][j]=="0" and mat[i[1]-1][j]=="0":

You could just count the number of ones using int(), bin() and | as below:

orResult = int(mat[i[0] - 1], 2) | int(mat[j[0] - 1], 2)
numberOfSubjects = bin(orResult).count("1")

Confusing usage of count

Rather then counting the number of 0's and then subtracting it from m, you could initialize count to m and then decrement it each time 0's are encountered. Then, in the end, count would denote the number of 1's.

Variable naming

Of course, I had to mention this. Variable names are not self-explanatory and it's difficult to understand what they represent exactly. For instance, z means nothing meaningless to me. Please come up with better names. For instance, change

a = combinations(range(1,n+1),2)  

To

indexPairs = combinations(range(1,n+1),2)  

Optimised Code

from itertools import combinations

nm = input().split()
n = int(nm[0])
m = int(nm[1])

attendees=[]
for i in range(n):
    attendees.append(input()) 
indexPairs = combinations(range(1,n+1),2)  

maxNumberOfSubjects = 0
numberOfBestTeams = 0
for pair in indexPairs:
    orResult = int(attendees[pair[0] - 1], 2) | int(attendees[pair[1] - 1], 2)
    numberOfSubjects = bin(orResult).count("1")
    if maxNumberOfSubjects == numberOfSubjects:
        numberOfBestTeams += 1
    elif maxNumberOfSubjects < numberOfSubjects:
        maxNumberOfSubjects = numberOfSubjects
        numberOfBestTeams = 1 

print (maxNumberOfSubjects)
print (numberOfBestTeams) 

I tested the code and it passed all the test cases.

Answer 2

I don't have much time, and don't see any quick performance suggestions, but,

mat = []
for i in range(n):
    mat.append(input())

Can be written more terse as a list comprehension:

mat = [input() for _ in range(n)]

And note how you never use i. If you don't use a variable, you can indicate that it isn't needed by calling it _. That's a placeholder convention to say that "I needed to create a variable, but I don't need it".

---

count=count+1

can be

count += 1

---

Also, please be more careful with spaces around operators. In some places, you use no spaces, in some places you use one on each side, and then in one case, you have

nm =input().split()

I prefer one per side, but regardless of what you choose, you should be consistent.