Thursday, December 11, 2008

Planning for PhD

After the painful experience of seeing my masters supervisor resign a few months ago, things have been turning out rather nicely. A huge advantage of working with my new supervisor is that she has good international collaboration. Last month I met the lead developer (from Illinois) of VMD, one of the visualisation programs I'll be writing my masters project for. This week it got even better!

This week, Dr Robert Best is visiting from Cambridge. It is looking increasingly more likely as time passes that he will be my PhD supervisor. Yes, that is correct...I am this close to getting the amazing opportunity of studying my PhD at Cambridge! The only hurdle at the moment is funding. I've been very slowly releasing news of this, as I first got word of the possibility around the time I started my new masters project a couple months ago. This is entirely thanks to my masters supervisor, Michelle Kuttel, who put me in contact with Dr Best.

Yesterday I met him for the first time, and we discussed potential research topics. The deadline for applications is due very soon, so for the moment we're focussing on a particular topic that looks very promising. Summarising very crudely, it's about taking advantage of both the speed of coarse-grained simulations and the accuracy of fine-grained simulations to produce fast, but accurate simulations of biomolecules. The main question here is how to swap between different representations of the system. Another possibility we have been looking into is furthering his research in reaction coordinates, which he summarises on his website.

By the way, this is the reason I am trying to finish my masters in a year. The year starts in October at Cambridge, and starting when their year begins makes things much simpler.

Thursday, November 13, 2008

Proposal Presentation

My proposal presentation went really well today. I was concerned that the biology jargon would get in the way of the meat of the project, but we got past that. Edwin is my second reader and he provided some very useful criticism. Main thing I'm glad about is he suggested we remove the user testing aspect, which was always my least favourite. He also picked up a few bits of jargon we need to describe better come the thesis, but nothing major. The last thing he picked on was a concern I raised with Alex (my co-supervisor) previously anyway, which means I'll be paying more attention to it.

So on from here we go. Next step is to continue with the background reading and starting of the background chapter. The plan is to wrap up with the bulk of the background reading by the end of this year and then dig deep into the project. I have a tight schedule as I plan to finish up by October next year. I've had very contradictory reactions to this, some saying it's quite doable, others laughing it off. We'll see.

Tuesday, November 11, 2008

Masters Milestone #1: Proposal

If official milestones were all that counted, I'd be about to exceed progress of the project I previously spent six months on within the first six weeks of my new project. My proposal is all written up, gone through the shredding of two wild supervisors and I'm ready to present it to the department this Wednesday. Woohoo!!

It's insane thinking how fast things can move when everything just works. From the way things ran in my last project to this now, wow how things can change over such a short period of time. I have to thank my supervisors Michelle and Alex, they've really provided great support.

So anyway, Wednesday 13:00 in CS303. My title is "Development and Validation of a Visualization Tool for Predicting Protein-Protein Interfaces". If you're interested in scientific applications of Computer Science, this is a good example. It also involves quite a bit of computer graphics.

Friday, October 31, 2008

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!

Sunday, October 12, 2008

ACM ICPC South African 2008

Yesterday UCT hosted 22 teams from UCT, Stellenbosch and UWC for the ACM International Collegiate Programming Contest. This year we had three new helpers from this years World Finals team that can no longer compete. We did a lot of preparation on our side for the event, but as we had the SACO just two weeks ago we didn't contribute any problems.

The contestants started arriving from 07:30 for a large breakfast we prepared for them. They thoroughly enjoyed all the food and chowed it far quicker than we could've imagined! Thanks to Chris Parker and Bertus Labuschagne for preparing the breakfast and snacks during the contest.



While the contestants ate and I handled registrations, Ian Tunbridge was in charge of preparing the lab with the team flags and balloons. For the first time we decided to blow up all the balloons in advance. Given the number of problems solved last year this seemed like a good idea, but alas as you'll find out soon enough it was not.


At 08:30 we started moving the contestants down to the lab, let them login and waited for the practice contest to start. After the practice contest the Nigerian server went offline due to power cuts, which pushed the start 45 minutes late. The start wasn't as pretty as we had hoped for, but things finally got underway at around 09:45. It took some time for the first problem to be solved, so I had plenty time to catch a before shot:


We put together a large team of UCT students no longer eligible to compete. We had Timothy, Migael, Tamara, Harry, James, Robert, myself and for a brief period Ian. Our first goal was to check the problems and send in any clarification requests early, our second goal was to beat Bruce who was doing them solo. Unfortunately we failed at our second goal, but then again Bruce cheated. :P We got A, B and D within little over an hour. We then got stuck for quite some time trying to match what was actually expected in F but got it eventually. Harry was working on C, but very quickly hit a dead-end as he was getting wrong answer. We asked numerous clarification requests and submitted countless times before finally getting it correct. We tried too hard on E, realising too late that a brute force solution would work in time (Bruce beat us to it and solved all six!).

This was our team near the beginning, minus me who took the photo:


More than an hour into the competition, ʇlnɐɟƃ3s got the first problem at the UCT site:


Things never really took off for the full five hours. The number of problems solved was very low with only 14 of about 70 teams solving anything at all, only two of them solving more than two problems. Going into the last hour Tuks3 were leading on time and the scoreboard stopped updating. This is when the local teams started pulling away, with team ʇlnɐɟƃ3s solving a third, followed shortly by Code Red from Stellenbosch also solving a third. At this point both teams were extremely close on time, but UCT's ʇlnɐɟƃ3s was just ahead.

It was in the last 15 minutes that ʇlnɐɟƃ3s closed the door on everyone else by solving their fourth and final problem. No-one was able to pass them in the final minutes. The end results were:

  1. ʇlnɐɟƃ3s of UCT (Keegan Carruthers-Smith, Max Rabkin, Saadiq Moolla)
  2. Code Red of Stellenbosch (Ralf Kistner, Dirk-B Coetzee, Petrus Theron)
  3. Tuks3 of Pretoria
  4. Team LOL of UCT (Julian Kenwood, Richard Baxter, Mike Talbot)
  5. OMG Raptors of UKZN
With only 15 problems solved at the UCT site (23 overall) we had 117 inflated balloons left over. What to do with 117 balloons? Well we let the contestants take them home, and this was the result :)


After the contest we went to Primi Piatti in Cavendish for lunch. Unfortunately before we could go we needed to clean up the mess the contestants left behind. Yes messy bunch...Once the lab was all cleared up we headed off and were just about the last to arrive.


After lunch, which was staggered by table for some reason (the kitchen couldn't handle the numbers or something) we had a little awards ceremony.

3rd at UCT site and 4th overall: Team LOL (Richard, Mike, Julian)


2nd overall: Code Red (Dirk-B, Petrus, Ralf)


1st overall: ʇlnɐɟƃ3s (Saadiq, Keegan, Max)


Contest helpers: Marco, Harry, Timothy, Tamara, Migael
Missing: Chris, Bertus, Ian

Problems, detailed standings, statistics and more are available here.

Thursday, October 9, 2008

Renewed Masters

It's been two months now since I heard the news that would result in drastic changes in my life. I never realised just how bad the news was that day. It took some time to sink in. When it did, however, that was the start of a very stressful period for me. I'm talking about the day my supervisor resigned.

There's a lot of details behind what happened, but for personal and ethical reasons I have chosen not to comment about it much online. It is for the same reason I have held off posting about what has been happening until now. Now that things are settling down it's time to start coming out with the news though. Many of my friends have known about this for a while now, it's just time I announce it publically.

So my supervisor resigned. Within a couple days I started talking around and within a week I was discussing the possibility of a new project. Ironically the first person I spoke to, Michelle Kuttel, is now my new supervisor. The main reason for the change of topic is that no-one else at UCT was strongly grounded in the field of my existing project. While it meant essentially writing off six months of hard work, I had to consider my long-term goals. It sucks, it really really sucks...but I don't regret making the decision, not yet. It's been a long, stressful ordeal, but I feel I've made a good decision.

My new project is in bioinformatics and is on protein-protein interface prediction. It's a graphics-heavy project with the new field of computational biology to learn. It's a drastic change from my previous project, but I have reasons for doing so. The plan is to get down to serious work quickly and get wrap up end of September 2009. It's a very quick masters, but after the huge setback I'm seriously determined to get this done and with my supervisor believing it's possible I will get it done.

Apologies for keeping this so brief, but I don't want to say too much publically about this. You'll be hearing more about my new topic though, no reason to keep that quiet! I plan on putting together my proposal by the beginning on next month and giving my proposal presentation a week or so after.

Thursday, October 2, 2008

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. :)

Wednesday, September 10, 2008

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! ;-)

Thursday, August 28, 2008

IOI Day 5: Contest, Conference and VIP Dinner

As you will have seen from my previous posts the second round of competition took place on Wednesday. Well, actually it is all over now and I am back home in South Africa. Things just got too hectic and sleep became a higher priority than blogging. I'll be going back and blogging about what happened for the last few days.

Day 5 started with the second and final round of competition, which from seeing the problems the night before I considered easier than those from the first round. Our guys went into this round still standing a fair chance given the low scores from round one. I was not to see them until it was all over though as us team leaders were in quarantine.

The day started with an early breakfast. I had my presentation to give at the IOI Conference and I wasn't going to be late. I was scheduled for 10:30, the second slot. I arrived early to get my presentation onto the laptop they were using, however, after much waiting no laptop arrived. They wouldn't let us use the main PC that was there as it was connected to the network so we had to wait for a laptop to come, which took a while. During this time I was told that the first speaker was busy in a meeting and so I was to go first. As if the nerves couldn't get any worse they finally brought the laptop and the first person to copy his slides was having difficulties, but luckily I was able to step in and resolve them.

Finally my presentation was underway. The paper I presented, titled "Challenges Running a Computer Olympiad in South Africa" is available here and my slides here. It went well and timing was spot-on 20 minutes. The questions that followed were most interesting, although I must admit I have forgotten most of them. Wolfgang was interested in the decline in numbers for the second round upon introducing the new first round format. A couple people were interested in what we did with promising results from the first round if the student had no access to a computer.

After the presentation, however, is when the real fun started. Several people approached me to discuss some of the points I had made. There were those just stunned at the difficulties we face back home and our novel approaches at tackling them. The Dutch who know us so well were even themselves surprised at how difficult our task was! One of the unsurprising interests was our experience with Python which a few others were testing out. There was even some interest in our efforts to get juniors involved.

Once the presentation was done I was far more relaxed, although we still had the contestants hacking away at the problems. I enjoyed the rest of the presentations and there were some great ones given, although there were also those that went bad, mainly by non-native English speakers -- got to give them a hand for trying though. One that especially caught my interest was Ben's paper on alternative training methods. After all the presentations it was announced that the 3rd IOI Conference will be held during the next IOI in Bulgaria. I later caught up with Valentina who runs the conference and she told me they're planning on setting the topic on how countries have progressed over the years.

When we got back to the rooms lunch was not yet ready for us, but I had a couple more discussions about my paper leading me to almost forget entirely about lunch! The contestants seemed to be taking longer to come back this time, but I eventually found our guys just after lunch. The general atmosphere wasn't that great and everyone was keeping to themselves which meant we had to wait for the results to come out. Before they could be released they had already found the computers and started Counter Strike, which proved contagious as several others joined.


When the results finally arrived (they were slow to place them in the pigeon holes again!) I rushed to collect them. Unfortunately the team weren't as anxious to see them as I was, understandable after seeing them. Mark, who had done well on day one did poorly this round while Saadiq was the one to clinch our one hope of success with a full score on linear gardens. All-in-all the problems proved a serious challenge to our team and they weren't expecting such a toughie. Hopefully the two that can return will learn from this experience.

Saadiq ended up with an ear infection and our team leader took him to get medical treatment. Apparently they brought an ambulance sirens blurting yet never even checked his ears! Fortunately his father is a doctor so since returning he's gone for a proper check-up. The Counter Strike returned and continued for many hours. At its peak I counted 12 on the provided computers and many more on laptops. This made getting a computer for Internet usage very difficult.


After a long discussion with some of the guys I'd met earlier in the week, we had our VIP Dinner to go to. It's not often people like us get to go to such an event. The team leaders and deputy leaders were given special invitations the night before and most people dressed in suits, however, with the weather we didn't come prepared for this so I went in the smartest I had, a shirt. I tried dragging Mohamed Taha of the HSC along. He was resistant as he was extremely tired, but I managed to convince him. Unfortunately the buses were packed, but he found a ride with Osama of the ISC. On the road to the dinner I had a discussion with the Macedonian leader who was inspired by my presentation and we exchanged experiences and both gained new ideas from one another.

When we arrived we were greeted by a most wonderful venue full of people dressed in suits, as you can see below. They even laid out the "red" carpet for us. The drinks they served were absolutely stunning, I loved the strawberry and guava! Soon after arriving the main guests arrived. There was the Minister of IT and Communications and the Minister of Education. For the locals it was a great honour to be able to host people of such stature. Just before leaving for the dinner I also heard that many ambassadors were attending the dinner. It turns out all the country's ambassadors had been invited, but unfortunately our's did not show up (it seems roughly half did!).


I wandered around outside a bit with the Macedonian leader before finding Taha and chatting more with him.


Finally when they were ready for us to take our seats we discovered we had been preassigned seats by country. Unfortunately that meant we had to split up and I ended up at a table with Singapore and Serbia. The Serbian ambassador and his wife were also at our table and somehow the two of them ended up sitting between Peter and I, so the Serbian team never really spoke with their ambassador. I had a great time talking with him about his experiences in Cairo, especially as a foreigner who'd lived there for 2.5 years. Strangely he prefers living in Egypt to Serbia, something I wasn't expecting.

The dinner started with several speeches, quite possibly more than any other event. Frankly I've heard enough propaganda from such speeches that I mostly ignored what was being said. The meal that followed was easily the best we had had that week. One good thing about having the ambassador next to me is that he warned me what not to eat, especially the lettuce. During the dinner we had what could end up being quite an historic moment for us in that Nigeria confirmed that they would be hosting the first African Olympiad in Informatics in Max/June 2009. They were that quick in contacting their government and organising the funds!


Once the desert was over we were, as usual, quickly scurried out of the venue. I found it very annoying when they did this, but I suppose it's their culture so it's normal to them. When we got back the guys were still at CS. In fact they ended up pulling right through till breakfast and then skipped the tour the next day in favour of sleep! I had some fun with Ricardo from Spain, Mile from Macedonia and for some time one of the contestants from Azerbaijan (apparently they do absolutely no training for the IOI!). Mile was trying to get us to enter the BOI which they're hosting in October, but it's too far for us and costs too high.

After having enough with the indoors we took a walk outside, something I hadn't done all week so I saw a couple new places. Just before our walk we were asked by one of the guides if we wanted McDonald's. Given that we were in Egypt and that it was one in the morning, we kindly rejected the offer. When we returned from our walk we noticed he had started getting quite the list of orders together. I will never forget him on the phone in the cheesy accent ordering a "Chicken Friday hello hello". Apparently Chicken Friday really is the name of a burger, while "hello" or however you spell it is "nice" in Arabic. Well he ended up taking a lot longer than any of us could have expected. He finally put the order through at three in the morning, which by that time he had convinced us to order a Mc Arabic. Just look at the order he has on his lap:


When he told me the order was going to take two hours to deliver I took it as a cue to go sleep. With such a large order there was bound to be someone who would take my burger, which I had actually planned on sharing with Ricardo anyway. The next morning I found out the order arrived at 04:30 and came to 1,500 Egyptian Pounds ($300)!

The next day was the final GA meeting followed by Dream Park World for the contestants and the Egyptian Museum for the team leaders, ending off with the awards ceremony.

Wednesday, August 20, 2008

IOI 2008 Solutions

UPDATE: PDF's of the solutions available here: http://people.ksp.sk/~misof/ioi08/

Here are photos of the official solutions for the IOI tasks of 2008. Anyone care to OCR them? :-P

Printing


Islands



Fish



Linear Garden



Teleporters


Pyramid Base



Results Out

The second round of competition is over and the results are slowly being revealed. Our results are 156, 111 and two <= 100. SnarkNews is slowly putting together a list of results from those willing to give them their results:

http://snarknews.info/index.cgi?data=newstape&menu=ioi08&head=index&class=ioi08

Another more complete list of results:

http://forums.topcoder.com/?module=Thread&threadID=613160&start=210&mc=220#1015095

IOI Day 4: Pyramids and Task Selection

This morning there was another GA meeting to discuss any problems with the first day of competition. I asked Taha, one of the leading members of the HSC, and he told me there were no appeals so not much would happen at the meeting. Given this and me being really exhausted I chose an extra hour of sleep in favour of attending the meeting, while our team leader attended just in case anything important arose.

I had some interesting words with Taha last night. He said that there was only a single 100% submission for fish, the hardest task, and that the marks were very low in general. He proposed and set islands, the medium problem, and it was very interesting hearing the procedures he had to go through to get the task and most importantly the test data really polished. It's disappointing that all the organisation around him and the contest itself, i.e. the outings and such, have been plagued by so many problems.

After breakfast this morning (the same...again!) we went to the pyramids of Giza. You hear so much about the history behind the pyramids, possibly more than any other man-made structure that it's amazing to simply think that we were actually going to see them. Last night, as mentioned in my previous post, we saw a glimpse of some pyramids. I had no idea at the time, but these happened to be the ones we were to go up close to today.

When the bus drove past the pyramids we were able for the first time to put into perspective just how amazing a feat it was for man to have built such structures so many years ago. Each block was nearly the height of an average person. It's just amazing getting the opportunity to see them so close I don't think I'll ever get over it.

When we got out the bus for the first time to get an overall view of the three pyramids we were immediately scavenged by locals trying to make a quick buck out of people. They would put one of those material things on your head and get a picture taken of you with them after which they'd ask for money. This happened to me once (pic below), but I never had any money on me so I couldn't pay and he didn't seem to frustrated. After this, however, Robert and Mark got caught out with the local taking the picture with Rob's camera. It looked for a moment that he wasn't going to return the camera until he received money, but then one of our guides came to the rescue!





After taking enough pictures we were called back to the bus which took us right down to the pyramids. Here we had a rather interesting encounter with a local and his camel. This guy approached him with his camel and almost forced him to hop on, while Schalk-Willem continuously said "No money, no money!" and he replied "You student, free for you." After a few words flew back and forth he hopped on the camel. I rushed in front of the camel to get the following picture:


He then insisted that I got on the camel together with Schalk-Willem, which after a bit of hesitation I did. He gave us a nice camel ride and even gave me the whip to speed him up. Then he took our cameras and took what turned out to be very nice photos:



During the ride he asked us if we had US dollars or Euros. I said South African money only, believing I had brought my wallet with me. He got a bit confused and upset, but sounded eventually like he would accept it. Shortly after he let me get off so that Schalk-Willem could ride the camel alone without him holding the lead. When he asked for money I quickly felt in my pocket and realised I had left my wallet in our room (since I had no local money anyway) and he wasn't happy to hear this. During the ride our team leader, Peter, took a couple pictures of us and so he knew we weren't alone. So I went to go ask Peter, but saw our guide and decided to ask him instead.

Our guide had local money and we agreed that 10 Egyptian Pounds ($2) was a fair price. Unfortunately the camel man didn't agree with our definition of fair. He had a lengthy, heated argument with our guide in Arabic which drew quite a crowd. I later found out he wanted 40 pounds for each of us, i.e. 80 pounds ($16) and that our guide said he could do nothing to us and was threatening not to pay a thing. He eventually handed over the money (10 pounds) and we walked away in hysterical laughter anxiously trying to find out what he had said.


After that was all over we went to stand on the edge of one of the pyramids. The blocks were so large that we could only climb up one level. It was an awesome feeling to be able to stand on the pyramids and touch them. Unfortunately we were told not to go inside the pyramids, which we later found out some of the teams had done. I had heard the day before that they only allow a limited number of people in a day, but this was obviously not very accurate.




After nearly reaching the Great Pyramid of Giza (the only standing of the Seven Wonders of the Ancient World) we were called back to the bus. The last stopover was the Sphinx. I just couldn't believe that we were actually seeing all this for real, it was that amazing. It was right there in front of us. There was a bit of a crowd to get above the Sphinx to get a good view. In this area we were constantly bumping into locals trying to sell things, but we never bought anything.



Once that was all over we headed back to Mubarak City. I was zonked out the whole way back. When we arrived we quickly had lunch which ended with some of the contestants constructing a pyramid of cans. After lunch we had a few hours for activities, but I had my presentation to finish off so I only booked for the paintball at 17:00.

Just before the paintball our team had got hooked onto Counter Strike which also attracted some other contestants. Lets see if this starts a new trend in IOI like we've had in our SACO for a few years now. We were told earlier that the paintball would be 40 on 40, but this was definitely not happening once we saw the field. It ended up being 5 on 5 matches, but they took forever to split us into teams and get things going that by 18:00 they were still busy with the second game. While it looked exciting, us leaders had an important GA meeting to attend to scrutinise the second set of tasks for tomorrow.



The meeting began with some other matters such as the IOI Workshop that took place in May this year and the possibility of a new IOI logo for the return to Bulgaria (hosts of the first IOI) next year. The tasks were then distributed for us to check. The problem set for tomorrow is a really great set, even better than yesterday's. Unfortunately they were once again all batch tasks with no data or interactive problems. This was one of three major objections, the others were that the last problem was similar to a previous task and that the story behind the first one was similar to a previous task. All major objections were rejected while all sixteen minor objections were accepted.

Thankfully food had arrived before we were done with the meeting and so dinner went quickly. We then had a meeting with the leaders from Nigeria and Ghana to discuss introducing an IOI-like competition for the African continent. For now it looks like it will be hosted in Nigeria and about eight countries will be invited. It's nice to see other African countries taking such initiative and we're gladly supporting them. I also discussed the ACM ICPC-like competition I've been planning with them and they're really eager to get more West African universities to enter.

Last night I mentioned to Taha that I would probably be going to the Egyptian museum instead of Dream Park World on Thursday. He put forward the suggestion that we have the option of going to the museum all paid for and such instead of the park and they announced they were doing this at the GA meeting. I was very impressed that he managed to get this changed! Later on though they told us the contestants had to go to the park and only us leaders had the choice, but we're going anyway.

At about 22:00 we were given permission to leave. There was a little mis-communication with those guarding the exit, but we eventually got out. The security was also much tighter as we were walked to our rooms and not allowed to wander inside the building.

So tomorrow is the second and final day of competition. I'm very eager and stressed right now to find out how the guys are going to manage with the problems. The first one is easy, the second needs some thought and the last one is easy to get some marks but I'm still not sure yet how to score full marks, although I have ideas. I am also presenting our paper on "Challenges Running a Computer Olympiad in South Africa" tomorrow morning at 10:30. In the evening us team leaders have a VIP dinner with the H.E. Minister of Communications and IT after some well-earned free time.