South African ACM ICPC Regionals 2007

This past Saturday was an amazing day for more reasons than one. Not only did the Bokke claim their second set of hands on the William Webb Ellis trophy, but UCT simply extended their domination of the South African ACM ICPC regional contest.


For many of us coaches it was our last year running the contest and so we wanted to leave with a bang. So we went in search of some sponsors that would help us do something special, something we couldn't achieve on our own. That sponsor quickly turned out to be the one and only Google! Our intention was to use their involvement in the contest to make the single improvement that has the greatest impact - more contestants!

Last year we had ten teams participate from UCT. There was an obvious split between a few teams that were very successful and the rest that were in it just for the fun. This year we wanted to get more top teams, while filling in that middle gap. The gathering of contestants turned out to be very successful, with Google proving to be a crucial factor. We started reaching numbers such that we started becoming concerned that we would have insufficient space in the competition lab. After some discussion between us we settled on cutting the numbers at 22, with 5 teams from each of Stellenbosch and UWC.

For the past three years, we had been running training for the teams. For these three years we were fine tuning the training every year, making changes from the experiences from the previous year. However, there was a wide diversity of teams attending the training. The strongest teams would typically get together for their own training, while the teams that had lots of potential, but lack of enthusiasm, would just pitch up for the contest without practice.

This year we made some serious changes to the structure of our training. First of all, as silly as it may sound, providing free pizza during the training has a huge impact on turnout. Thanks to our success in swiping all the R325,000 prize money from the Standard Bank IT Challenge we were able to do this, although in future it would be interesting to see what can be done about obtaining sponsorship for this as well. We then ran full mock contests, using full problem sets from past contests and the Abacus contest system used in our regional contest.

Providing full rankings as in the actual contest seemed to attract the stronger teams along. They couldn't resist showing off and seeing who was better, although in the one session that Harry and I participated for fun we beat the lot. One thing that this contest requires to succeed is exceptional team work. This is one reason I find the teams that remain together for several contests are the ones that win. Without practicing together as a team, you cannot achieve the level of team work required to win this contest. This is where the new form of training adopted this year proved very successful, attracting many more people than ever before. The improved training also appeared to have some effect on the turnout for the contest itself.

With more than a week to go before the official registration closed, we hit our limit of 22 teams from UCT. We were forced to close down registration early, turning several teams away. It was unfortunate that we had to do this and next year we will try our best to accommodate the larger numbers. It was, however, already cramped with some rows of four PCs allocated two teams.

Yesterday, Saturday 20 October. This was the big day. The day we had been building up for for so long. The day before Bruce and Carl did the final preparations. They pre-allocated all the t-shirts, name badges and all sorts of other goodies into paper bags for each team. With a total of 30 teams (22 UCT, 3 Stellenbosch and 5 UWC) arriving in the morning we had to prepare ourselves for a speedy registration process. There were a host of other preparations they had to do, all to make the contest day run as smooth as we could possibly make it.

We told everyone to start arriving at 07:30, so we arrived at 07:00 to for final preparations. With the sponsorship from Google, we were able to use the budget from Pretoria to provide breakfast before and snacks during the contest. Unfortunately we underestimated the consumption rate, so we understocked. Before anyone got a chance to invade the breakfast supplies they had to register and pick up their team bags full of goodies. There was a steady flow of people, which is always better than a massive flood.

As people were still arriving at 08:15, we hung around the registration area a little longer until eventually moving down at 08:30. Everyone found their seats quickly as we had maps outside the lab. By the time everyone was seated and logged into the PCs, the practice contest had started. The practice contest was a poor start. There were several errors in the problem statements, some of which wasted several teams a lot of time which should have been used in testing the environment and not the problems. I hate laying the blame, but Pretoria ran the contest and they didn't get things off to a good start in this regard.

We were scheduled for a 09:00 start, however, I don't think we have ever started on time. There were four locations across South Africa where teams were participating from. Each site had to give the ready signal and any last minute technical difficulties needed to be sorted out. To make matters worse, they had a brief power failure in Pretoria! We finally got going at 09:45.

We were very anxious to see the problems. Since we don't run the contest, the first time we get to see the selected problems is when the contest starts. We submitted five problems to Pretoria, which was much larger than our typical number of one or two problems. This was in part due to part due to the increased preparation we were doing for the contest this year on our end and that there were four of us interested in submitting problems. With our experience in running the SACO we were used to working together on checking each others problems thoroughly.

This is where we got a little disappointed. After having submitted five problems, only one of them was accepted. Happily for me, it was one of mine, but it was still a disappointment. Especially when we consider the reduced difficulty level in this years problem set compared to previous years. While this might have been done purposefully, I tend to disagree for reasons that should become apparent later in this post. I'd be interested to discover where the selected problems usually come from.

I will probably provide solutions to the problems in a later post. However, a quick analysis for now. The problems should be made available here shortly. Problems A (blue) and F (yellow) were both trivial - there was nothing algorithmically difficult about them. Problem E (red) was also algorithmically trivial, although the coding was slightly more complicated. Problem C (pink) wasn't very tricky either, but the Maths could prove problematic for some. Problem B (green) was tough on constraints, requiring a linear solution. Lots of teams timed out by using a quadratic solution, or even if they had the correct algorithm got an "abnormal termination" due to too much memory usage. Problem D (purple) was the evil one, and to make you all hate me let me be the one to inform you that I set it. :-P

The gang got off to a quick start with UCT team ʇ|nɐɟƃ3s claiming the first problem in 16 minutes, followed closely by UCT teams teh_solverers and The G-dS-B Conjecture, Wits team Blackhole Constants and then UCT team Custard Frog in that order. All of them solved problem B first. This resulted in a quick spurt of blue balloons that we had to dish out, such that we quickly changed strategy to preparing balloons before a team solved a problem.


As more and more teams came in with the blue balloon, so teh_solvers claimed top spot by solving problem F and claiming the first yellow balloon. They never lost the top spot! Once the scoreboard settled down a bit we had the top three teams all from UCT - teh_solverers, The G-dS-B Conjecture and ʇ|nɐɟƃ3s. That was the way I was expecting the scoreboard to look like at the end, but that wasn't to be.

teh_solverers pulled ahead, claiming the red problem after about 90 minutes. Shortly after this something disastrous unfolded. Several people were attempting the green problem, but getting timeouts. Since the time limit was two minutes, we thought that the slight backlog of pending submissions was due to this. However, the backlog grew larger and larger to the point where it just came to a grinding halt! Once we realised what was unfolding we quickly contacted Pretoria to find out more about the situation. It turned out that the main Abacus server was churning away so hard that it was out of memory, so they were building Abacus on a new server with more memory.

They told us it would be back up in about 15 minutes, so we made an announcement to the teams, however, even then they were disgruntled by the scenario. And this was before things started getting a lot worse! The problem seemed to be caused by the 30MB test data some of some of the problems, which was being polled by the marker servers every time they started evaluating a new submission. Add this to the numerous last minute commits to the Abacus software just before the contest and I still wonder why we use it over PC².

After an hour the backlog of submissions grew ridiculously long and still things weren't getting any better. Pretoria were rebuilding Abacus on a new server with more memory, however, this was taking some time. When they eventually got it linked up they only had two markers attached in order to prevent the server from crashing again. This wasn't working though as submissions were coming it at a faster rate than they were being processed.

About 90 minutes into the saga, they finally attached 10 markers to the server and it started processing the submissions much quicker. Only problem though, for some reason the system was developed in a way such that a new server would start evaluating the submissions right from when the contest started. So it sat there churning away through all the old submissions that had already been evaluated! I still don't understand this design decision, but at least things were moving. We had to wait another 15 minutes or so before the server got to the new submissions.


The next 10 minutes was balloon chaos!! Think of all the problems solved during that span of nearly two hours. Picture us having to blow up and dish out all these balloons as fast as we could. That's what it was like for these next 10 minutes - FUN! This was also the period during which any doubts about the problem set not being easier than previous years faded away. There were so many teams that hit three balloons! I'd guess it was about 40-50 balloons that we distributed in this short period of time. Determine colour of next balloon, blow up, tie, attach piece of string, run!

While the markers were borked, the standings were obviously idle. The spurt of balloons after they came back online shuffled things up a bit. teh_solverers further secured their lead with the pink balloon and the green balloon soon after the spurt. They therefore had two hours to work on the final, purple, balloon and were well on their way to defending their title. My recollection of the order further down is a bit fuzzy due to the chaotic balloon rush, but Bacon & Eggs climbed up into second place with the pink balloon, just ahead of ʇ|nɐɟƃ3s who also got pink. The G-dS-B Conjecture were slipping down a bit, while Team LOL was climbing.

At the start of the last hour, when the scoreboard was frozen to keep some suspense, there were three teams that had solved all but the purple balloon: teh_solverers, Bacon & Eggs and ʇ|nɐɟƃ3s (all UCT teams!). The time gap between second and third was a paltry 7 minutes! Blackhole Constants (Richard Starfield and co.) from Wits was the top-ranked non-UCT team on four problems. They needed both the remaining problems to clinch it as they were far behind on time. With 40 minutes remaining, Bit Chow Down grabbed fourth place to make it UCT with the only four on five problems! And any of those four could clinch in the remaining 40 minutes by solving my purple problem.

The balloons trickled real slow in the last push. The De Bruyn Altimeter (Nicholas Pilkington and co.) from Rhodes joined the other UCT teams on five problems right near the end, but other than that the results were pretty much unchanged.

The top four teams remained UCT teams, in the following order:

1. teh_solverers
• Timothy Stranex
• Migael Strydom
  
• Tamara von Glehn

2. Bacon & Eggs
• Bertus Labuschagne
• Ian Tunbridge
• Ingrid von Glehn

3. ʇ|nɐɟƃ3s
• Charles Bradshaw
  
• Max Rabkin
• Keegan Carruthers-Smith

4. Bit Chow Down
• Christian Geist
  
• Dave Jacka
  
• Ashley Reid

The full standings are available at:

http://acm.cs.up.ac.za/cgi-bin/standings.pl

It was all over. All that hard work paid off. This was an awesome result for us. It shows that our new training methods are working effectively. It's often said that having many teams highly ranked shows the coaching abilities more than having one do exceptionally well. We've definitely succeeded in getting on the many highly ranked teams side. A lot of this is due to this community that has been evolving at UCT, a community of people interested in competitive programming. We've grown to a point where we now work together and learn from one another.

After the contest we went to Da Vinci's in Kloof Street for lunch. We took up most of the restaurant we there were so many of us. They served some excellent pizza, only a tad slow on the delivery of the food. After the food, we had a little prize giving. The top three teams each got Google goodies that Google supplied us with as well as something small from Pretoria.

1st place: teh_solverers (left to right: Migael, Tamara, Timothy)


2nd place: Bacon & Eggs (left to right: Ian, Ingrid, Bertus)


There has always been a shortage of females in Computer Science. This is always evident in the numbers in these contests. This year we had three females out of 66 contestants at UCT, which is less than 5%! Therefore we were glad to see two of them fighting it out at the top, eventually taking the top two spots. On top of it, they are twins.

Left to right: Ingrid, Tamara


What would the contest be without us wonderful coaches? No training, no motivation to participate and worst of all no contest at all! For three of the coaches, this was likely the last ever contest they will be running. For me, this was likely my last ICPC regional at UCT (hopefully I can find some new minions to train when I move on).

Left to right: Carl, Donald, Bruce, me, Shen
Bottom: Harry


So now I will be taking teh_solverers back to the World Finals next year, this time in lonely Alberta, Canada. This year they came 26th, can they make the medals next year?