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.


\$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

    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.


1 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)

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

    '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

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

    Return score
End Function
  • \$\begingroup\$ 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. \$\endgroup\$
    – Anthony
    May 1, 2016 at 21:18
  • \$\begingroup\$ @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. \$\endgroup\$ May 1, 2016 at 21:44
  • \$\begingroup\$ @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! :) \$\endgroup\$ May 1, 2016 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.