There are a number of people who will be attending ACM-ICPC World Finals. Each of them may be well versed in a number of topics. Given a list of topics known by each attendee, presented as binary strings, 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.
Example
n=3
Topics = [‘10101’,’11110’,’00010’]
The attendee data is aligned for clarity below:
10101
11110
00010
These are all possible teams that can be formed:
Members Subjects
(1,2) [1,2,3,4,5]
(1,3) [1,3,4,5]
(2,3) [1,2,3,4]
In this case, the first team will know all 5 subjects. They are the only team that can be created that knows that many subjects, so [5,1] is returned.
Function Description
Complete the acmTeam function in the editor below.
acmTeam has the following parameter(s):
- string topic: a string of binary digits
Returns
- int[2]: the maximum topics and the number of teams that know that many topics
Input Format
The first line contains two space-separated integers n and m, where n is the number of attendees and m is the number of topics.
Each of the next n lines contains a binary string of length m.
Constraints
2<=n<=500
Sample Input
4 5 10101 11100 11010 00101
Sample Output
5 2
ACM ICPC Team HackerRank Solution in C
#include <stdio.h>
int main() {
int n, m;
scanf("%d %d",&n,&m);
char cosa[n][m];
for(int i=0; i<n; i++) {
scanf("%s", cosa[i]);
}
int max = 0;
int cont = 0;
int res[n][n];
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
int matches = 0;
for(int k=0; k<m; k++) {
if(cosa[i][k] != cosa[j][k] || cosa[i][k]=='1') {
matches++;
}
}
res[i][j] = matches;
if(max < matches)
max = matches;
}
}
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
if(res[i][j] == max) {
cont++;
}
}
}
printf("%d\n%d",max,cont);
}
ACM ICPC Team HackerRank Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, cnt = 0, max_tpc = 0, temp_cnt = 0;
cin>>n>>m;
string s[1005];
for( int i = 0; i < n; i++ ) cin>>s[i];
for( int i = 0; i < n; i++ )
for( int j = i + 1; j < n; j++ ){
temp_cnt = 0;
for( int k = 0; k < m; k++ )
if( s[i][k] == '1' || s[j][k] == '1' ) temp_cnt++;
if( temp_cnt == max_tpc ){
cnt++;
continue;
}
if( temp_cnt > max_tpc ){
max_tpc = temp_cnt;
cnt = 1;
//cout<<" i :"<<i<<" j: "<<j<<" cnt: "<<max_tpc;
}
}
cout<<max_tpc<<endl<<cnt<<endl;
return 0;
}
ACM ICPC Team HackerRank Solution in Java
import java.io.*;
import java.util.*;
public class Solution{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String[] bin = new String[N];
boolean[][] b = new boolean[N][M];
for (int i=0; i < N; i++){
bin[i] = br.readLine();
for (int k=0; k < M; k++){
if (bin[i].charAt(k) == '1')
b[i][k] = true;
else
b[i][k] = false;
}
}
int max = 0;
for (int i=0; i < N; i++){
for(int j=0; j < N; j++){
int cnt = 0;
if (i != j){
for (int k=0; k < M; k++){
if ((b[i][k] == true) || (b[j][k] == true)){
cnt++;
}
}
if (cnt > max){
max = cnt;
}
}
}
}
int res = 0;
for (int i=0; i < N; i++){
for(int j=0; j < N; j++){
int cnt = 0;
if (i != j){
for (int k=0; k < M; k++){
if ((b[i][k] == true) || (b[j][k] == true)){
cnt++;
}
}
if (cnt == max){
res++;
}
}
}
}
System.out.println(max);
System.out.println(res/2);
}
}
ACM ICPC Team HackerRank Solution in Python
#O(n^2)
N,k=map(int,raw_input().split())
l=[]
for i in xrange(N):
l.append(int(raw_input(),2))
maxtopics=-1
nummax=1
for i in xrange(N):
for j in xrange(i+1,N):
topics=len([k for k in bin(l[i]|l[j]) if k=='1'])
if(topics>maxtopics):
nummax=1
maxtopics=topics
elif(topics==maxtopics):
nummax+=1
print maxtopics
print nummax
ACM ICPC Team HackerRank Solution in C#
using System;
using System.Linq;
public class Test
{
public static void Main()
{
// your code goes here
int[] num = Console.ReadLine().Trim().Split().Select(x => int.Parse(x)).ToArray();
int N = num[0]; int M = num[1];
int maxTopics = -1;
int maxTopicsGang = 0;
string[] sel = new string[N];
for(int i = 0 ; i < N ; i++)
sel[i] = Console.ReadLine().Trim();
for(int i = 0 ; i < N ; i++){
for(int j = 0 ; j < N ; j++){
int count = 0;
if(i == j)
continue;
for(int k = 0 ; k < M ; k++){
if(sel[i][k] == '1' || sel[j][k] == '1')
count++;
}
if(count > maxTopics){
maxTopics = count;
maxTopicsGang = 1;
}else if (count == maxTopics){
maxTopicsGang++;
}
}
}
Console.WriteLine(maxTopics);
Console.WriteLine(maxTopicsGang/2);
}
}
Attempt ACM ICPC Team HackerRank Challenge
Link – https://www.hackerrank.com/challenges/acm-icpc-team/
Next HackerRank Challenge Solution
Link – https://exploringbits.com/taum-and-bday-hackerrank-solution/
Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.