Header Ad

HackerRank ACM ICPC Team problem solution

In this HackerRank ACM ICPC Team problem, you need to determine the maximum number of topics a 2-person team can know. Each subject has a column in the binary string, and a '1' means the subject is known while '0' means it is not. Also, determine the number of teams that know the maximum number of topics. Return an integer array with two elements. The first is the maximum number of topics known, and the second is the number of teams that know that number of topics.

HackerRank ACM ICPC Team problem solution


Problem solution in Python programming.

line = input()
line = line.split()
n = int(line[0])
m = int(line[1])

people = [input() for i  in range(n)]
skills = []
max_skills = 0

for i in range(len(people)):
    j = i
    while j < n:
        first_person = people[i]
        second_person = people[j]
        
        skill = bin(int(first_person, 2) | int(second_person, 2))[2:].count('1')
        if (skill > max_skills):
            max_skills = skill
        skills.append(str(skill))
        
        j += 1

print(max_skills)
print(skills.count(str(max_skills)))


Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(); //number of people
        int M = in.nextInt(); //number of topics
        String[] person_info = new String[N];
        
        for (int i = 0; i < N; i++) 
            person_info[i] = in.next();
        long teams = 0;
        long max_covered = 0;
        long matched_topics = 0;
        for (int i = 0; i < N; i++) {
            
            for (int k = i + 1; k < N; k++) {
                matched_topics = 0;
                for (int j = 0; j < M; j++) {
           
                    if (person_info[i].charAt(j) - '0' > 0 || person_info[k].charAt(j) - '0' > 0)
                        matched_topics++;
                }
                if (matched_topics == max_covered)
                    teams++;
                else if (matched_topics > max_covered) {
                    max_covered = matched_topics;
                    teams = 1;   
                }
            }
           
            
            
       
        }
        
        System.out.println(max_covered);
        System.out.println(teams);
        /*for (int i = 0; i < N; i++) {
            System.out.printf("%s\n", person_info[i]);
        }*/
        in.close();
    }
}


Problem solution in C++ programming.

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;

char s[3001][1001];

int main() {
    int n, m;
    cin >> n >> m;
    vvi v(n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", s[i]);
        for (int j = 0; j < m; j += 32) {
            v[i].push_back(0);
            for (int k = 0; k < 32 && j + k < m; ++k) if (s[i][j + k] == '1') {
                v[i].back() += (1 << k);
            }
        }
    }
    int ma = 0, cnt = 0;
    for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
        int cur = 0;
        for (int l = 0; l < v[i].size(); ++l) {
            cur += __builtin_popcount(v[i][l] | v[j][l]);
        }
        if (cur == ma) ++cnt;
        else if (cur > ma) {
            ma = cur;
            cnt = 1;
        }
    }
    cout << ma << endl << cnt << endl;
    return 0;
}


Problem solution in C programming.

#include <stdio.h>
#include <math.h>

int totalTopics(unsigned char *topics1, unsigned char *topics2, int topics) {
    int total = 0;
    for (int j=0; j<topics; j++) {
        unsigned char orValue = topics1[j] | topics2[j];
        if (orValue)
            total++;
    }
    return total;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    unsigned char topics[N][M];
    for (int i=0; i<N; i++) {
        unsigned char input;
        scanf("%c", &input);
        for (int j=0; j<M; j++) {
            scanf("%c", &input);
            topics[i][j] = input-'0';
//            printf("%d", topics[i][j]);
        }
//        printf("\n");
    }
    int combined[M+1];
    for (int j=1; j<=M; j++)
        combined[j] = 0;
    for (int i=0; i<N; i++)
        for (int j=i+1; j<N; j++) {
            int total = totalTopics(topics[i], topics[j], M);
//            printf("Members %d and %d have %d topics\n", i, j, total);
            combined[total]++;
        }
    for (int j=M; j>0; j--)
        if (combined[j] > 0) {
            printf("%d\n%d\n", j, combined[j]);
            break;
        }
        
    return 0;
}


Problem solution in JavaScript programming.


function howManyBitsOn(a, b) {
    var on = 0;
    for (var i = 0; i < a.length; i ++) {
      if (a.charAt(i) === "1") {
          on++;
      } else if (b.charAt(i) === "1") {
          on++;
      }
    }
    return on;
}

function processData(input) {
   var lines = input.split("\n");
   var parts = lines[0].split(" ");
   var n = parts[0];
   var m = parts[1];
   var max = 0;
   var teams = 0;
   
   for (var i = 0; i < n; i++) {
        for (var j = i + 1; j < n; j++) {
            var c = howManyBitsOn(lines[1 + i], lines[1 + j]);

            if (c > max) {
                teams = 0;
                max = c;
            }

            if (c == max) {
                teams++;
            }
        }
   }    
   
   process.stdout.write(max + "\n" + teams);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});


Post a Comment

1 Comments

  1. is there any better solution as its complexity becomes n^3

    ReplyDelete