This year's competition was fairly difficult, especially in the short two-hour period. It was more mathematical in nature than previous years, which some teams of course preferred and some teams disliked. We were very impressed with the general level of knowledge, ability and innovation among the 76 teams. Overall the students showed varying levels of ability, ranging from very good to somewhat creative. The better solutions generally had a better overall structure, with the problem being broken down into smaller problems. There were some solutions that came close to working but were let down in the end by their haphazard style.
As always, Visual Basic was overwhelmingly the most popular language, with 64% of entrants using Visual Basic or some Basic hybrid, the next most popular choice being C/C++ (28%). And, as always, contestants who used Basic tended to suffer as a result. Notably the top eight teams all primarily used a language other than VB. We continue to discourage the use of Visual Basic - candidates seem to worry too much about GUI features rather than getting straight into the heart of the code. As an indication, teams that used exclusively VB averaged 32.9 whereas teams using some C/C++ averaged a much higher 45.7, with teams using (Visual) Pascal typically scoring in the middle at 39.
We would very much suggest to teams planning to participate next year to learn about the useful programming technique of recursion. It proved most valuable in this year's competition, simplifying tasks 3 and 6 greatly.
Average score: 12.7
This question was attempted by almost all teams, with the general method
employed being to read in a string of digits, add the numbers up, convert
the result back to a string, and then test if the length of the result was
only one. This question was generally done well, although some people
got themselves tangled up with goto
statements while trying to handle the
case when the length of the result was greater than one.
One creative solution to this problem was to use repeated subtraction of 9 until the the number was less than 10. You can quickly convince yourself that subtracting 9 from any number will maintain its digital sum. A more efficient method here would be to just take the number mod 9 which would give the same result (though a result of 0 should be changed to 9).
Average score: 10.0
Fairly well handled. The crux of the problem lies in factorising numbers. Most teams had a good feel for how to do this, and made good headway accordingly. The only downfall, which was most probably an oversight, as opposed to bad programming, was to only check the sum of factors of one of the numbers, and not both. We were glad to see there were some very efficient solutions, the best ones checking only until the square root of the number, adding pairs of factors at a time.
Average score: 5.3
This problem, while attempted by many, ended up being harder than most people had anticipated. All correct solutions utilised some form of recursive function call, a sophisticated technique which many would not have been familiar with, and gained bonus marks as well. A number of teams found solutions for the case n=2, but then found it difficult to generalise the solution.
No teams took the approach we expected, which was to work out permutations (a far easier problem) and then go through eliminating duplicates, even though the bonus mark requirements hinted at this approach.
Average score: 4.6
This was a very hard problem, given the limited time, and no team came up with a completely correct solution. An exhaustive search (permutation-based) was necessary for full marks. The most efficient way was to try the minimum number of bags possible, then increment by one until a satisfactory solution was found.
Nonetheless, most teams intelligently approached the task using an approximation algorithm that would work in most cases. The greedy algorithm worked for all the test data we provided, so it gained 14/15 when correctly implemented. These approaches required the programmer to employ nested loops/functions to check through the bags and the list of weights at the same time. Many teams got caught up in these details and hence were unable to get a complete solution, although many teams displayed a knowledge of the overall algorithm required, and were rewarded with partial marks.
The approach that teams took pretty much eliminated the possibility of bonus marks, which was only really possible if the permutation search was used.
Average score: 1.5
We were surprised that no-one followed the expected approach of testing where the point lies in relation to the polygon sides. However, we were pleasantly surprised with a few very clever solutions based on adding up the angles formed by the spokes (if the point is inside, they should add to 360°, if outside 0°).
Another innovative approach was using a graphics library to draw a filled polygon in, say, black, and then testing whether that co-ordinate was blacked in or not. Unfortunately this method was not quite fully correct, because graphics libraries use approximation techniques when deciding whether or not to draw a particular pixel. Nonetheless, it was good to see lateral attempts at solutions.
The one team that used Java utilised the Poly class with its
built-in inside
function that trivialised the matter (though their input was fixed).
Average score: 2.8
This was probably an easier question than several earlier tasks, and it is a pity that very few teams attempted it, presumably simply because it was task 6. Recursive flood fill was the easiest approach. Alternatively, a loop that only ended when no more changes were made could have worked.
Line-based approaches, e.g. based on filling in between asterisks, were present too. Generally unsuccessful, there were one or two very clever ones which behaved differently for an odd or even number of asterisks in a line, and these received high marks.