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.

Tuesday, August 19, 2008

IOI Contest Day 1

Today was the start of the real competition at the IOI with the first of two five hour rounds with three problems each. From the GA meeting last night us team leaders saw the problems and recognised the last two as challenging, however, we still underestimated them as the scores have turned out lower than usual.

While the contestants wrote the competition the team leaders attended the 2nd IOI Conference, where some interesting papers were presented. Unfortunately I've been so zonked out that I had to skip the second half in favour of sleep.

As usual it was very stressful waiting for the contestants not knowing how they were coping. At least with the ACM ICPC we get to view the scores during the contest, whereas here we get absolutely no feedback. This was made worse when the spew of contestants came back from the contest arena into lunch and they kept on coming, and coming and we never saw our team...Peter eventually decided to look around for them and found them. The first signs weren't very good, but after hearing what the other teams had to say we felt a bit better.

One thing in past IOI's that has varied drastically is the time for results to be released. This year it was looking reasonable as they quickly got the results printed, but then they took their sweet time to release them and put them in the pigeon holes. They insisted that we could not collect them until they had placed everyone's results in the pigeon holes, which was a painful process to watch. Just before they eventually finished I was told they had enabled analysis mode so many teams saw their results on the contest computers. We stuck it out a couple more minutes and I was one of the first to collect the paper results.


The results were almost as expected from what the guys had thought of their submissions, minus a couple silly bugs. Our top score was 100, which given the partial unofficial results doesn't look so bad compared to what it might have in a previous IOI. A good score seems to be 140 -- 100 for printing and 40 for islands, although 100 is good enough to make a return in the next round of competition.

After the results were released we went back to the contest arena for analysis mode. We tried saving our solutions and the official test data to flash disk, but the judges for some reason didn't like that idea and were insistant that we stop immediately. I hope we weren't the only ones stopped as we weren't even allowed to print solutions. Anyway, we looked through the results and discovered a couple silly bugs such as the use of ints instead of long long in a single place for islands.


Once we were satisfied with things we went to catch the bus for the Nile cruise, which was supposed to leave it 17:00. Want to guess what happened? Why yes of course, we sat in the bus for about 2 hours before leaving with absolutely no reason given at all! When we finally did get going we were stuck in pretty heavy traffic, which is unusual for us at this time of day. It was about a 90 minute bus ride to the ship and we caught our first glimpse of pyramids along the way. I was so surprised to see them as I wasn't expecting them that when I did see them I shouted "Woah, pyramids!!" and my entire team abrubtly woke up!


And I just have to include this wonderful photo:


After waiting so patiently in the bus and taking the long bus ride, our patience was to be tested even further as we waited about another 45 minutes for the ship to arrive and be prepared for us. When we eventually got on we were offered a buffet dinner and we ran to be one of the first in the queue. It was pretty good food and a nice filler given the previously smallish meals we've been served. The dessert was especially delicious!


The dinner was accompanied by some humorous dancing:





The bus trip back included lots of sleeping:


Tomorrow we have a trip to the pyramids of Giza in the morning followed by activities and the GA meeting for the second day of tasks.

Sunday, August 17, 2008

IOI Day 2: Opening Ceremony, Practice Session and Task Selection

Dear oh dear, the Egyptians really take African time way too seriously. The organisation to get into the venue for the opening ceremony this morning wasn't the greatest, but they definitely made up for it with the performances. The speeches were cut to a minimum, although we've been told they're holding them back for the closing ceremony where we'll have the president's son and expected future president give a speech amongst other top people in Egypt.




The speeches were followed by some Egyptian dancing, which was quite fascinating to watch especially with the dresses. We then had the world's most famous marimba player give a solo, which was pretty damn awesome! The crowd really cheered her on very nicely and it made the opening ceremony a memorable one.




Due to the delays they had to shift the practice session after lunch, which was made an hour early. Lunch was once again the big meal of the day (something I have yet to get used to). After lunch we hung around a bit more waiting to head over to the contest room for the practice contest.

The practice contest is always an interesting time as its the first time we get to see the contest environment. The handin and evaluation system has gone back to being a new system specifically developed for this event, something which I had hoped had died given the recent years. As expected with any new system there were problems and one major one was the networking issues they had. I'm not sure if related to the networking problems, but our team would get different feedback for different submissions of the same code! This was highly frustrating given that you couldn't trust the errors it spewed at you. There were a few other problems which I hope they'll sort out before the competition tomorrow.


I'm not sure where they bought them from, but look at what they're still using these:


The contest arena was separated into 13 rooms with about 8 teams per room, which is different to what I'm used to seeing in the past. We had the Spanish and Swedish team next to us and I had some interesting discussions with their leaders (two of whom I had previously met). The Swedish guys are hosting the ACM ICPC World Finals next year and I've been talking to them a bit about that. They claim that they're going to be putting on a real whopper of a World Finals, already have booked out three of their grande hotels! They're preparing to host the first World Finals with live commentary for spectators, streaming it over the Internet. Because of this they are also pushing to get automated judging, something which the judges are constantly resisting. Lets hope they can successfully outdo Shanghai, which would be really impressive.

After the practice session we had to rush over to our first GA meeting, leaving the contestants behind. The GA meetings can be rather amusing as they're highly democratic with voting on every minor point. They go as far as voting on the agenda of the meetings. This year started off no different to last year, with a couple issues raised. One was that the version of FPC used was unstable and the request was that they change the compiler flags from -O2 to -O1. However, as you can imagine this would cause countless problems in the uncertainty as they had tested the solutions using the exisitng -O2 flag.


After seeing the contestants for one last time we went to the second GA meeting where we were given the tasks for the first day of competition. Our job was to scrutinise the tasks and then translate them into our national languages. This is always a fun time as we get to discuss in detail with other team leaders the solutions to the tasks.



[This post was only published well into the start of the competition. The timestamp is the time of writing, not publishing.]

The first problem is really easy with only a small trick you have to notice, so I hope most of our team doesn't overlook this small trick and solves it successfully. The second problem is a tricky graph problem with lots of smaller parts that need to all work in linear time, which I haven't quite worked at a full solution to as I'm way too sleepy right now. The third problem is a really interesting task that stumped even the original author who submitted the problem with a quadratic solution in mind, but the scientific committee discovered an NlogN solution of which all I've heard is really icky. I'm sure I'll hear the solution soonish though. All-in-all a very nice problem set in my opinion.

So back to the task scrutinising. We had a couple minor issues with the task descriptions, but as we never considered them problematic enough for our team we never reported them. There was a total of ten minor and one major objection. The major objection was from the Croatian team that they had a similar problem to Islands in their national contest last year. The scientific committee said they were aware of this task and considered it significantly different enough to keep the task and everyone took their word for it without further question. Besides one minor objection, which I cannot remember, the others were all accepted. Then their was one guy who blurted out something minor about the Islands task that he wanted to be considered a major issue. Fortunately the voting process stepped in quickly which democratically calmed him down.

Once the tasks were accepted we moved onto translation. One advantage of coming from an English speaking country, however, is that we get to mingle with the other English speaking countries instead! It took a good while for them to bring in dinner and it arrived cold, as we have become so used to. I could have easily downed two of those meals, but many people had to wait for the second and even third batch to arrive so I never did.

Peter and I ended up spending most of the time, and yes it was a long time, chatting with the Brits and Troy. We kept wandering just when they'd let us leave, a major point of discussion in all years as we have to wait for the contestants to return from their activities and get back to their rooms so as not to meet with the leaders who have seen the tasks. We also have to wait for the tasks to be finalised, which thankfully has hasn't been a bottleneck so far this year.

After we got sick of debating on the Egyptian definition of "soon" I went to go have a talk with the Ghana and Nigerian leaders. We discussed some of the issues that they've been having in running their national contest to select their teams for the IOI. They sound very enthusiastic about getting involved and are even set on entering some teams into our ACM ICPC regional contest for Southern Africa with the eventual aim to break away and form their own West African regional. They're very eager and think they can get at least 6 countries from West Africa to participate and they definitely have a strong backing from the government. I talked to the about the African contest for university students I've been running and they were very excited to hear more about it.

Eventually at about 23:30 we were told we could leave, which was half an hour sooner than our original estimates so one point to the organisers! We all ran straight for our rooms after getting the word so the day was over.

Tomorrow is the first day of competition from 09:00-14:00 with an online contest scheduled to start at 17:00 (14:00 GMT) while us leaders attend day one of the IOI Conference. This is followed by a trip down the Nile river.