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;
}