UCT Algorithm Circle

After much grinding away, we had our first class of the UCT Algorithm Circle this past Thursday. We invited 32 of the most talented school kids we could find in the Cape Town area and invited them to some training. We're also slowly inviting kids outside of Cape Town to train online. We're teaching them from the very basics of programming right through to the advanced algorithms and data structures required for the IOI.

For the first class, we introduced the basics of Python. We were amazed at how quickly the kids caught on. After a 20 minute lecture and 60 minute practical session they were understanding operations, variables, stdio and more. The majority of these kids are in grades 9 and 10, and amazingly half are girls.

If things continue at the rate they're going now, this could provide a serious boost to our IOI results in upcoming years. We've always been welcome to the idea of training a wider audience, but finding the talented kids and getting them interested has always been a brick wall we couldn't knock down. This time though, collaboration with one of the people involved in the teaching kids for the IMO has seriously helped change all that.

To see the kids we have, just check out some of their introductions in this thread to see what they're capable of.

Juniors in the South African Computer Olympiad

A concern I have always had with the South African Computer Olympiad (SACO) is the lack of juniors (grades 10 and below) making it through to the third round and eventually the International Olympiad in Informatics (IOI). A glance at the SACO winner archive makes this quite evident. The only person that has won a medal in grade 9 or below (and hence stood a chance of making the IOI) was the well-known Bruce Merry.

Why do we have this problem? The obvious problem is that IT is only offered from grade 10 and it's nearly impossible for someone to pick up enough within those first few months in time to make the final round of the SACO. However, it is quite common to get those who taught themselves programming in the earlier grades yet only make the final round in there last one or two years. Vastly different situation to the Maths camp, where grade 8s and 9s are a common occurence.

Today we made a giant step in improving the situation. It goes back to little over a year ago during the final round of last year's SACO. We had three juniors (grades 8-10) joining us on-site for a junior competition in which they couldn't win anything. One of these kids did so well on the first day we invited him to write the senior paper the following day. Unfortunately as he only had a single day's worth of points to stand on, it was near impossible for him to win a medal and a place in the IOI training squad.

This gave us reason to invite a larger number to participate in the training. Due to a strictly worded rule, only the medallists could compete for a place in the IOI. Along with this and our limited budget we had to place several restrictions on those outside the top six, but we invited the next six best non-matrics to attend the training camps of which five accepted the offer. Things ran very well as the larger squad resulted in more discussion as well as pushed the top guys to perform better. Yet still, there was this lack of competition amongst those we called the squad++ as they had nothing to aim for but goals they set themselves.

For this year's final round the rule in questioned was worded more openly. The final round this year was the most competative from recent years and yet we still ended up with a new grade 9 and new grade 10 just missing the medal positions! It's been a long month, but today they were finally accepted into our first ever larger-than-usual squad. We now have ten highly competative kids in our squad, with the distribution being three grade 12, five grade 11, one grade 10 and one grade 9. All are elegbile to make the IOI team next year, and should Charl who's the one in grade 9 make the team he will be our youngest team member after Bruce! Now that they've shown us what they can do it's up to us to train them and make sure we continue to work on the great results.

I have some other plans to further increase the junior numbers. Now that we have these guys as role models it will be easier to catch the attention of other juniors and I don't plan on missing this opportunity. I already have the names of some current very capable grade 8s and 9s wanting to take a shot at the SACO next year. It's going to be a fun and interesting year to come!

South African Computer Olympiad 3rd Round 2008

The final round of the South African Computer Olympiad took place this past weekend. This was the first year it's been run since Bruce and Carl left UCT at the end of last year. While we sorely missed them and noticed how much we had previously taken for granted, we managed really well.

There were 16 contestants, 7 of which had gone through squad training over the past year so we had a nice split between newcomers and oldies. Two months ago I setup a Google Group for them to ask questions and discuss the 3rd round. Given the large number of oldies this turned into an exceptionally useful discussion forum with the oldies asking advanced questions which in turn gave the newcomers a target to aim for. They could see what was out there and it really boosted their urge to learn. Over the past two months there have been nearly 400 messages posted!

The contestants all arrived on Friday evening, when we had an introduction session and went through the rules and environment. This was followed by the classical pizza-on-campus supper. After having helped most of them through the forum I was anxious to meet the new guys, but the swarm of unrecognisable faces threw me off guard, especially as we were running around frantically sorting out a couple last minute things. Fortunately I was able to get to know most of them over the weekend.

On Saturday morning we started them off with a practice session so they could become familiar with the environment. One advantage of having the forum was that we also for the first time got them all to use the handing system before arriving, even going as far as providing a time-constrained practice contest for them. This meant that most of the time was spent getting familiar with the setup of the PC's, which wasn't much to get used to and so they got bored very quickly (bored for these guys means they were coding up quite advanced algorithms we have never taught them). The only issue we had was with Dev-CPP setting folders to read-only and saying it couldn't save, which we eventually fixed.

While they went off for lunch, we setup the lab for the start of the first round of competition. A first for this year again is that we logged them in and pre-loaded all the IDE's and such (the network is so slow we have scripts that copy everything onto the local disk), which took more time than we had anticipated so most of us got cold food. We're supposed to have an admin account that can wipe their accounts clean, but the network admins messed that up and it's one of few things we forgot to test beforehand. This meant we had to wipe the accounts manually.

The first round of competition started well. We had given them two easier problems and a challenging graph theory problem. Our goal was to get them a good starting score and letting them have sufficient time to have a real crack at the nastiest problem of the weekend. The plan worked well, besides us underestimating the difficult of the second problem. The scores were very high, with the average for this single day higher than the average over both days last year. While the problems were slightly easier this year, the major reason for the difference was the much stronger contestants. We were seeing the results of a larger training squad over the past year combined with the amazingly fruitful forum.

There was one single issue we've had haunting us for about six months now, but which has affected us very little prior to this weekend. One of our grading servers keeps on crashing, and we only recently discovered that a CPU error is resulting in a kernel panic. Alongside this the hard drives our only other grading server were stolen (long story!) and with everything else we were working on we never got around to finding new drives and reinstalling in time (we got close though!). With the introduction of detailed feedback and grouped test data increasing the load on the grading server it starting crashing a lot more frequently, to the point where we had to be careful and coax it along, rebooting it a number of times. Being South Africans we quickly improvised, using a red packet of sweets to indicate the server was down and a green packet when it was up.

Once the first round of competition was over we started a problem discussion lead by the problem authors. We describe the expected solutions, which is a great learning experience for the contestants. While that was going on we started the evaluation of the day's submissions. Unfortunately the grading server really started freaking out under the load we were putting it under. Combined with many more test cases than we previously used due to grouped test data, the evaluation took over two hours! When we finally got the marks to the contestants they were mostly all very happy with the higher-than-usual marks.

We then went out for supper to the Spur where I had a very chatty group at my table. It's always wonderful have conversations with them about their experiences in school and in the competition. It's the best way to discover what areas need improving and potential solutions to them. It's amazing hearing stories of how students at schools without Computer Studies quite randomly happen to come across the SACO, and also quite sad to think of all those who miss out.

Sunday morning was an early one for us as we had to prepare for a 09:00 start. While the problems were busy printing Keegan and I moved the grading server closer to the aircon in the hope that it would reduce the frequency of crashes. We then went down to the lab to log everyone on, clean the accounts and do some other stuff to make the contestants' lives easier. We started a few minutes late again, but it went very well from there on. We had very few crashes of the grading server, helped in part by further decreasing the load we put on it. So it was a much more peaceful day for us coaches (this just half of us):


The problems for the second round of competition were considerably harder and we noticed the effect from early on. The easiest problem was very easy to get a wrong answer on as it looked like greedy was correct. Fortunately most of them quickly moved onto the other two problems, one a competitive data problem and the other a quite challenging greedy problem with a 70% Dynamic Programming solution. The race for first place was extremely tight up until the last half hour when the eventual winner zoomed ahead. It's always fascinating watching the rush of submissions coming in at the end, which can sometimes shuffle things up quite significantly.

Evaluation of the second day was much, much faster due to several reasons. This meant that we had the results ready and printed immediately after lunch. The contestants were very anxious to see their results and as much as we try keep them from discussing them within a few minutes nearly everyone knew who had come where. The medal winners were:

1. Francois Conradie winning R36,000
2. Robert Ketteringham winning R24,000
3. Kosie van der Merwe winning R24,000
4. Haroon Moolla winning R2,000 (used Java)
5. Schalk-Willem Kruger winning R12,000
6. Michiel Baird winning R12,000

The final Python prize of R10,000 went to Gwylim Ashley. The results were extremely strong this year and the competition very tight. Just looking at how this years IOI contestants Robert and Schalk-Willem were beaten by others shows how hard everyone worked for this competition. The results were also nicely separated with no positions at the top very tight, and the scores at the lower end weren't dismally low as they have often been in the past (another sign of how strong the competition was!)

Some random statistics about the medallists: Kosie is the only one not wearing glasses. Four are Afrikaans-speaking (reading Afrikaans code isn't fun, fortunately only Francois does this!). Half are in grade 11 and can return next year, including Francois. Robert and Schalk-Willem participated in the IOI this year, and Haroon was invited but withdrew. Besides Michiel, all made the final round last year.

Rondebosch Boys' High School has had a strong performance in the SACO over the past years. Being the first Bosch boy to make the final round and leading the Scientific Committee, this makes me extremely proud. This year the boys didn't disappoint, grabbing 2nd and 4th places as well as one non-medallist position. Here's me with the Bosch contestants (Haroon, Robert, me, Roland):


The Western Cape as a whole has also produced the largest number of final round participants in recent years. This year we trumped big time though, with 10 of the 16 contestants. Of the rest, three were from Gauteng, one from the North West and one from Namibia. Why not share that fabulous Western Cape photo then? One of the Cape contestants is missing from this photo.


And while I'm at it I might as well give the lonely out-of-towners some love and care :)


Left to right: Divan, Heinrich, Graham, Bennie, Sheldon, Michiel, Kosie, Haroon, Gwylim, Francois, James, Roland, Charl, Schalk-Willem, Robert

After the photo session they had an opportunity to check on their results and raise any appeals. Fortunately we had none, which is always a great sign and a relief. Once that was over we could rest in peace knowing that the five weeks of hard work we put into the problems yielded no problems besides two minor clarification requests.

Very quickly the attention switched to Open Arena, yes they start earlier every year! Some day we need to start a new game, this is getting boring Ben. Graham also tried working on a visualisation tool for the data problem, but when I saw him trying I quickly told him us coaches already had one and I showed it to them. After there hour of fun we had pizza and watched some Fawlty Towers and Thin Blue Line.

Monday was their last day. It was supposed to begin with a tour of the Center for High Performance Computing, but due to the political situation in the country and the resignation of the Minister of Science this was cancelled at the last minute. We couldn't find anything to replace it in time so they had a late morning and arrived on campus at 12:30 when I took them for some campus food. It was another opportunity to have some good discussion time with them.

At 14:00 they had an hour with Michelle Kuttel, student advisor at UCT. She went through the Computer Science streams and courses at UCT as well as touching on a few other areas. I then took them over to the Robotics Lab where one of the engineers gave them a tour of the lab. The tour of UCT ended with a visit to the Virtual Reality Room where they were shown some demo's of current and past masters/phd projects.

At the end of it all it started raining and they needed a lift down to the bed and breakfast. Fortunately two of the other coaches were available to help with lifts, but the rain proved an interesting challenge: how to get 13 people down to the B&B using three cars parked in different parking lots while getting the least wet. After getting them all down there to prepare for the awards ceremony, we had to get them all to Kelvin Grove. Fortunately we were just able to squeeze in a single trip there as opposed to the planned double trip.

It was the first time I had been to Kelvin Grove and I was very pleased with it. I was also very happy to see my old headmaster from school attend the awards ceremony for the first time. This was the first time I can even remember talking to him. He was most impressed with the continuous success of Rondebosch at the SACO. Prof John Webb was also a surprise to see, he heads the Mathematics Olympiad. I also got the opportunity to meet Bennie and Michiel's parents, two of the top newcomers. There were many other people I met, but to list them would be silly as I'd miss out on so many.

The awards ceremony was very formal as usual, with guest speakers from Standard Bank and Microsoft. Fortunately they weren't all that boring, but one or two did drag on a bit long. When we finally got around to the announcement of the results it all flew by so quickly. It was great hearing such positive feedback from the contestants and their parents. Before I knew it, it was over and people had started leaving. I even missed out on the now mandatory official Rondebosch photo.


And that's the end of the beginning. Yes, now we just need to select the training squad (medallists are already guaranteed a place in the squad, but we're hoping we can invite more). We then put them through a rigorous training process which we use to select four of them for the International Olympiad in Informatics to be held in Bulgaria in August 2009. I look forward to the year ahead of working with this great bunch!

Huge thanks to the other members of the Scientific Committee who helped make this one of the smoothest SACO 3rd rounds I think we've ever run. Max helped out a lot with the general admin as well as setting a problem. Keegan took on a lot of the technical work, as well as taking over Harry's problem. Ben organised the junior contest, with some help mostly from Timothy, Julian and Richard. Richard was great at proof-reading the problems and being very nit-picky about them. Migael took on the mission of setting the data problem and helped out a lot over the weekend. Harry in setting his lovely problem, but forcing me to rewrite the problem text. Mark, the new addition to the group helped me set the easy problem. Nicholas, Bruce and Carl also helped out a lot with checking the problems and all of them are far away so they all helped out online only. Tamara was also the first beta tester we've had, a new idea picked up from the IOI. Michelle and Peter helped with some last minute proof-reading. I hope I never missed out on anyone. :)

South African Computer Olympiad Online Contest

Back by popular demand! :-P For the second time we will be running an online version of the South African Computer Olympiad and we would like to invite anyone who is interested to take part. The SACO is an IOI-style contest run over two days. The contest will run

Saturday 27 September at 13:30 to 18:30 SAST (11:30 to 16:30 GMT)
Sunday 28 September at 10:00 to 15:00 SAST (08:00 to 13:00 GMT)

We will also run a Future Stars division which will consist of easier problems targeted at, but not limited to, juniors. For an idea of the difficulty level of this division see the problems from last year at http://olympiad.cs.uct.ac.za/old/saco2007/

Register now at https://olympiad.cs.uct.ac.za/contests/saco-2008/?page=register (accounts from one of our previous contests should still work)

More information is available at http://olympiad.cs.uct.ac.za/online-contest.html

Looking forward to challenging you guys! ;-)

South African IOI Team 2008

Three weeks ago we had our final training camp before selecting the South African team for the International Olympiad in Informatics. We experimented with extending it by a day to allow for more presentations and have group problem tackling sessions, which worked out really well.

Shortly after the camp we had a meeting to select the team. The team for this year's International Olympiad in Informatics in Egypt is:

1. Haroon Moolla
2. Mark Danoher
   
3. Saadiq Moolla
   
4. Schalk-Willem Krüger

Yes, Haroon and Saadiq are brothers, which is a first for the South African team. It is also a first that we have two members from the same school, which I am proud to say is my school -- Rondebosch Boys' High School. No, I did not rig the results. ;-) In fact the two that lost out on being selected were also from Rondebosch!! What is also great to see is that Schalk-Willem is only in grade 11 and so therefore has the opportunity to attend three IOI's.

The IOI this year takes place in Cairo from 16-23 August. I will be attending as deputy team leader along with the team leader Peter Waker.

The second round of the SACO takes place at schools across the country in just 5 days (30 May). If you're one of the contestants be sure to read this page I wrote for information on how to prepare.

SACO Online Contest

The second training camp for the South African IOI squad is coming up in a weeks time on the weekend of 2-4 May. This will be the final round of training and competition before we select the team for the IOI in Egypt.

As we've done in the past, we are continuing to offer the problems in an online contest that will be run simultaneously. You are all welcome to participate. The contest page and place to register is:

https://olympiad.cs.uct.ac.za:8082/contests/camp2-2008/

The times are:

• Friday 2 May at 13:00 to 18:00 SAST
• Sunday 4 May at 08:30 to 13:30 SAST

Languages accepted are C/C++, Pascal, Java, Python and Haskell. If you have any clarification requests or other queries, email them to online-contest@olympiad.cs.uct.ac.za.

And while I'm at it, there are a couple other really good contests coming up soon. The IPSC on 24 May is a team of 3 contest with no limits on computers used or programming language. The problems are typically very mathematical and some rather interesting and unusual problems creep in.

The there's the ICFP Contest. Yes, that's the one we came 2nd in last year! Things weren't looking so hot for this one as there was a long period of silence as to what was happening with the contest this year. We were concerned in particular because we had offered to host and received positive feedback initially, but then the organisers went mute and we never heard from them. Anyway, it's being hosted by John Reppy (University of Chicago) and Tim Sheard (Portland State University) this year (from here), although we don't yet have the dates. As soon as we have them we will know who's available for our team. Here's hoping it's a smashing contest this year! If you look around you'll see that John hosted the 2000 and Tim the 2002 ICFP Contests...interesting!

SACO Training Camp One Online

Making the SACO final round and the online training camp available to the general public has proven rather successful, so we're planning on continuing to do so indefinitely. We've been getting lots of participation from TopCoder members, however, we'd really like stronger participation from South Africans. So if you're a South African reading this and are interested or know someone that might be interested please read further.

The first training camp of the year is being held in two weeks time over the weekend of 23-24 February. We'll be holding it online during at the same times as the on-site contest:

• Saturday 23 February at 08:30 to 13:30 SAST
• Sunday 24 February at 09:00 to 14:00 SAST

To participate, all you have to do is register over here:

https://olympiad.cs.uct.ac.za:8082/contests/camp1-2008/

If you have already registered for a previous contest, then you don't need to re-register as your account will carry over to the new contest. The coaches will be on IRC, in #saco on the FreeNode network during the contest for any potential issues that may arise. To see what type of problems to expect, have a quick look through the problem archive.

SACO Online Camp

This is rather (very) late notice, but starting at 11:00 GMT (13:00 SA time) tomorrow (Saturday 15 December) we will be hosting the first of several training camps to select the South African IOI team.

We're continuing on from the SACO and opening it up to the public in the form of an online contest, so you're all welcome to join. We'll be accepting submissions in any of Java, C/C++, Pascal, Python and Haskell. Haskell is an unusual one on the list -- this is the first time we'll be making it available so we'd love to see some FP gurus show us what they got! The contest will consist of three problems and you'll have five hours to solve them, followed by an online discussion via IRC.

Registration and further details is available here:

http://olympiad.cs.uct.ac.za/contest.html

On a related matter, we recently expanded the size of our training squad from six to twelve. The training has always been limited in the past to the six medallists from the SACO. This year we've invited the top six non-matrics outside the medals. Unfortunately they are not eligible to make the IOI team, but we will be trying to change that for next year. The goal is to catch the good ones at a younger age, which is what the Mathematics Olympiad is already good at doing. It's also another reason why we're opening up these contests to the public.

New SACO Forums

Us organisers of the SACO have been very busy discussing ways to expand our training program beyond the top six. Up until now we have taken the six medalists, trained them and selected four from the squad to form the IOI team. A lot about what I'm about to discuss is still a work in progress and may well change. I'm also leaving out plenty details to prevent this from backfiring.

As a first step, we now have a new forum board which we hope will gather together a community of SACO participants, be they future, past or present. We will use this as a means to expand our knowledge from the current squad of six, out to anyone who's eager to learn more.

Although we're still working on polishing up the forums, you can start registering here:

http://olympiad.cs.uct.ac.za/forums/

It's open to anyone, but the people we're looking to attract are those wanting to learn more about computer science than what's offered at school. If your school doesn't teach programming, come join! If you're too young to start learning programming, but you want to learn to program early, come join! If you find what you learn in computer classes at school too easy, please come join! If you're a school teacher and are involved in the SACO or want to get involved (by this I mean getting your students participating), please join!

We're working towards an event pretty much like the UCT Maths Circle, where top school students get invited to one of two groups. There will be a Programming Circle where Python will be taught to those either learning to program or wanting to further their programming skills. Then there will be an Algorithm Circle for those who are ready to learn about all the algorithm goodness. Want to learn about search techniques, graph theory, dynamic programming and much more?

This year we ran the SACO as an online contest open to everyone. We got such positive feedback and we've realised that it doesn't require much additional effort. We are therefore strongly considering making all our training camps and future SACO's available to everyone online. Hopefully this will attract some locals as well and better prepare them for the SACO, eventually giving us a better IOI team.

There's plenty more we're discussing, but that should keep your mouths watering if you're interested in getting involved. :-P

Rondebosch Owning SACO

Rondebosch Boys' High School just rocks! When they do well at something, they really do well at it. The SACO is one of those things they are getting better and better at. Just like UCT are getting better and better at the ACM ICPC and the likes.

The results were announced tonight at the awards ceremony and I don't think many people foresaw such a dominance from Bosch. Mark Danoher came first, but that was kind of expected since he was the only member of this year's IOI team that got another chance. The next four places where swiped by the four Bosch contestants! The last medal went to a grade 10 who's the youngest medalist we've had for a while - possibly even since Bruce!

The top six and the training team for next year's IOI in Egypt:

1. Mark Danoher
2. Saadiq Moolla
3. Haroon Moolla
4. Raeez Lorgat
5. Robert Ketteringham
6. Schalk-Willem Krüger

Left to right: Schalk, Robert, Raeez, Mark, Saadiq, Haroon.


The way things are looking now, we only need Mark to fall ill and we're on target for an all-Bosch team. :-P It's strange looking back and thinking that just four years ago I was the very first finalist from Bosch and that since then they(we)'ve had such a strong showing with this Charles and now this bunch. Brock also tells me there are some grade 10's who could make an appearance next year, so this isn't just a once-off fluke.

What really excites me is that we Haroon and Robert are grade 11 and Schalk is grade 10. So we could have some continuity with them making the team more than once (or at least training), which is seldom the case.

Over the past seven-eight years Bruce and Carl have pretty much been the reason for SACO's vast improvements. They brought the SACO from manual evaluation to fully automated evaluation, much like the IOI runs now. To do this they put in one hell of a lot of work into an evaluation system that now runs so smoothly and is so effective that it's difficult thinking what it must have been like back in the dark ages (before I was around). It's difficult summarising all their contributions.

To put it bluntly, Bruce has already submitted his PhD thesis and Carl is almost done and both with be leaving us come the end of the year. Along with Donald (see below), we will only realise the full impact of the loss come their departure. I've been creeping into their roles over the past four months or so and I was the "chief whipper" for the SACO this year, with Bruce and Carl taking more of a onlooker role so that I would be prepared for when they leave.

It's a tough role to fill and I've therefore been recruiting some new helpers. Next year, however, I've heard we will be getting a number of this year's SACO finalists into UCT next year so we should manage just fine. If you're one of the finalists and considering where to go - just remember what I told you about UCT dominating in the college contests. :-D

I can't wait to get cracking with the training of our new youngsters! Who will be going to Egypt next year? Right now, no-one is guaranteed a place. Who? WHO? Nothing's confirmed yet, but we might be inviting one or two additional finalists to the training. They won't be eligible for the team though - thank the blinking rules for that. :-(

And now for something completely different:

The behind-the-scene men! Left to right: Donald, Carl, Migael, Max, Keegan, Bruce, Marco (and there are many more!)


Scientific committee and medalists:


The set is incomplete without a photo of our winner on his own. Congrats Mark!


Donald Cook. The more I think about it, the more I realise how much we're going to miss him. He retires to Bredarsdorp at the end of the year.


I've uploaded all my photos here.

SACO is...Over!

The SACO just ended this afternoon and while the results are still secret I can tell you this year's bunch is looking good! We had 22 participate in the open round and three in the future stars. It was also our first attempt at an online contest with the same problems which drew in over 100 registrations.

The questions (available here) were really nasty this year. As if we didn't clobber them enough last year, a fair number of the contestants were returnees from last year. Gwylim Ashley did so well in the first day of competition in the future stars (beating several seniors even when only considering his mark for the single problem overlap between the two categories) that we did a first by offering him the possibility to move to the open category for the second day.

My old school, Rondebosch Boys' High School, had four contestants in the open round and one in the future stars. While I can't tell the results they did astoundingly well. Go BOSCH!! It does help when you have three Moollas to encourage the guys. :D

The awards ceremony is tomorrow evening, after which I'll be posting results. The top six get medals (one gold, two silver, three bronze) and some prize money for themselves and their schools. The top six Python contestants get a super wad of money ranging from R30,000 for 1st place to R10,000 for 6th place, all thanks to Mark Shuttleworth.

A couple shots from the first round of competition:



And the obligatory pizza stack:


The interest in Open Arena is growing exponentially year-on-year, with more than half of the contestants and coaches playing in a single flag capture:


And finally, the frantic discussions to find out how the $%#& to solve my problem. :-P


For more pictures, go here.

SACO: All Ready To Go!

A group of twelve of us have been preparing the problems for the final round of the South African Computer Olympiad over the past month. We've spent many hours proof-reading the problems and writing over 100 check solutions to make the problems as polished as we possibly can. We are finally ready for to hit the big red button, getting the show underway.

If you're a contestant this year, best of luck to you and I'll see you tomorrow! If you're not, however, you can still compete. I announced our first ever online contest here, but this deserves a reminder. Registration is open and full details can be found here. The problems in the main event are very challenging, so if you're not used to this level of competition I recommend trying the junior contest.

Last I heard the registration numbers are fairly good, although we'd love to see you join in as well. The probability of us repeating this in future years is directly proportional to the numbers and hence its success. If anything, our Monty Python theme (with Python being a key language thanks to Mark Shuttleworth) is alone a reason good enough to participate in the fun!

South African Computer Olympiad Online Contest

In the words of Bruce Merry:

For the first time, we will be running an online version of the South African Computer Olympiad, similar to the way this year's IOI was run as an online contest, and we would like to invite anyone who is interested to take part. The SACO is an IOI-style contest run over two
days. The online contest will run

Saturday 15 September 13:30-18:30 SAST (11:30-16:30 GMT)
Sunday 16 September 10:00-15:00 SAST ( 8:00-13:00 GMT)

More information is available at http://olympiad.cs.uct.ac.za/#online
We have not yet set up the registration system. I will make another announcement when this is ready, but I wanted to provide advance notice.


In my words:

If you participate in the 2nd round of the SACO (past/present), this is a great opportunity to see how you would have fared in the 3rd round (assuming you haven't progressed of course). If you've done any other programming contest and enjoyed it, if you've even just considered taking part or wanted to, but couldn't for any reason, it's worth a shot.

The online contest is open to everyone, including college students, people already out working in the real world and professors. It's not limited to South Africans, but open to the world. Basically, the only people that cannot compete are those involved in the organisation and those participating in the real contest.

The problems will be identical to those in the real contest. So besides competing off-site and not being eligible for the prizes, it's identical. It would be great to get a good turnout for the first run!

Languages supported are Java, C/C++, Python and Pascal.

UPDATE: Registration is now open. More details here.

Training the Youth

When a paper-based round was added to the SACO in 2003, suddenly the participation nearly tripled. Students without access to a computer were finally able to participate. However, participation in the computer-based second round (or what was originally the first round) remained fairly constant. If someone did well in the first round, but never knew how to program, there wasn't much they could do.

Yesterday, however, the situation was improved slightly. The top students from schools unable to compete in the second round were invited to learn Python. I was one of the three students that went to teach them. There were 15 of them and only 4 of them had any programming experience (Java). The rest knew nothing about programming before we visited them.

I was expecting there to be maybe a couple interested with the rest wishing they weren't there. I couldn't have been more wrong. They were all very eager to learn and they caught on surprisingly quickly. There was one that wasn't too interested, but the rest found it so amazing that they were learning to control the computer. Withing less than three hours they understood up to if-else statements. To put it into perspective, it usually takes two weeks before loops are covered at UCT using Java.

The SACO started advertising Python since 2005 when The Shuttleworth Foundation sponsored prizes for the top Python 3rd round participants. Since then UCT has spawned a 1st year Python course for advanced programmers as a replacement to the usual Java course. Most students taking the course get hooked onto Python. While I do have other favourites for other tasks, I certainly like using Python for several tasks mainly due to its conciseness.

There have been discussions about Python replacing Java at schools. However, most teachers are against change and so it's a difficult battle. From the experience of training these kids with little to no programming experience I can confidently say that Python is a much better teaching language than Java. There's nothing that is required before it can be explained, such as the classic "public static void main(String args[]) {". Compare System.out.println() in Java to print in Python. It's self-evident which is easier to teach.

The training continued today, however I had other kiddies to train. This time it was ACM ICPC training. The regional contest is coming up in mid-October so now was time to get the training started. As I can no longer compete, having won two regionals, I am now doing the training. Some of this bunch are older than me even, which makes for could make for an interesting experience if one of them wins. We went over some old problems, which some of them tackled fairly well.

Next weekend the training continues, but once again with a different bunch. I be training the IOI team I'm going with to Zagreb, Croatia on the 14th. For that training we have to set new problems for them to solve under competition conditions, i.e. a mock IOI.

ICTS Can Fix Things

Yes, there are those rare few who know what they're doing at ICTS. And Adrian Frith is one of those people who knows those particular people and what they're good at.

With Adrian's help, last week the issues with the LCC were solved. The solution ended up being: "Oh, let's just disable all the smart stuff in the smart switch!" Problem I find in that is, what was the point of a new switch then? Apart from the nice upgrade to a Gbit network, which doesn't really improve the situation for ICTS and them wanting to remotely block ports. It's fixed though and nothing has gone backwards (thankfully) so I'm happy.

Then, another issue we had with them was with the Olympiad server. This is the server we use for the SACO. Now, the team are supposed to be training for the upcoming IOI and half of their training is done off this server. The 3rd round of the SACO is also approaching and again, they use this server to train on. The issue was that it could only be accessed on campus via the IP address. The DNS wouldn't resolve and the firewall was blocking access from off campus.

This problem started about 3-4 weeks ago. We've been in contact with ICTS for at least two weeks. They kept on closing the call, telling us the problem was resolved. Three of us (myself, Bruce and Carl) all tried desperately to get them to sort this out as it was really slowing other things down. On Friday I tell Adrian about the problem and this morning it is solved! Wow, how it helps knowing the right people at ICTS.

So that's two of three issues solved for now. The last one which is only getting worse is affecting everyone. Carl has blogged about this problem, so I won't say much more other than it appears to be related to the issues they're having with multi-casting. They've pulled down the network about five times now to get it working and they're doing it again this evening.

My word, how disruptive a small group of people can be!

Programming Contests

One of my biggest interests is programming contests. The number these days is ever increasing and more importantly, so is the diversity. In this post I aim to identify and discuss some of the major contests and pick out the parts I enjoy most.

The first international contest I competed in (in 2004) was the International Olympiad in Informatics (IOI). While it is only for high school students, it has a very different structure to any other contest. It is an individual contest consisting of two rounds of three problems with five hours per round. Part marks are assigned based on correctness and efficiency and marks are only returned at the end of each round. I like the split over two rounds, which allows for one to have a bad day and come back on the other day. I also like the way it squeezes you on efficiency, which often contests with a single yes/no response cannot afford. The South African team is picked from the medalists of the South African Computer Olympiad (SACO).

By far the most prestigious contest is the ACM International Collegiate Programming Contest (ICPC), for which I competed in the 2004 and 2005 regionals and the 2005 and 2006 world finals. As the name suggests it is only open to university students. Teams of three compete against one another by solving as many of the ten problems in five hours, with a single PC per team. I like the teamwork that is forced upon teams with only one PC, which also requires very good planning/management skills. The problems are usually of the best quality and the types of problems vary, which allows for teams with mixed skills such as including mathematicians in the team. In this and many other contests, you get the result of a submission back immediately. I must say I am a little against this as it makes teams submit without testing much at all. You also get no part marks which results in very close results, often split by time penalties.

The Internet Problem Solving Contest (IPSC) is similar in structure to the ACM ICPC. The crucial difference is that it is an online event without any specific locations. The contest is open to anyone and everyone and not restricted to students. It also allows for any programming languages and hardware/software resources. These differences all allow for a much larger number of contestants. There are generally about 12 problems to solve in the five hours, each with an easy (1 point) and difficult (2 points) level. Teams of three are competing against one another. The problems are typically far more mathematically inclined than the ICPC, although the problems vary rather drastically between years. This year they even included a simple image processing problem. I really enjoy the problems in this contest and that is the major factor towards this being my second favourite contest.

Another contest which many compete in is the TopCoder. They run contests about once a week - online, as with the IPSC. I must confess that I dislike the format so much that I have only ever competed twice. The short duration of three problems in about 75 minutes really kills it for me. I don't like solving problems so quickly. I like having to think about them. That's why you'll see as you read on that I have a preference for the marathon-style contests. All the top competitors define their own macros to squeeze out an extra few minutes. I'm sorry, but as much as it might prove fun to some people, I just cannot pull myself take part in it again. The Google Code Jam follows a very similar structure and runs on the TopCoder platform.

In South Africa we have a national contest which started in 2005 called the Standard Bank IT Challenge. This is another one I dislike, but for different reasons. However, it has some interesting new ideas. The first round (heats) are four hours with five problems. However, two of the problems are related and you only receive the second part after solving the first part. This adds an interesting dynamic in that you have to be cautious not to leave the problem with two parts too late, although it's typically one of the more difficult problems which makes things very interesting. You are also in teams of four for this one, which adds more to the team aspect. The finals consist of six problems with six hours to solve them in. This time there are two problems with two parts. One of those is very different to all the others as it's an interactive problem. In the three years the contest has run the interactive problem has been the most interesting: foxes and hounds, maze game and suicide chess. The other problems are all mostly simulating some process, with very picky and vague problem descriptions. It's the problems and the poor judging that kills the contest for me. The only reason I compete is that it's a national contest and the prizes are very nice.

My favourite contest to date is the ICFP Programming Contest. It's a 72 hour marathon contest with almost no limits whatsoever. Anyone can participate, teams can be of any size and can even be spread across the world (as will our team be this year). There are no restrictions on programming languages, software or hardware used. There are in fact no restrictions I can think of other than the 72 hours you are given and that they asked us nicely last year not to reverse engineer the platform provided. I competed for the first time last year with a team of seven students. The 72 hour time frame is just perfect I think as it's long enough that you can concentrate on the problem for the full time without getting the feeling you're giving your life up to the contest like with semester-long contests. I also really enjoy having no limit on team size as it allows you to get some people coming in to help on parts they're experts at and then go back to their normal lives while the contest continues. This makes it reasonable to get people not willing to give up much of their time. You can also very easily get advice from people, which takes up very little of their time. Even if the person is not in the country, you can still contact them.

Just last week while in Zurich I was told about the Extreme Challenge. This is another marathon contest, but 24 hours this time. The teams are restricted to three and you aren't allowed access to any external resources, including the Internet. The finals are held in Budapest, Hungary. You are given a single power cord and a desk and you bring all your own hardware - and you can bring as much of it and whatever you like! It sounds like a very interesting contest, although I still think I'd prefer the ICFP due to the lack of restrictions. The problems seem very interesting though and they are very polished, which is seldom the case. I will definitely aim to try it out next year as I like these marathon contests. Until then, I can only go on what others have told me and that is that is is an excellent contest.

For those of you who haven't heard, there are no Code Jams this year. After four of them last year, the organisers are a bit exhausted and needed a break. With this break, some of the coaches discussed the possibility at the Google ACM meeting last week of Google starting a new, very different contest. The idea spawned from the Extreme Challenge, while they though extending it to 72 hours would be more exciting. The idea behind it is that the Code Jam is so short that it doesn't necessarily identify good software engineers, but rather those who can very quickly solve small problems. With this longer contest, planning is required as well as team work, which should provide a better of software engineering skills. Details are still very rough, but the idea definitely caught their interest. I think it's a great idea! So who knows, we might just have started a new Google contest!! :)

Those are just a few contests I have competed in. If you have another favourite, I'd love to hear about it. As I said, I only recently found out about the Extreme Challenge and it sounds like one I should have heard of long ago. Also, if you have anything to add about my analysis of these contests I'd love to here them too. This is one thing I'd really like to get your feedback on.