"ACM ICPC Team" challenge on Hackerrank... Easy?

Question

This challenge took me awhile to figure out, and it's characterized as "easy," so I'm sorta wondering what I missed.

Problem Statement

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.

N = number of people = number of lines of input. 2 ≤ N ≤ 500
M = number of topics = number of bits per line. 1 ≤ M ≤ 500

Sample Input

4 5
10101
11100
11010
00101

Sample Output

5
2

My solution below uses a BitArray object, because all of the test cases except one have more than 32 topics.

I'm wondering if HackerRank wasn't expecting something a little more fundamental... Maybe some clever string twiddling hack that I don't know about?

Most of the test cases took about .86 seconds to execute, which seems quite slow to me.

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Text;

class Solution {
    static void Main(String[] args) 
    {
        string input = Console.ReadLine();
        string[] inputs = input.Split(new char[] {' '});
        
        int numberOfMembers = int.Parse(inputs[0]);
        int numberOfTopics = int.Parse(inputs[1]);
        
        var bitArray = new BitArray[numberOfMembers];
        for (int n = 0; n < numberOfMembers; n++)
        {
            bitArray[n] = new BitArray(numberOfTopics);
            
            string memberTopics = Console.ReadLine();
            for(int m = 0; m < numberOfTopics; m++)
                bitArray[n].Set(m, memberTopics[m] == '1');
        }

        // Find the maximum number of topics that all the teams know.
        int maxTopics = 0;
        for(int i = 0; i < numberOfMembers - 1; i++)
            for (int j = i + 1; j < numberOfMembers; j++)
            {
                int numberOfTeamTopics = NumberOfSetBits(new BitArray(numberOfTopics).Or(bitArray[i]).Or(bitArray[j]));
                if (numberOfTeamTopics > maxTopics)
                    maxTopics = numberOfTeamTopics;
            }
        
        // Find the number of teams that know the maximum number of topics.
        int maxTeams = 0;
        for(int i = 0; i < numberOfMembers - 1; i++)
            for (int j = i + 1; j < numberOfMembers; j++)
            {
                int numberOfTeamTopics = NumberOfSetBits(new BitArray(numberOfTopics).Or(bitArray[i]).Or(bitArray[j]));
                if (numberOfTeamTopics == maxTopics)
                    maxTeams++;
            }
        
        Console.WriteLine(maxTopics);
        Console.WriteLine(maxTeams);
    }
    
    static int NumberOfSetBits(BitArray b)
    {
        int count = 0;
        for (int i = 0; i < b.Length; i++)
            if (b.Get(i))
                count++;
        return count;
    }
}

Answer 1

Some improvements:

Combine loops

int maxTopics = 0;
int maxTeams = 0;
for(int i = 0; i < numberOfMembers - 1; i++)
    for (int j = i + 1; j < numberOfMembers; j++)
    {
        int numberOfTeamTopics 
            = NumberOfSetBits(new BitArray(numberOfTopics).Or(bitArray[i]).Or(bitArray[j]));

        if (numberOfTeamTopics > maxTopics)
        {
            maxTopics = numberOfTeamTopics;
            maxTeams = 1;
        }
        else if (numberOfTeamTopics == maxTopics)
        {
            maxTeams++; 
        }
    }

Use a better algorithm for counting set bits

public static Int32 NumberOfSetBits(BitArray bitArray)
{
    Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];
    bitArray.CopyTo(ints, 0);
    Int32 count = 0;

    // fix for not truncated bits in last integer that may have been set to true with SetAll()
    ints[ints.Length - 1] &= ~(-1 << (bitArray.Count % 32));

    for (Int32 i = 0; i < ints.Length; i++)
    {
        Int32 c = ints[i];

        // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)
        unchecked
        {
            c = c - ((c >> 1) & 0x55555555);
            c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
            c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
        }
        count += c;
    }
    return count;
}

New execution time: 0.12 seconds.

Answer 2

Code Style

A number of commonly criticized code style issues are there in your code. The most noticable one is the lack of braces for single-statement blocks. This is relatively commonly found with if-statements, like you have with:

if (numberOfTeamTopics > maxTopics)
    maxTopics = numberOfTeamTopics;

That should be written as:

if (numberOfTeamTopics > maxTopics)
{
    maxTopics = numberOfTeamTopics;
}

The reason is not specifically for readability, but for maintainability. Consider the change you made in your answer, merging two loops. You converted the above if-statement to be:

if (numberOfTeamTopics > maxTopics)
{
    maxTopics = numberOfTeamTopics;
    maxTeams = 1;
}

Now, in a change management/version-control system, your single change (moving the line maxTeams = 1) has changed 3 lines of code, and it looks like you added three lines in the diff, making the change look more substantial than need be.

Tracking changes is often the hardest part about maintaining code, and being able to separate substantial changes from clutter is hard.

By placing braces appropriately when you first write the code, you make subsequent changes clutter-free.

This is even more apparent in code like:

    for (int i = 0; i < b.Length; i++)
        if (b.Get(i))
            count++;

Function Extraction

I realize that programming challenges like this often end up with logic piled in to the Main method. Object oriented code and challenges like this are often incompatible. Still, functional extraction is useful, and you don't do it enough. Consider code like:

    for (int n = 0; n < numberOfMembers; n++)
    {
        bitArray[n] = new BitArray(numberOfTopics);

        string memberTopics = Console.ReadLine();
        for(int m = 0; m < numberOfTopics; m++)
            bitArray[n].Set(m, memberTopics[m] == '1');
    }

That should be written with a function to extract the BitArray, and used like:

    for (int n = 0; n < numberOfMembers; n++)
    {
        bitArray[n] = ReadBits(numberOfBits);
    }

Algorithm

In your answer you suggest you can merge two loops and save time that way. You are right, but you can take it even further... you can merge all three loops.

In addition, you can incorporate some memoization and dynamic programming to make the algorithm more efficient.

In your code, you read all the data in to memory, and then scan each row against all the rows that follow it. You can reverse that logic, and scan each row against all the rows from before it.

Consider storing the number of topics each member is proficient in, in an array, and then using that to short-circuit impossible circumstances.

By merging the three arrays I halved the execution time on HackerRank to about 0.45 seconds.

I am surprised that the BitArray system you use makes such a difference (4X down to 0.12 is impressive), but by merging the suggestions above (and code below), you should be able to get another loop out of the system. Note, using a BitArray will reduce the memory usage a lot, so it may be that which is making the difference....

Note that these are not changing the time complexity of the solutions, just the number of iterations through the data.

Even I am falling victim to the overloaded Main method, but here's the code I suggest:

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Text;

class Solution {

    static void Main(String[] args) 
    {
        string input = Console.ReadLine();
        string[] inputs = input.Split(new char[] {' '});

        int numberOfMembers = int.Parse(inputs[0]);
        int numberOfTopics = int.Parse(inputs[1]);

        int [] topicCounts = new int[numberOfMembers];
        char[][] memberMatrix = new char[numberOfMembers][];

        int maxTopics = 0;
        int maxTeams = 0;

        for (int member = 0; member < numberOfMembers; member++)
        {
            char[] line = Console.ReadLine().ToCharArray();
            int lineCount = CountTopics(line);
            memberMatrix[member] = line;
            topicCounts[member] = lineCount;
            for (int matchWith = 0; matchWith < member; matchWith++) {
                int common = CountCommon(line, lineCount, memberMatrix[matchWith], 
                                            topicCounts[matchWith], numberOfTopics, maxTopics);
                if (common >= maxTopics)
                {
                    if (common > maxTopics)
                    {
                        maxTopics = common;
                        maxTeams = 0;
                    }
                    maxTeams++;
                }
            }
        }

        Console.WriteLine(maxTopics);
        Console.WriteLine(maxTeams);
    }

    static int CountCommon(char[] member, int memberTopics,
        char[] match, int matchTopics, int width, int needTopics)
    {
        int potential = memberTopics + matchTopics;
        int count = 0;
        for (int i = 0; i < width && potential >= needTopics; i++)
        {
            if (member[i] == '1' || match[i] == '1')
            {
                count++;
                if (member[i] == match[i])
                {
                    potential--;
                }
            }
        }
        return count;
    }

    static int CountTopics(char[] topicMap)
    {
        int count = 0;
        for (int i = 0; i < topicMap.Length; i++)
        {
            if (topicMap[i] != '0')
            {
                count++;
            }
        }
        return count;
    }
}