“ACM ICPC Team” challenge on Hackerrank

Question

ACM ICPC Team

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 \$i^{th}\$ line's \$j^{th}\$ character is 1, then the \$i^{th}\$ person knows the \$j^{th}\$ topic; otherwise, he doesn't know the topic.

Output Format

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

After several revisions to my code, this is the best I could come up with. It takes around 0.16s to execute Hackerrank's extremity inputs, which I feel is very good, but I was wondering if there would be anything else I could do to improve the efficiency and/or readability of my code.

In addition, one of my first revisions utilized a std::to_string method, which before removing, timed out my process on Hackerrank (thus it must've taken 2+ seconds). The std::to_string was utilized in the innermost for loop, and I was wondering if that method really does impact performance that much, if so, why?

#include <cstdio>
#include <vector>
#include <iostream>

int main(){
    // Insert the input into the three variables:
    //  - 'people' for number of people.
    //  - 'topics' for number of topics.
    //  - 'person' for a vector of strings of the learnt topics of the people.
    int people, topics;
    std::cin >> people >> topics;
    std::vector<std::string> person(people);
    for (int person_i = 0; person_i < people; person_i++) {
       std::cin >> person[person_i];
    }

    // Initializers for the main two output variables.
    int maxTopics = 0;
    int teamsWithMaxTopics = 0;
    // This loop works by taking one person that is not the last person, and then matching that person with all the
    // next people including the last; for each iteration it checks the topics and such. E.g. if I take person 0
    // and I have a total of 3 people, it will match the people in the following order: 0-1, 0-2, 1-1, 1-2.
    // In that way there are no duplicate matches, no same-person matches, and every person gets matched.
    for (int team_i = 0; team_i < people - 1; team_i++) {
        for (int team_j = team_i + 1; team_j < people; team_j++) {
            // Initializer for the checking of how many topics does each team know.
            int topicsInTeam = 0;
            // Runs through each topic.
            for (int topic_i = 0; topic_i < topics; topic_i++) {
                // Sets the status for each person's topic, to make calculation easier.
                int personOneTopic = int(person[team_i][topic_i] - '0');
                int personTwoTopic = int(person[team_j][topic_i] - '0');
                // A bitwise OR operator to check if either person has the topic, increase the amount of topics if so.
                if (personOneTopic|personTwoTopic) {
                    topicsInTeam++;
                }
            }        

            // Checks if the amount of topics in this team is more than the maximum detected before.
            // If so, then reset the amount of teams with maximum topics.
            // If they have the same, then just add to the amount of teams with maximum topics.
            if (topicsInTeam > maxTopics) {
                teamsWithMaxTopics = 1;
                maxTopics = topicsInTeam;
            } else if (topicsInTeam == maxTopics) {
                teamsWithMaxTopics++;
            } 
        }
    }

    // Output
    std::cout << maxTopics << std::endl;
    std::cout << teamsWithMaxTopics << std::endl;

    return 0;
}

Answer 1

I have some comments on your code that you may find useful.

Keep writing good comments

The comments are clear, relevant and actually assist in understanding the program. Well done, and keep doing that!

Only include files that are needed

The current code doesn't use anything from <cstdio> so that include may be omitted.

Possible algorithm improvement

One thing that may (on average) improve the speed of the program is to quickly eliminate pairs of people who can't possibly improve the top current score \$t\$. A simple way to do that would be to additionally store the number of skills \$s_i\$ for each person \$i\$. That way, as each pair \$i, j\$ is considered, if \$s_i + s_j < t\$, then there's no point in doing the skill-by-skill comparison.

Consider using a std::valarray

It may or may not run faster, but an alternative data structure to the current std::vector<std::string> might be a std::vector<std::valarray<bool>>. That way, the conversion to bool can be done just once during the initial read of input data. For example:

std::vector<std::valarray<bool>> person(people, std::valarray<bool>(topics));
for (int person_i = 0; person_i < people; person_i++) {
    std::string skills;
    std::cin >> skills;
    for (int i = 0; i < topics; ++i) {
        person[person_i][i] = (skills[i] == '1');
    }
}

Use a standard algorithm

One could use std::inner_product to calculate the topicsInTeam value rather than iterating "by hand." This might have an advantage for some compilers in which the operations are parallelized by the implementation of valarray.

int topicsInTeam = std::inner_product(
    &person[team_i][0],       // first iterator start
    &person[team_i][topics],  // first iterator end
    &person[team_j][0],       // second iterator start
    0,                        // initial value 
    [](int a, int b){ return a+b;},   // sum lambda
    [](bool a, bool b){return (a|b) ? 1 : 0;}   // * lambda
);

Use an object

Combining the above ideas into an object, the main routine can become quite clean. Consider the following very simple object:

// for this progam, each Person is merely a collection of skills
class Person 
{
public:
    Person(int skillcount) 
    : skills(skillcount)
    { }
    int with(const Person& other) const {
        return std::inner_product(
            &skills[0], 
            &skills[skills.size()], 
            &other.skills[0],
            0, 
            [](int a, int b){ return a+b;}, 
            [](bool a, bool b){return (a|b) ? 1 : 0;}
        );
    }
    friend std::istream& operator>>(std::istream& in, Person& p) {
        std::string skillset;
        in >> skillset;
        for (size_t i = 0; i < p.skills.size(); ++i) {
            p.skills[i] = (skillset[i] == '1');
        }
        return in;
    }
private:
    std::valarray<bool> skills;
};

Now your main can be as simple as this:

int main(){
    int peopleCount, topicCount;
    std::cin >> peopleCount >> topicCount;
    std::vector<Person> people(peopleCount, Person(topicCount));
    for (auto &person : people) {
        std::cin >> person;
    }
    int maxTopics = 0;
    int teamsWithMaxTopics = 0;
    for (auto first = people.cbegin(); first != people.cend()-1; ++first) {
        for (auto second = first+1; second != people.cend(); ++second) {
            int topicsInTeam = (*first).with(*second);
            if (topicsInTeam > maxTopics) {
                teamsWithMaxTopics = 1;
                maxTopics = topicsInTeam;
            } else if (topicsInTeam == maxTopics) {
                teamsWithMaxTopics++;
            } 
        }
    }
    std::cout << maxTopics << '\n' << teamsWithMaxTopics << '\n';
}

Note, too, that I have used iterators and "range-for" constructs instead of indexing. It makes thing easier to understand, I think, and allows us to encode things more concisely. Also note that I've renamed some variables to more clearly convey what they contain.

Combine output operations

The current code contains these two lines:

std::cout << maxTopics << std::endl;
std::cout << teamsWithMaxTopics << std::endl;

It won't make much difference here, but generally one can reduce time by combining operations and eliminating the implicit flush() that occurs as part of std::endl when all you really need is a newline. Here's the alternative:

std::cout << maxTopics << '\n' << teamsWithMaxTopics << '\n';

The output will be flushed anyway when the program ends, so there's no need for an explicit std::endl here.

Why was to_string slow?

Conversion from integer or floating point to string representation is often slow for several reasons. First, it's often implemented in terms of division which is often one of the slower mathematical operations of a given CPU. Second, it often also requires memory allocation to store the resulting string, which often requires interaction with the underlying operating system. That, too, slows things down. Eliminating both operations often yields considerable speedup.

Answer 2

It's called main. It's not called everything.

We should be breaking our code down into functions. We also have lots of quite large comment blocks. Properly written functions with good names will make our code self-documenting enough to cut down on the amount of comments required without reducing the readability of our code (because writing readable code is important).

---

Typically, when we are getting input from a user, we want to prompt them with what sort of input we're expecting. And I like to making this combination of prompting and getting input quite easy and natural, and it's typically something you're going to do repeatedly (as you've done here), so it's typically going to be one of the first functions I write:

std::string getInput(std::string prompt) {
    std::cout << prompt;
    std::string value;
    std::cin >> value;
    return value;
}

Of course, this probably isn't perfect--it only works when we want to grab strings, but I think it gives you an idea of just one of the ways we can break our code down into functions rather than turning main into everything.

The next most logic function to break out of here is a function for returning a vector of N people. That would look something like this:

std::vector<std::string> getPeople(int numberOfPeople) {
    std::vector<std::string> people = std::vector<std::string>();

    while (people.size() < numberOfPeople) {
        people.push_back(getInput("Enter the next person: "));
    }

    return people;
}

And now, in main, you're using that something like this:

int main() {
    std::vector<std::string> competitors = getPeople(getIntInput("How many people? "));

    // ...
}

This replaces the first ten lines of main with a single line and eliminates some unnecessarily variables. Moreover, we've replaced a lot of comments with appropriately named functions that make the code at least equally readable (arguably moreso because I can read it in line instead of having to read it, and then refer back to the comments above it), and I don't have to worry about remembering to update the comments if I've changed the code.

We should always strive to first break down our problems into the smallest possible units, and then solve those smaller problems one at a time.