Computing pairwise bitwise OR in a list of bit-strings

Question

I am trying to solve this problem using Clojure:

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.

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\$. In this string, 1 indicates that the ith person knows a particular topic, and 0 indicates that the ith person does not know the topic.

Output Format:

On the first line, print the maximum number of topics a 2-people team can know. On the second line, print the number of 2-person teams that can know the maximum number of topics.

Constraints:

\2ドル ≤ N ≤ 500\$

\1ドル ≤ M ≤ 500\$

Sample Input:

4 5
10101 
11100 
11010 
00101 

Sample Output:

5 
2

However, my implementation is too slow to pass all the test cases. What are some suggestions to optimize this implementation? Basically, I have a list of bit-strings, and I am trying to find a faster way to bitwise-OR every pair of strings, and find the maximum number of set bits that could be obtained from ORing a pair.

(let [[N _] (clojure.string/split (read-line) #" ")
 N (Integer/parseInt N)
 strings (vec (repeatedly N read-line))
 known 
 (for [i (range N) j (range (inc i) N)
 :let [s1 (strings i)
 s2 (strings j)]]
 (apply + (map #(if (or (= %1 1円)
 (= %2 1円))
 1
 0)
 s1
 s2)))
 maximum (apply max known)]
 (println maximum)
 (println (count (filterv #(= % maximum) known))))

• Jamal: Please revise the title to state the challenge, not the review request. It would also help to embed the challenge objective.
• Brythan: "Finding the maximum bitwise union of pairs from a list of integers" is one possibility for a title that describes the challenge. Also, there's a bitwise tag that would be appropriate for this question. And consider tagging as lisp so that more people can find it.

Answer 1

I was able to get it accepted by optimizing the inner loop by using BitSets instead of plain strings. I then just used the BitSet's or and bit counting method (cardinality) to do the work. Here's the resulting code:

(import [java.util BitSet])
(defn string->bitset [str]
 (let [bitset (BitSet. (count str))]
 (doall (map-indexed #(when (= 1円 %2)
 (.set bitset %1)) str))
 bitset))
(defn bitset-or [s1 s2]
 (let [tmp (.clone s1)]
 (.or tmp s2)
 tmp))
(let [[N _] (clojure.string/split (read-line) #" ")
 N (Integer/parseInt N)
 bitsets (mapv #(string->bitset %) (repeatedly N read-line))
 known 
 (for [i (range N) j (range (inc i) N)
 :let [s1 (bitsets i)
 s2 (bitsets j)]]
 (.cardinality (bitset-or s1 s2)))
 maximum (apply max known)]
 (println maximum)
 (println (count (filterv #(= % maximum) known))))

Answer 2

One optimization would be to first build a map of the attendees with the number of topics for each one and find the maximum number of topics for a single person. You know that the maximum number for a pair will obvious be larger than the maximum for a single person. So when you loop over the pairs to compute the numbers of topics covered by a pair, you can skip the topics intersection computation if the sum of the topics for both attendees is less than the maximum.

I don't know that optimization alone will be sufficient.