2010 Canadian Computing Competition results

Yeah… I only scored 17 points. What a miscalculation for my original hope of 30! After reviewing my solutions and compared them to the unofficial answers to problems one and two, I realized that I had a lot of miscalculations.

Even though it’s after the competition, I always redo the parts that I did incorrectly so that I can learn from my mistakes, a cliché but it’s true. So in this post, I also have the completed questions that should now score 30 points (after checking with the test cases myself).

S1: Computer Purchase

This problem was actually quite simple now that I read it the second time. Apparently, the problem only required two if comparisons for each line during each of the for loop’s iterations.

  1. Check if the new value is greater than the current highest value or if the new value is equal to the current highest value but sorts alphabetically ahead.
  2. Same as step one but do the same for the second highest value.

Finally, in the output, I forgot to check if there’s only one line of input, e.g., there’s only one computer so it doesn’t make sense to have a first and second preference for the same computer.

Imports System.IO

Module s1
    Sub Main()
        Dim sr As StreamReader = New StreamReader("s1.in")
        Dim lines As Integer
        Dim i As Integer

        Dim input As String
        Dim args(0 To 3) As String
        Dim preference As Integer, name As String

        Dim first As String, second As String
        Dim vFirst As Integer, vSecond As Integer

        lines = sr.ReadLine

        For i = 1 To lines

            input = sr.ReadLine
            args = Split(input)

            'set pretty names
            name = args(0)
            preference = 2 * Int(args(1)) + 3 * Int(args(2)) + Int(args(3))

            'creates a default value to compare to
            If i = 1 Then
                vFirst = preference
                first = name

                vSecond = preference
                second = name
            Else
                If (preference > vFirst) Or _
                   (preference = vFirst And _
                    StrComp(name, first) = -1) Then
					
                    vSecond = vFirst
                    vFirst = preference

                    second = first
                    first = name
                ElseIf (preference > vSecond) Or _
                       (preference = vFirst And _
                        StrComp(name, first) = -1) Then
						
                    vSecond = preference
                    second = name
                End If
            End If
        Next

        Console.Write(first & vbNewLine)
        If first <> second Then : Console.Write(second) : End If
        Console.Read()
    End Sub
End Module

In total, I think I got 13 points from this question because I forgot to delimit the output when there’s only one computer and I misread the lexicographic preference for the longer string.

S2: Huffman Encoding

Again, a simple mistake in my choice in function usage. During the competition,  I used the replace() function which, unfortunately, didn’t do the replacing as I had intended.

It seems that the replace() function doesn’t work well when multiple starting terms, keys, have the same prefix (so much for the prefix-free property!). The prefix-free property only states that one key cannot be the prefix of another longer key (wish I knew this before the competition!).

Instead, a friend recommended me to try loop through every character in the binary string and each key in order to compare each character’s subsequent characters(depending on the current iteration’s key’s length) to the key. If there’s a match, a new string can simply be concatenated with the key’s representative letter.

Imports System.IO

Module s2

    Sub Main()
        Dim sr As StreamReader = New StreamReader("s2.in")
        Dim i, j, k As Integer
        Dim input() As String
        Dim lines As Integer

        Dim letter() As String
        Dim key() As String

        'get total reference keys (starting at 0)
        lines = sr.ReadLine
        k = lines - 1

        ReDim key(0 To k)
        ReDim letter(0 To k)

        For i = 0 To k
            input = sr.ReadLine.Split

            letter(i) = input(0)
            key(i) = input(1)
        Next

        'once all keys are stored in array
        Dim binary As String = sr.ReadLine
        Dim output As String = ""
        Dim x As Integer = 0 'start position

        'loop through each character in binary
        For i = 1 To binary.Length
            'loops through each key until a match is found
            For j = 0 To k
                'check if index counter is out of string index
                If x < binary.Length Then
                    'check for key matches
                    If binary.Substring(x, key(j).Length) = key(j) Then
                        output &= letter(j)
                        x += key(j).Length
                    End If
                End If
            Next
        Next

        Console.Write(output)
        Console.Read()
    End Sub
End Module

Sadly, I only scored 4 points on this question because I used the replace() function instead of an actual algorithm.

Final thoughts

Overall, it was simply because of misinterpretation of the question and shortcuts that led to my, well… disastrous result. If only I had a computer science dictionary during the competition.

Nevertheless, it was fun and challenging to answer these algorithm questions. Even though I probably wouldn’t be getting a certificate, it was a great learning experience and now I can reuse these algorithms for future projects!