HackerRank ACM ICPC Team

Question

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
 peopleKnowledge(i) = Console.ReadLine().ToCharArray()
 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.

Answer 1

Public Sub Main()
 Dim input = Console.ReadLine().Split(" ")
 '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
 peopleKnowledge.Add(New List(Of Boolean))
 Dim CharArray = Console.ReadLine().ToCharArray()
 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)
 peopleKnowledge(i).Add(IsKnowledgeable)
 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

• Anthony: 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.
• Zach Mierzejewski: @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: @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! :)