# HackerRank 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.

Constraints

$2 ≤ N ≤ 500$
$1 ≤ M ≤ 500$

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.

Imports System

Module Solution
Public Sub Main()
Dim input As String() = Console.Readline().Split(" ")
Dim people As Integer = CInt(input(0))
Dim topics As Integer = CInt(input(1))

Dim peopleKnowledge(people-1)() As Char
Dim maxScore As Integer = 0
Dim teamsWithMaxScore As Integer = 0
Dim score As Integer = 0

For i As Integer = 0 To people-1
Next i

For i As Integer = 0 to people-2
For j As Integer = i+1 To people-1
score = GetTeamScore(peopleKnowledge(i),peopleKnowledge(j),topics)

If score > maxScore Then
maxScore = score
teamsWithMaxScore = 1
ElseIf score = maxScore Then
teamsWithMaxScore += 1
End If
Next j
Next i

Console.WriteLine(maxScore)
Console.WriteLine(teamsWithMaxScore)
End Sub

Private Function GetTeamScore(m1 As Char(),m2 As Char(), topics As Integer) As Integer
Dim score As Integer = 0

For i as Integer = 0 to topics-1
If m1(i).Equals("1"c) Or m2(i).Equals("1"c) Then
score += 1
End If
Next i

Return score
End Function
End Module


Trying to become acquainted with VB.NET so I welcome any and all suggestions. This solution executes in 0.61s with $N = M = 500$; would love to know about any performance gains.

Public Sub Main()
'The variable name should describe what it is more specifically, "people" could mean
'   a List(Of Person), or be a Boolean For If there are people, etc.
'You don't need to explicitly state the data type.  I don't, it's a matter of
'   personal (or company) style, i.e. no consensus either way.
'Take note that you are setting the largest possible number of people or topics here
'   to be <= Int32.MaxValue (2,147,483,647) by casting use CInt().  This is fine
'   because your spec says it will be <= 500.  You could also use Int16
'   (max of 32,767).  My point is that you should be somewhat aware of the sizes of
'   data types you are using.
Dim peopleCount = CInt(input(0))
Dim topicsCount = CInt(input(1))

'Arrays are great for low level or highly structured data, but this is neither.
'   Lists provide many benefits over an array which we'll get to in a second.
'The data is being input to you in a text representation of 0's and 1's, but the
'   actual concept they represent is are they nowledgeable or not which is a Boolean.
Dim peopleKnowledge As New List(Of List(Of Boolean))
Dim maxScore As Integer = 0
Dim teamsWithMaxScoreCount As Integer = 0

For i = 0 To peopleCount - 1

For Each ch In CharArray
'Nowhere in your code was any validation that the only text input on the lines
'   was 0, 1, Or CrLf (return) which is fine if you are the only person who
'   will ever use it, but other users won't always remember rules like that.
Dim IsKnowledgeable = If(ch = "1", True, False)
Next

'No need for the "i" in "Next i"
Next

'Lists allow us to use For Each which helps the developer not have to worry about
'   getting the numbers in the loops right.
'By starting i at 0 and j at 2, I assume you were trying (correctly) to prevent getting
'   team scores for a team of the same person twice.  The way you had it set up though
'   only prevented the very first person being added to itself.  Every other person did
'   have a team score calculated for double their score.
For Each PersonA In peopleKnowledge
For Each PersonB In peopleKnowledge
'This line prevents the getting a team score for a team of the same person twice.
'PersonA and PersonB are both *references* to an object in peopleKnowledge.
'   This comparison compares if they are pointing at the same object, not if
'   the contents of their lists are the same.
If PersonA Is PersonB Then Continue For

Dim score = GetTeamScore(PersonA, PersonB)

If score > maxScore Then
maxScore = score
teamsWithMaxScoreCount = 1
ElseIf score = maxScore Then
teamsWithMaxScoreCount += 1
End If
Next
Next

Console.WriteLine(maxScore)
Console.WriteLine(teamsWithMaxScoreCount)
End Sub

Private Function GetTeamScore(PersonA As List(Of Boolean), PersonB As List(Of Boolean)) As Integer
Dim score As Integer = 0

'Nowhere in your code was any validation that every person's topic list of 1's and 0's
'   were equal in length which is fine if you are the only person who will ever use it,
'   but other users won't always remember rules like that.
For i = 0 To PersonA.Count
If PersonA(i) Or PersonB(i) Then
score += 1
End If
Next

Return score
End Function

• Hi @Zach, thanks for the review - I like the List solution, but my only question would be on performance for having to iterate over every 1 and 0 to create the Boolean List versus just using the array from .ToCharArray(). Also I think by going from i = 0 to people-2(i.e. first person to the second to last person) and from j = i+1 to people-1(i.e. person after the i'th person to the last person) shouldn't end up calculating a score for a team consisting of the same person. – Anthony May 1 '16 at 21:18
• @Tony Ah, you are right about the j = i + 1 thing. I misread it. My solution to that j = i + 1 thing would actually produce every team twice which is incorrect. – Zach Mierzejewski May 1 '16 at 21:44
• @Tony The performance difference between our two ways of iterating over the 1's and 0's would be absolutely minuscule. I would call worrying about that performance a "premature optimization". In a situation like that, I would write whichever way is more readable to the next programmer. My way may actually be less readable than yours, or not (I'm slightly biased! :) – Zach Mierzejewski May 1 '16 at 21:54