2
\$\begingroup\$

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))))
\$\endgroup\$
  • 1
    \$\begingroup\$ Please revise the title to state the challenge, not the review request. It would also help to embed the challenge objective. \$\endgroup\$ – Jamal Nov 9 '14 at 2:17
  • \$\begingroup\$ "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. \$\endgroup\$ – Brythan Nov 9 '14 at 2:44
1
\$\begingroup\$

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))))
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.