2010 Canadian Computing Competition

It has been awhile since I last wrote anything; for some reason, all of February has been hectic for me. On February 23, me a and a few other friends competed in the Canadian Computing Challenge (CCC).

The competition is held annually around February and is divided into two categories: juniors and seniors for students in grades 8 to 12 in Canada. It lasts 3 hours and students can use any standard programming language in the first round. If they made it into the top 20, they will be invited to compete in the second round in May, but are limited to using Pascal, C, or C++.

Junior topics

Senior topics (in addition to junior topics)

Of course, these are only some of the many other topics in computer science that are covered by the questions. Check out the unofficial answers site to compare the differences in difficulty.

Although we had little understanding of the advanced topics in computer science such as graphs and trees, most of us competed in the senior level. We all wanted the challenge to test what we learned from our computer science classes in school.

I used Visual Basic .NET to create a console application because it’s the only programming language and framework that I know (excluding PHP and Javascript). While It is possible to use PHP, it’s harder to debug because I was limited to only using standard editors and compliers (so no third-party PHP debugging frameworks). Javascript is impossible because the input is from text files.

In total, the contest took me three hours to fully finish two of the five questions. Technically, this was a fail but considering that last year’s average was only 14/75 marks, I feel confident about my final score.

Since the official contest questions and unofficial answers are not released yet, I decided to share my answers and see if anyone else has did something similar. The given questions are only a summary of the official question.

Problem S1: Computer Purchase

In order to increase your performance on the ABC (Another Buying Contest), you decide that you need a new computer. When determining which computer to buy, you narrow your search categories to:

You perform some analysis and determine that the most preferred machine is the machine that has the largest value of the formula: 2 * R + 3 * S + D.

The first line of input will be an integer (between 0 to 10,000) indicating the remaining lines of input. The remaining lines will contain a computer name, R, S, and D; all separated by a space.

Example input

4
ABC 13 22 1
DEF 10 20 30
GHI 11 2 2
JKL 20 20 20

The output will contain two lines: the names of the top two optimal computers in decending order. If there are computers of equal value, the computer name shortest in length is preferred.

Computer ABC has a preference value of 93; DEF has 110; GHI has 30; and JKL has 120. Therefore, the output will print out computers JKL and DEF.

Example output

JKL
DEF

The obvious solution would be to simply use .NET’s built-in sort function. Unfortunately, due to the extra restriction for computers with equal preference values, I had to use a lot of IF statements to manually compare and sort.

My solution

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() As String
        Dim preference As Integer

        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)

            preference = 2 * Int(args(1)) + 3 * Int(args(2)) + Int(args(3))

            'redim because the split function
            'resets the array to the number of items (0 to 3)
            'now the forth index stores the current computer's
            'preference value
            ReDim Preserve args(0 To 4)
            args(4) = preference

            'creates a default value to compare to
            If i = 1 Then
                vFirst = args(4)
                vSecond = args(4)

                first = args(0)
                second = args(0)
            Else
                If args(4) > vSecond Then

                    If args(4) > vFirst Then

                        vSecond = vFirst
                        second = first

                        vFirst = args(4)
                        first = args(0)

                    ElseIf args(4) = vFirst Then

                        If Len(args(0)) < Len(first) Then
                            vSecond = vFirst
                            first = second

                            vFirst = args(4)
                            first = args(0)
                        Else
                            vSecond = args(4)
                            second = args(0)
                        End If

                    Else
                        vSecond = args(4)
                        second = args(0)
                    End If

                ElseIf args(4) = vSecond Then

                    If Len(args(0)) < Len(second) Then
                        vSecond = args(4)
                        second = args(0)
                    End If

                    'if current value is equal but length is shorter
                    'than second, take no action

                End If
            End If
        Next

        Console.Write(first & vbNewLine)
        Console.Write(second)
        Console.Read()
    End Sub
End Module

Problem S2: Huffman Encoding

There is an ingenious text-compression algorithm called Huffman coding, designed by David Huffman in 1952. The basic idea is that each character is associated with a binary sequence. These binary sequences satisfy the prefix-free property: a binary sequence for one character is never a prefix of another binary sequence.

The task was to read a Huffman code and a binary sequence and decode the sequence to its character equivalent. My method was to do a simple search through the binary sequence for each of the given Huffman code. Unfortunately, the more that I think about this question, the more I doubt this can work for longer Huffman codes and binary sequences because it only has the prefix-free property; thus, it might be possible to have duplicate suffixes for longer sequences.

Example input

5
A 00
B 01
C 10
D 110
E 111
00000101111

Like the first question, the first line n (between 1 to 20) is the remaining number of inputs (Huffman codes). Each line of Huffman code is an alphabet character, a space, and its corresponding binary sequence (at most 10 digits). The n+2nd line (last line) contains the binary sequence that needs to be decoded.

Example output

AABBE

As I said before, this might not work for other test cases.

My solution

Imports System.IO
Module s2

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

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

        lines = sr.ReadLine

        ReDim key(0 To lines - 1)
        ReDim letter(0 To lines - 1)

        'I didn't use i = 1 to lines because
        'redim must start at 0 index
        For i = 0 To lines - 1
            input = sr.ReadLine.Split

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

        Dim sequence As String = sr.ReadLine
        Dim binary As String 'to store final output

        'loop through every Huffman key
        For j = 0 To i - 1

            If j = 0 Then
                binary = sequence
            End If

            'in the binary, replace the Huffman code
            'with its corresponding letter
            binary = binary.Replace(key(j), letter(j))
        Next

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

Problems S3-5

I tried S3 but I already know that I did that wrong. The rest of the problems were just too difficult at my current skill level to solve.

Conclusion

Well that’s all the senior questions for this year’s competition. I tried my best but I wonder if my best is enough to earn me an acceptance into the University of Waterloo mathematics or engineering department. I just hope I can at least earn a certificate from this year’s competition!

In the meantime while I am waiting for the results, I’m going to get some rest and prepare for next year’s competition.