After competing in the national round of the British Informatics Olympiad, I made it through to the final, and came 5th in the UK. That made me the reserve for the team which represented the UK at the International Olympiad in Informatics. The results are on the Olympiad's website.
The first round
The first round involved papers taken by selected sixth formers in Computer Science and Mathematics A-levels, held by participating schools. It was a three-hour paper, taken in exam conditions, with around 350 pupils entered from 71 schools and colleges.
It was a set of LeetCode-style questions and problem solving: finding amicable numbers, programming Conway's Game of Life, and fitting dominoes together. The first round paper is online too.
The national UK finals
The finals were held at Christ's College, Cambridge, and it was my first opportunity to visit this beautiful city, before coming back to study Mathematics and eventually receiving an MA in Mathematics & Computer Science (Churchill 1999). The best fifteen from the first round were invited. The papers are online here.
That's the UK winners outside the college, with the organisers, Antony Rix and Richard Forster.
The finals took place over the course of three days, from 12 to 14 April 1996, and involved both timed practical tests and essays. The Saturday was the competition: two written questions in the morning, then three programming questions in the afternoon, with three hours to solve them. As soon as a program was written it was handed in and tested on unseen data, and you got a chance to change it if it failed.
Trees, Forests and Heaps of leaves
The first written question led through data structures that were new to most of us. It started with binary trees and binary search trees, and how many comparisons it takes to find a number in the shallowest and deepest trees of 8 and 15 nodes. Then binary heaps: building one, adding a node, and joining two heaps together. Then binomial trees, defined recursively, and binomial heaps, which are forests of them: drawing B4, counting the nodes in Bn, and joining two binomial heaps.
Random Numbers
The second was an essay, with the whole question in one paragraph: you're given a file which you're told contains random bytes, so how would you go about testing it? Anything relevant could go in, from algorithms to time and space considerations.
Connecting Towns
The first programming question was a list of roads between pairs of towns, each with a five-letter name, ending with XXXXX. The program had to say how many towns there are, and how many disjoint sets of them, where you can't get from one set to another by road:
AAAAA BBBBB
CCCCC BBBBB
DDDDD EEEEE
XXXXX
5 2There could be up to 250 towns but several million roads, and due to the carelessness of mapmakers, town planning committees and the Pentium floating point bug, the same road could be listed more than once.
Selection
The second programming question came in two parts. Part one gave an n by n array of numbers and a number x, and the program had to find n occurrences of x, with one, and only one, in each row and column, or print Impossible.
Part two was only handed out once part one had been solved. It was the optimal assignment problem: n candidates, n jobs and a measure of how suitable each candidate is for each job, and the program had to give every candidate a job so that the total came out as low as possible.
The international finals
The international finals, the 8th International Olympiad in Informatics, were held in Veszprém, Hungary, from 25 July to 2 August 1996, with 220 contestants from 57 countries. The British team was Andrew Cooke, Justin Santa Barbara, Michael Anderson, Alex Evans, and myself. The team took home two bronze medals, won by Alex Evans and Michael Anderson.