Slashdot Mirror
Introduction to Competitive Programming
chrisjrn writes "Last year, I unexpectedly found myself entered in the Australian Computer Programming Competition, and somehow did well in it. As a result I decided to write a guide as an introduction, for high school-level students (and others, I suppose,) into the world of programming competitively based on my experience, and how to go about successfully competing in competitions." Article looks like a good start, I'm sure Slashdot readers can add many more tidbits of wisdom.
- ACM International Collegiate Programming Contest: http://icpc.baylor.edu/icpc/ (Big competition between colleges worldwide - sort of the equivalent of the IOI at the university level).
- TopCoder: http://www.topcoder.com/tc (weekly matches, yearly competition with large cash prize, also hosts the Google Code Jam (http://google.com/codejam)).
In the Competition in India, we had around 10 minutes to get used to the IDE and compiler, and we used that to have our code ready. Most other comps are the same.
In the ICPC, we were given a test problem to work on. We had an hour to complete it, and it was a chance for them to work out any bugs with the network answer submission process before the competition started. Unfortunately, anything we coded up in that hour got wiped before the start of the real competition. The practice problem was also easy. It was something like, take 10 strings from this file, reverse them, and print them to the screen.
I don't, but I'd assume that you have a National Informatics Olympiad. The best thing to do would be to Google it :).
If you're in college still, ICPC = "International Collegiate Programming Contest." The site seems down at the moment, but it's usually at http://acm.baylor.edu/acmicpc or http://icpc.baylor.edu/icpc/
Make sure you know the IDE(s) that you'll have to use. When I went to my first competition, I was only familar with Borland's C++ IDE. Unfortunatly, I could only use Visual Studio. If it wasn't for my partner being familar with Visual Studio, I would have lost time getting used to it.
No, I will not work for your startup
I learned about it only because my school's chapter of the ACM always participated. The division I'm in covers the mcuh of the west coast of the US and the west coast of Canada. There were over 100 teams last year. It really sucks to be in the same division as Stanford, UC Berkeley, and British Columbia.
One of the best known contests is the ICFP (International Conference on Functional Programming) Contest. One great thing about it is that entries can be in any language. Therefore many consider it a competition between languages as much as between programmers.
0 5/30/036201&tid=156&tid=162
1 8252&tid=156&tid=8
The winners to the 2005 ICFP contest are set to be announced this month (Sep 27th). Here're a couple of slashdot threads about it:
http://developers.slashdot.org/article.pl?sid=05/
http://it.slashdot.org/article.pl?sid=05/06/26/00
The problem isn't unsolved, its just NP-Complete, and would have taken the computer longer than the 90 minutes allotted to solve a data set of an meaningful size.
Could become a representative for Great Britian to the International Olympiad of Informatics next summer, to be held in Mexico.
If you're in northern Ireland, you'd compete in the Irish Schools' Programming Competition.
You can also compete in online contests such as USA Computer Olympiad (operated in the USA, but open to everyone), or a quick google search will yield more.
I competed and coached for several years in the ACM Scholastic programming competitions. To this day, my school (the University of Central Florida) routinely places all three of their teams in the top ten of every regional, so it's safe to say that our method is tried and true.
Some of the major facets that we coach:
1. Easiest problems first. Appropriately applying a concept from computer science itself, the goal of a contest is to maximize your throughput. Since easy problems are worth as much as hard ones, effort should be made to discern which problems are easiest (as opposed to most interesting!).
2. Team roles. Back when contests had four people to a team, we had two people as "bangers" (i.e. people who sit at the terminal and quickly compose solutions to the easier problems) and two were "software engineers", who sat away from the terminal and worked on paper. Note that after the first hour or two of the competition, EVERYONE is a software engineer.
3. Specialize. In addition to roles, team members would typically have a specialty. Some people are good at algorithms; others at text processing; others at math problems, etc... This should all be worked out during practice to the point where every member of the team should be able to read a problem set and immediately tell who on the team will likely end up working on each problem.
4. Do as much work away from the terminal as possible. Since you only have one terminal (in the ACM contests), it should be considered a scarce resource. Priority should be placed on entering new code; if you are debugging and someone has written out new code that's ready to enter, take a printout of your program and let the other person on. An exception is made when the person debugging feels they are within five minutes of a solution.
5. Test extensively. This is the difference between a good team and a great team, in our experience. It is extremely tempting to submit your code once your program produces the correct output for the sample data. But it is not worth a failed submission.
6. Consistency. We didn't mandate particular coding conventions, but we did mandate that team members at least HAVE coding conventions. E.g. array names -- are they the plural or singular form of the word (node[i] vs. nodes[i])? Similarly for variables that keep count, method names, etc. Recalling such things while typing wastes valuable minutes.
7. Have practices that are genuine contest simulations. We even went so far as to shine lights in team member's faces and make lots of distracting noises, to simulate contest environments. On occasion we would even intentionally make mistakes in the problem sets and judging, just to prepare people for that (since it ALWAYS happens in the actual competition!).
There were others, but I can't give away all our secrets! Well, okay, maybe I just don't remember them all.
In our experience, it's the teams that consider contests to be all about "hacking" or "typing fast" that typically do very poorly. Those that apply good coding practices, and are consistent and organized are the ones that come out on top.
I object to that article, and to the next reply.
The most interesting thing I learned at the university later on was it is the cooperation that counts. I do not know why students should compete with each other when they will most often work in a team in their future jobs.
That is why I value Google Summer of Code so much; because it forces students to work together with ones they do not know: they learn the social part of programming. This is what most programmers lack; including me of course. Or else I would not be reading and contributing to this very forum...
I was introduced to a different type of programming competition when my team participated in New Mexico's Adventures in Supercomputing Challenge (in association with LANL) during my junior year of high school. We were granted time on a Cray, afforded accounts on a box running OSF/1 and a mentor from Sandia National Labs, and accommodated at a three-day programming retreat. Yet with all that preparation, we were totally unprepared for the presentational aspect of the competition, which was similar to a science fair. Our FORTRAN code was functional and the results were there, but we were unable to present our results effectively.