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.
- 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.
- 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!