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