I’ve just got back from the British Informatics Olympiad finals (they chose the top 14 in the country to take this – I was an experimental error) which took place at Trinity College in Cambridge. Despite a fairly epic fail, I thought the weekend was quite productive and I’ve definitely acquired better skills from the only formal or otherwise training in programming the contestants were (strongly) encouraged to undertake. More photos can be found on my Flickr photostream.
Night shot of housing
As always with such activities, the people there shared many interests, and since programming is (at St Paul’s anyway) an interest few people take vaguely seriously, it was a particularly unique weekend for me in that I could talk about Dijkstra’s Algorithm without getting suspicious sideways glances and a general awkward diffusion of human density away from myself… Pretty much all the people there were doing double Maths and were very much into it, and even at a school like St Paul’s one probably wouldn’t be able to mention the Collatz Conjecture and have every person in the room nod and begin elucidating their own hypotheses on where the proof will (if ever) eventually come from (e.g. graph theory, number theory, computing etc). One of the people who had a big hand in organising and managing the whole affair (Tom), seemed to know a great deal about Physics, Maths and computing and the night before the olympiad he and a few of us had a long argument about string theory, something unheard of even in Physics lessons at school. Tom also seemed to know my maths teacher from helping him set ridiculously hard BMO questions at some point in the past (I think I can just about forgive him for doing that). The atmosphere was also quite singular since geek humour actually worked, and maths and physics jokes got a higher laugh:groan ratio than usual; though I couldn’t help facepalming when, while collecting in papers, Tom remarked ‘all your papers are belong to us’.
I think I probably did get quite a bit out of this whole experience. Since being invited to the finals I’ve been constantly prodded to complete USACO training challenges which are combined with a form of structured training / algorithmic tutorial thing which gives users formal training of algorithms. This training is actually the only time I’ve ever been ‘trained’ in programming and I’d been sort of making things up on the fly since I started programming (in visual basic…) back in Colet Court – I didn’t actually know what a greedy algorithm was until this year, and my understanding of even what algorithms are was still sketchy when I took the BIO for the second time (last year). So by going through a beginners through intermediate algorithms training course was definitely useful for me and I now approach problems more analytically rather than just trying to convince a compiler to automatically do what I would personally do if faced with a problem (no, not give up straight away and watch a film instead). I have to say though that despite its utility I acquired a few bad habits from it. Since for each assignment infinite attempts are allowed, I tend not to actually test programs against anything other than sample data and submit it, hoping something that can solve a specific case will probably work with all other cases. Inevitably it tends not to work first time and rather than sitting down and debugging it, I take the test data and just try to make the program work for that by doing silly things like making loops slightly longer or incrementing variables by 1 randomly. USACO helpfully also provides the full answers for test data. I have to say though that the grading system on USACO is impressive – after you submit a solution the backend code automatically compiles and runs the program for each test case and grades its answer. Inspired, I’ve now got something vaguely similar set up on my Debian server (albeit requiring both FTP and SSH connections to sort of do everything manually).
Another thing I’ve always wanted to do was learn C++ as every linux package seems to require compilation with g++, so C/C++ seems to be the language to learn. Since the BIO Finals required code in C/C++ or Delphi (that nobody used, surprise surprise) I was forced to learn a new language, and after discovering the awesomeness of pointers, I have an incentive to endure the confusion and use some really cool programming features (at the risk of corrupting random critical data in the system memory).
And as always with a visit to Cambridge, I got to see more of the college and living quarters. I have to say, the Corpus rooms were more spacious though assuming a specific comparison is representative of a more general comparison would be displeasing to my stats teacher.
And of course since the BIO is sponsored by Lionhead Studios (gaming company) we got to meet a representative and should find obtaining work experience there much easier.
So anyway, here’s what I remember from the itinerary:
Erroll and I arrived at Trinity only to be told we had to be at the porters of Burrell College on Grange Road, which is somehow related to Trinity. After a bit of a trek we arrived, Pauline-style, fashionably late. We were shown our rooms, were provided with food and were shown the computer rooms where we got used to our environments. It was actually a very simple question on summing squares repeatedly (up to 2^63 times) – all we had to do was notice there was a repeating sequence – but the unfamiliar environment and unfamiliar method of file input (fscanf in <stdio> as opposed to fin >> in <fstream>) made me do all sorts of stupid things. I think after three months of USACO challenges in C++ I think I still prefer C# / Java as languages. Perhaps it’s got something to do with compilers (my 2003 MS C++ compiler at home goes kaput randomly).
The brain uses an insane amount of energy when working hard and doing olympiads was even suggested (as a joke) as a means of weight loss. For this reason an awesome breakfast was bestowed upon us, consisting of baconey, eggy, toastey goodness. The morning papers were both written, the first being on Turing Machines and the second on emotion/sentiment detection in text. This was actually probably the most enjoyable part of the contest – the questions on turing machines were a bit like a mix of maths, logic and electronis (involving truth table like things and train track systems etc). It was also the only bit I could actually seem vaguely competent doing – an education in maths and electronics probably helped me.
The afternoon was when the hardcore competitioning kicked in with a whopping five-hour paper consisting of four questions (the best people completed two questions). I’ll talk about those later, but I failed quite epically, only managing to write a program to solve a question for about half the test data. It also transpired I’d spent all my time on the hardest question, and that although I saw immediately an algorithm that Dr Forster said worked, my implementation was total crap. Later that evening I managed to think up a linear time program to solve the same problem which when I mentioned it the next morning was apparently the best solution Dr Forster had thought of. I still blame C++ :P
After the olympiad I attempted to take some night photography with a tripod which is apparently banned. Oops. We all then went to dinner at Ask and got quite stuffed up before being asked to eat more in the chill room afterwards.
Today was mostly free time in which Erroll, I and another person we met spent our 2 hours of free time pulling newspaper, broadband adverts and IR spectra printouts out of a pool table in an attempt to get the balls out. Our efforts included using mobile phones as endoscopes to get a better view of the inside of the machine, using wire coat hangers as hooks to reach the newspaper and peering inside the machine to aid our end. We were eventually thwarted as we concluded our over-zealous table tilting had resulted in the balls falling out of the mechanism entirely and ending up unretrievably on the bottom of the table. For future reference: pool table lock picking doesn’t work with coat hanger wires.
After an inventive method of going round (in three dimensions) a gate without a keycard I and a few others got to the main Trinity college. The tension was apparently high as they announced the IoI competitors though I didn’t notice; my expectations were clearly low as I had just organised three weeks’ work experience with Microsoft at the same time as the finals. What was nice though was that we got very cool 4GB memory sticks with ‘British Informatics Olympiad’ on them, and we were issued with compulsory free games and ‘Introduction to Algorithms’. I already had the book and had in fact brought it to the contest in order to seem vaguely intelligent with no real intention of looking at it.
I’ve put thumbnails of scans – click to enlarge. I cut out my retarded scribblings.
This is the one I half did, and also the hardest. You’re given a cross section of a polygon and are supposed to divide it into triangles using only given vertices. In the question the polygon is the cross section of a cave tunnel…
My initial (and apparently correct) thought was to cut off all the bits sticking out of the polygon (i.e. turn them into triangles and ignore the outside points) and end up with a convex polygon and subsequently just a triangle in the middle; sort of repeatedly going round the polygon chopping off bits. My second (and apparently better) thought was to go from left to right joining up points, an algorithm that runs in linear time.
This is apparently the easiest question: a river (= straight line) of up to length 2^31 kilometres (the unit was some amusing invented thing but I can’t remember what it was) can be split up in one of up to 1000 (=n) ways into n unequal segments (= up to 1000 different sections using up to 1000 different partitions). The question was to split it into n segments so that each different segment is a segment described in a different partition and there’s no overlap of partitions. OK that’s a crap explanation – the scan does it better.
I didn’t actually look at this which is a pity – it was the easiest. When I looked at it before going to bed that night I managed to come up with an algo straight away which would have worked in O(n^2 ish) – the biggest case would have taken about a second to run. Pity I saw 2^31 and immediately moved on when actually doing the competition.
All work and no play
The scan says it all. It was a really annoying question because I started working on it about an hour before the end. I wrote an efficient O(n) algo for finding how many ways there are of making n in such a way, had an amazing pascal’s triangle/combinatorics thing going, and was about to write it when I realised it all got screwed up by the blocks only going up to 10. Unable to repair my program, my final submission only worked up to n=10 (needs to work up to n=64). I might also have forgotten to change the output method from console to file output. Meh.
I couldn’t think of an efficient way of doing this (not even in the evening though I was very sleepy by then) and am certainly not going to attempt it again until I have lots of free time, i.e. summer. This was the second hardest.