Bart Massey

and Mike Vanier talk about programming contests such as the ACM International Collegiate Programming Competition.

Well, since I’m being told that I love ranting, I have to join this one. ;-)

I never participated in a contest except the Bundeswettbewerb Informatik back in (pre-university) school. In my opinion that contest was quite different for a number of reasons: most of the participants didn’t have any IT classes at school. And noone “trained” for that contest. Also the contest isn’t a speed contest, but you have a couple of months to solve a number of problems that most of us would find rather easy - for pupils aged 15-18 with no real CS classes they aren’t that easy. Even in the later rounds, time isn’t the main constriction - you have several weeks - and the programs are also judged by their code quality, documentation and design. I think you were allowed to participate in teams during the first and maybe second round.

A friend of mine pointed out the ACM chellege to me; but we never really managed to form a team since everybody was too busy. We never actually did a training session (though I myself solved a couple of the valladoloid online judge problems), and we didn’t submit our participitation. Though we would have automatically won our local contest, since I’m not aware of any teams by our universities here (despite them being top-ranked universities).

In general, Germany isn’t very much involved in this contest, despite being an “international” contest. This has various reasons. On one hand, CS teaching in germany is not much about just writing code. You’ll of course learn the basics, but even when they’ve finished their degree, most will be really slow in writing code. Instead, the focus is on modeling and the theoretical background. In my opinion, that is very good. You’ll always be able to improve your “basic” code writing skills later; that is mostly experience and routine. But you won’t be learning much theoretical background in your job later on.

Having worked on a number of the {old, archived, training} problem sets, I’m not convinced that this contest makes much sense. To succeed with the problem sets you need to be able to

  • Quickly find the common problem hidden in the written task (note that language barriers can make a difference here)
  • Write a parser quickly for the data sets you have to work on
  • Implement an appropriate data structure
  • Implement the (known) best algorithm for the problem; a second best algorithm usually won’t do, the judges will have a data set to make it fail the time or memory constraints
  • Coordinate computer use among your team

I agree with the others that I don’t think team-play is of much value in this contest; nor will you be doing much creative work. In my opinion it’s all about reducing the given problem to one of the known problems (e.g. longest common subsequence, shortest path, maximum flow), then adopting an algorithm to it. I’d call that reproductive work. In my opinion, they’re rather boring. Basically you’re expected to solve them using a certain algorithm. You aren’t judged by good or smart solutions either. Just by speed.

The (high-school) programming contest mentioned earlier was more interesting. For example there was the task of navigating a robot on a factory floor without any state information, and only a limited view. The robot was not allowed to keep any information. Such as “I need to go out of this dead end” or “that is a dead end”. It would easily walk into a path just to notice after a few steps (it had a limited view!) that this is a dead end, then try to walk out - just to walk in again, having forgotten that it’s a dead end. You of course can’t judge solutions without inspecting the code.

Smart programmers found a few ways to “cheat” here - and got extra credit here. For example one robot, when noticing that it’s in a dead end it might forget, would step up to the wall. And whenever it was close to a wall, it would follow it, and thus walk out of the dead end. Some heuristics making it step away from the wall again made it much more successful than others. Another “cheat” involved calculating “remaining steps allowed - distance to destination mod 2”. It then could be programmed with two alternating behaviours and switch between them by just not moving for one turn.

I don’t think there is any room for such great ideas in the ACM contest.