HackerRank ‘ACM ICPC Team’ Solution

Short Problem Definition:

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.

Link

ACM ICPC Team

Complexity:

time complexity is O(N^3);

space complexity is O(N)

Execution:

I generate all teams by brute force.

Solution:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;



int acmIcpc(string &str1, string &str2, int length){
    int topicsKnown = 0;
    for (int i=0; i<length; i++){
        if (str1.at(i) == '1' or str2.at(i) == '1'){
            topicsKnown+= 1;
        }
    }
    return topicsKnown;
}
int main() {
    string str[500] = {};
    int N, M;
    cin>>N>>M;
    for (int i=0;i<N;i++) {
        cin>>str[i];
    }
    
    int maxKnown = 0, teamsCnt = 0;
    
    for (int i=0;i<N-1;i++) {
        for (int j=i+1;j<N;j++) {
            int knownForThisCombo = acmIcpc(str[i], str[j], M);
            if (knownForThisCombo > maxKnown){
                maxKnown = knownForThisCombo;
                teamsCnt = 1;
            } else if (knownForThisCombo == maxKnown){
                teamsCnt += 1;
            }
        }
    }
    
    cout << maxKnown << endl;
    cout << teamsCnt << endl;
    return 0;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Brian Pendell

    I don’t completely understand. How many topics can a single attendee know, and how are you capturing that information in your algorithm?

    • For the solution you only need the number of topics, not what specific topics those are. If person A knows topics a and person B knows topics b, the team AB knows topics a OR b.

      It is not enough to know how many topics a person A knows, because there might be an overlap with B. You do not calculate cnt(a)+cnt(b) but a OR b. As for the team AB, you no longer care what topics those are. You can safely only stash cnt(a OR b).

      For the solution, generate all N^2 pairs and calculate how many topics that team knows. In my code those are the maxKnown and teamsCnt values.