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++.
- Simple Arithmetic
Senior topics (in addition to junior topics)
- Tricky Loops and Arrays
- Graph Theory
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.
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:
- RAM, R (integer between 1-128)
- CPU, S (integer between 1-4000)
- Disk Dive Space, D (integer between 1-3000)
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.
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.
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.
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.
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.
As I said before, this might not work for other test cases.
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
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.
- Problem S3 involved complex decision making and grouping (although this is simple, I ran out of time by the time I realized this algorithm).
- Problem S4 requires Dijkstra’s algorithm or something similar to find the shortest path of a graph.
- Problem S5 requires finding the shortest path in a binary tree graph (at least this is what I think the question is about).
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.