The British Informatics
Olympiad is a national competition in computing set up in
March 1995, open to pupils aged under 19 and studying in mainland
Britain. This report summarises the first year of the BIO. We
also look at the final stage, the sending of a team to the
International Olympiad in Informatics (IOI), at which team
members won a gold and a bronze medal.
The BIO could not have been completed without our sponsors, Brother and BT, and the many other individuals and organisations who contributed. We would like to thank them for their generosity and support.
Brother International Europe, Brother Holland
BT Education Service, BT Graduate Recruitment and Sponsorship
Department for Education
Christ's College, Cambridge
Department of Applied Mathematics and Theoretical Physics,
Cambridge
Department of Engineering, Cambridge
Young Professionals' Group, British Computer Society
IOI'95, the Netherlands
Antony Rix
I have a clear memory of the 1991 and 1992 International Olympiads in Informatics, in which I took part as a sixth former: of making friends from many countries, seeing new cultures, and taking part in an extremely challenging competition. The last that I had heard of the UK's participation in this was that the previous organisers, the Preston Branch and the Young Professionals' Group of the British Computer Society, had been unable to make it to IOI'93 in Argentina. Once I was told that they had moved apart and were no longer involved, I decided to find out more.
Through a friend from the 1991 and 1992 IOIs I was able to make contact with the manager of the 1995 IOI in the Netherlands, Ries Kock, and set out to organise a national competition and send a team. Backed by my College, I set up the British Informatics Olympiad with the general aims:
By now it was March, and there were just two months left in which to run the BIO. Dr Cyril Isenberg provided a mailing list of schools participating in the British Physics Olympiad, of which he is the Secretary. The Graduate Recruitment and Sponsorship group of BT kindly offered the use of their facilities to produce and send a mailshot to 230 schools and colleges in mainland Britain. Richard Forster became involved, especially helping out in the final stages. Once BT and Brother had pledged their financial support, the BIO became fully established.
Using the other Olympiads as a model, I chose the form of a two-stage competition. After completing an initial programming project (sample problems), eligible pupils enter the first round. This is marked by teachers and the best scripts are sent in for approval. The top students then take part in a second round of even harder tests, from which winners are picked and a team chosen.
Despite the short timescale, 25 schools took part in the last two stages, with a total of 117 pupils entering for Round One. For some, especially the younger entrants, the exam was pitched at a too high a level; nevertheless, several individuals effectively completed it and a total of 47 certificates were awarded. The 14 finalists who attended Round Two faced a gruelling 5 hours of tests, and all did well: it was difficult to choose between them. Their standard was reflected in the team's excellent performance at the IOI.
Antony Rix (Chairman) is starting his final year of M Eng Electrical and Information Science at Cambridge University, where he is based at Christ's College and is specialising in signal processing. He was a member of the British team at the 1991 IOI in Athens, and was re-selected for the 1992 IOI in Bonn, where he won a bronze medal. He also won a silver medal and the Encyclopaedia Britannica prize at the 1992 International Physics Olympiad.
Richard Forster (Secretary) also won a bronze medal in Bonn, and has just graduated in Mathematics and Computation at Trinity College, Oxford. He is staying on at Oxford to take a D.Phil, researching computer security.
In a team together with two other former IOI participants, Richard and Antony have twice won the British Computer Society's programming competition, defeating teams of professional programmers as well as other students.
The 1995 British Informatics Olympiad took place as follows:
Understandably, the short timescale prevented some schools from taking part. With a whole year in which to run the competition this will of course not be the case in the future, and a provisional outline of forthcoming BIOs is:
Many schools expressed interest in a competition for younger pupils, run in parallel with the BIO itself. We are considering possible options for this, for example having a younger section with separate prizes.
In this section we shall discuss the questions set during rounds one and two of the BIO. Because of their length, a full listing is not possible here, but copies may be obtained from the organisers and are on the Internet.
This question required a program to be written to fulfil a very detailed (3 page) specification. It had to read short text messages from the keyboard, filtering them and displaying them; then encode the text using rolling character substitution from a padded text key (precise details of this were given). The final part required the students to work out how to decode the text using a specified string, then program the computer to do this.
A marks scheme was given on this paper, with tasks roughly scaled in difficulty. (Only three people received the final 10 marks for fulfilling all of the question's requirements.) Teachers marked their students' scripts and were invited to submit those above a certain standard for further consideration: this allowed moderation before the best 15 finalists were selected.
Familiarity with string manipulation, text input and output, and basic program control were all tested. The tasks that appeared to be the hardest were sifting through the fine detail of the program's requirements and working out how to make it decode text.
While there are a number of analytical techniques for finding certain classes of magic squares - arrays in which all rows, columns and (optionally) diagonals sum to a given number - these are not studied at school level and only one teacher reported that his students knew of their existence. This question set out to examine how to produce magic squares using computer search.
After some simple analysis, the main tasks required the students to describe an algorithm to find magic squares, consider how it grew in complexity as the size of the squares increased, and look at ways of improving it.
There are several ways of doing this, some more efficient than others; marks could easily be gained by suggesting a simple recursive search and noting that this performs very badly as the problem grows. Some students produced very innovative solutions and at least one actually wrote a working program during the time available in the exam.
This written question mainly served to discriminate between the top 20 entrants, who had completed or nearly completed the programming task.
Both of the problems in Round One were written by Antony Rix
The high standard of the finalists required some very testing questions for Round Two. The hardest of these, this task was adapted by Richard Forster from lectures in the Oxford University Computation course, and was set first to allow it to be marked while the competition was running.
Using parallel computers, prefix addition was considered - given a list of numbers, a 'sum so far' is desired. The question built up from simple examples of serial and parallel addition of lists to producing a 'black box' prefix adder. Although not the fastest way of carrying out prefix addition, the techniques used simplify what would otherwise be a very complex system.
While most of the finalists understood the first two tasks, which dealt with simple parallel systems, the problem became rapidly harder and only a few attempted the fourth and final section. While this might appear to be another abstract mathematical problem, the methods used to solve it have a very wide field of application.
By contrast, this was an extremely open-ended question, and is short enough to be stated here:
You are supplied with a number of representative files from a number of different languages. All languages use the Latin alphabet A to Z; case can be ignored and the only punctuation characters are . , ; : and single space characters separating words. For example, you might have the files FRENCH.1, FRENCH.2 to FRENCH.9, ENGLISH.1 to ENGLISH.6 and so on.
Given a file TEXT in the same format but of unknown origin, how would you go about programming a computer to identify its language?
The applications of such a program are clear; the field of speech and language recognition and understanding is now large and developing rapidly. Nevertheless, it is possible to write a simple program to accomplish this task and several different classification methods can be used. The best answers were from those students who took a step back and looked at what could characterise a language, how this could be extracted from the supplied files, and how this would be used to identify a 'best fit' for an unknown text.
The problem had been proposed (although not used) as a programming task for the 1991 IOI in Athens and was used in a similar (written) form to the above for the 1992 British team selection.
This problem was also adapted from the IOI in Athens, in this case from the first day of the competition itself. After cutting it down slightly, it was used as a basic test of fast programming under pressure: making the right steps, the code could be written in a third of the time available. Several students completed the program after only one hour.
A set of rules were given for placing, in order, the numbers 1 to 25 on a 5x5 grid, in a similar way to a knight's moves in chess. These can be investigated recursively, producing around 500 valid final states from each starting square. The first part of the problem was relatively easy: given the position of piece 1, where can piece 2 be placed? The second part required a recursive program to find the number of permutations and one example completed grid.
Charlotte Rusby (St Paul's Girls' School) withdrew from the team to concentrate on STEP.
All the team members were also awarded cameras by Brother.
The finalists received pens and £10 book tokens.
All entrants who achieved Merit or above were awarded certificates.
The following schools entered for Round One of the BIO.
A number of individuals also responded to an article in the Daily Telegraph, 29 March.
Richard
Forster
The 7th International Olympiad in Informatics took place at the end of June at Eindhoven in the Netherlands. The competition, which hosts the winners of many national contests, attracted over 200 competitors from 52 different countries. It is far from being an exclusively European affair, with teams from as far afield as Colombia and China.
Great Britain is not a newcomer to the event, but having been unable to attend for the last two years it felt like it at times. This year we picked a team of 5 from the 'British Informatics Olympiad', four of whom were able to attend. We flew into Amsterdam, from where we were taken to the Eindhoven University of Technology (TUE), the main competition site.
For the week of the competition, the IOI took over much of the campus. As well as rooms for the computing a hospitality tent was set up, and many of the students were brought in as guides. Accommodation was at the nearby 'Center Parcs' complex. We were there during an unexpected heat wave (the climate is usually similar to our own), so the cool breezes from the complex's lakes and the swimming pool were much appreciated.
Due to traffic, we arrived too late, unfortunately, on the first day to see the opening ceremony. We thankfully made the post-ceremony dinner, where we were introduced to Philip, our guide for the duration of the competition. One of the aims of the IOI is to make friends, and the dinner gave everyone, both competitors and team leaders, the chance to mingle.
The following day, a Tuesday, was spent on a visit to Amsterdam to let people settle in. This started off with a boat trip on the canals, followed by a walk through the city and a visit to the Rijksmuseum. This was the first of two major cultural tours laid on for us, the second being in between the competition days on Thursday.
The second visit, to Rotterdam, gave a chance to see the harbour (the largest in the world), and then a baseball tournament. In the evening there was a reception at the Provinciehuis hosted by the Royal Commissioner of the North Brabant province. This was then followed by a 'surprise' talk by Edsger Dijkstra on the history of computer science.
Wednesday saw the first day of the competition, and an early start - 5 am - for team leaders. There were three questions set for the first day, two computer based and one written. The first question required the competitors to find the smallest enclosing rectangle that four given rectangles could fit into without overlapping. The second question gave a set of prices and special offers in a shop and wanted the cheapest way of purchasing a set of items. The written question introduced the ideas of semaphores and message passing, and asked some simple questions about a system of users and printers.
The questions were well written, with few ambiguities. English is the language used for the whole competition, and there was no need, as there has been in the past, for an English to English translation. Some other teams had more difficulty. The Dutch version of the written question grew from 2 to 7 pages, hardly surprising when the Dutch for 'communication diagram' takes a line and a half to write.
Marking of the questions also went smoothly. This year saw the use of an automatic evaluator, which mercilessly attacked the solutions with a range of test data. Whatever other pros and cons it might have, it certainly made the marking more painless than in previous years. Effort had also been made to divide the marks, splitting each problem into several tasks, so that the previous IOI's catch phrase of 'Zero Marks' was only seldom heard.
The second day of the competition saw a further three questions. This time there was no written one, but one of the problems was interactive: it had to ask questions about the test data which were interpreted by the evaluation program, running on another computer. The more usual type of programming problem simply takes input from a file.
The first question involved finding words from a large dictionary which maximised Scrabble-like scoring rules. The second question involved finding certain types of points on a graph. Finally the interactive program was a puzzle to deduce a network of wires connected to switches. The maximum number of questions that could be asked was specified, while the programs were pushed to this limit by the automatic evaluator, which responded so as to keep the puzzle as hard as possible.
By Friday evening most competitors knew their score for the competition, and were able to sit back. The weekend saw a science fair held at the university, including stalls from all of the companies involved with the IOI. Two world records were made. On Saturday the competitors took part in the largest computer game in the world - 'Hot Balls'. This consisted of 256 Pentiums connected together, and the impressive sight of a wall of 16x16 monitors. The next day saw the world's largest human computer, built out of around 1000 people.
Sunday was also given over to the science fair, but like most teams we elected to stay in Center Parcs to relax. Later in the afternoon we headed to the Frits Philips Music Centre for the closing ceremony.
Although individuals knew their own scores, and the team leaders knew how many people would get each type of medal, we arrived unaware of the medal boundaries. After a procession of speeches all was finally revealed. We received a gold and a bronze medal, with our gold medallist Patrick Smears coming second in the whole competition, and our bronze medallist Justin Santa Barbara narrowly missing silver. Lev Bishop and David Armstrong, our other competitors, both performed very respectably despite missing medals.
The competition was a great success, both for the week's events and the team's performance. Inevitably there were a few hiccups, but thanks to the hard work of the organisation and the guides everyone involved had a wonderful time!
Antony Rix
This report is only a brief summary of what the first British Informatics Olympiad has achieved. While it will be several years before the BIO becomes fully established, it is clear that we have a successful framework for running a national computing competition at school level.
It will also take some time, and a good deal of effort, for the BIO's long-term aim - of encouraging all pupils to take an interest in computers - to be fulfilled. It is my hope that the skills it fosters will be of great benefit to all those who compete, at any level. On a more practical level, the BIO would be doing very well if it encouraged more school leavers to take courses in Engineering or Computing.
This year's rushed schedule probably did not help to encourage state schools, greatly under-represented, to take part. Much could be said about the tiny proportion of girls who entered. Both of these issues are being considered and will be addressed as far as possible. Nevertheless, the high standard of those who did take part shows that British computing has a strong future.