Don’t be surprise if you find this blog somehow read like a mathematical precise proof, just like my other assignments. I had been working on the three assignments, which were all due today, for 2 days. The CAS professors always want to keep we graduate students busy and busier, so I really did not have enough time to update the story I had since I came back from ACM 2005 Day 2.
As we can seen in Pictures, most of the pictures I took during the contest were already uploaded. My team worked out one problem and we were ranked at 45th place, out of more than 130 teams. The 15th place, McMonkeys, another team of us, got three problems correct. The first four places, two from University of Waterloo, two from University of Toronto, had worked out all eight problems. More results can be found here.
The real contest problem set can be downloaded at here, as well as judges’ solutions. The problem we worked out is problem D, as known as “Queens, Knights and Pawns”. We spent less than 2 hours on it, and actually more than 30 minutes were debugging. It turned out that it was a mistake in setting the maximum size of the chess board. For the rest of the time, we worked on 3 other problems but had some problems in designing the algorithms.
To solve this kind of problems in contest, it really needs people to concentrate on the details and be careful on the special cases when testing. Most of the time the speed of coding is more important than skill of designing an algorithm with less running time complexity or more efficient. Programming in a contest and programming in software production are different, but both require a good understanding on the problems you are facing before the coding. Once the idea is correct and the frame of algorithm becomes clear enough, go for it. A good resource for practicing such problems, is http://acm.uva.es/problemset/
After the contest, all contestants were invited to the dinner. I like the food.
