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.
Hopefully this type of a story will encourage other high school and college students to go into competitive programming. I know that I, at least, am nervous to start in programming competitions, but I think that having a real "just like me" article/guide on the subject will help boost interest.
All in all, good PR.
- dshaw
The article mentions writing template code before the competition begins. How much code do these competitions generally let you rock up with? Could you turn up with huge preprogrammed libraries ready to deal with any situation? I know the questions would probably be rather obscure, but surely you get an unfair advantage by coming with preprepared code. Surely only allowing competitors standard libraries is the easiest way to make things fair.
- 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)).
My team competed (and won first place in) several high school computer programming contests at the colleges in New England back in my day (Plymouth State, St. Anselm, etc). I'm not sure what today's competitions look like, but the team concept made things work here. I was the code monkey of the group, and the rest had their own strengths. Prior to my coming onboard, the team continually lost - not because they weren't smart, but they weren't complete. They were very strong in figuring out solutions to problems, while I was very strong at taking those solutions and laying them out in code. That's one of the reasons I'm suspicious of the 'one-man' competitions, as real-life work challenges are often team-oriented. As adults, most of us have learned to wear many of the different hats (problem solving, mathematics, coding, etc), but building a strong team based on members' strengths still usually makes the difference between mediocre products and works of art. That's just my 2c.
Just one tip:
Needs more Caffeine.
Why is "competetive programming" so great? I'm not trying to troll, but is this for some lack of being able to compete in sports or something? Why does this too have to be competitive? It seems like everything in here has to be tested and ranked.
My university had a team, I went to one meeting and realised how stupid and hokey it was. Half of it was an intellectual circle-jerk and the other half was some practicing. All too l4m3.
Now there's a scary yearbook shot
My school participated in a competition once, and we didn't do too well. One of our teams coming in hung over and running on two hours of sleep probably didn't help.
Want to get involved with some competitive programming, right now?
TopCoder is always looking for more members. The algorithm compeitions only take a few hours, and can pay good money. Plus discussion of the algorithms afterwards with the other members can be quite enlightening.
They also do design and development competitions, which take a bit longer, but pay a lot better. You can also pick up cash by being a reviewer for these compeitions, if you pick up enough "scratch" in the compeitions themselves.
You get individually rated on each of the 3 competitions and TC also provides some measure of employment services.
Back when algorithm competitions always paid, I earned my 1/2 of rent through them. After I graduated from college I paid my bills through a combination of design / development / reviewing. Now I work for TopCoder as a salaried employee.
Check it out, and look me up. My member handle is the same as my /. handle, just without the spaces.
TopCoder can be very rewarding. I hope every programmer that reads this at least looks at the website.
Competitive programming can be addicting, I started on highschool just for fun on a small local contest, then me and my mate moved to the national olympiads, we were there just for the fun of it, but i actually got a good place. Then it started to get addicting, we were participating on every kind of contest, i won the national olympiad that year and therefore went to the International Olympiads in Informatics. This year i went to the IOI again. Just a word of wisdom, do _NOT_ get carried away by these contestes, they are good for fun but if you get addicted, they can even harm your studies.
The company I'm at has a big C#/ASP.NET application, but a couple marketing guys were doing UI prototyping in Ruby/Rails that appears to be nearing feature completion faster than the "real product". It's kinda fun to see - but in the end only one of the two solutions will survive - perhaps with quite a few people's jobs on the line as the prize.
If you're not interested, don't read it. Some of us do find it interesting, either because we're programmers or because we like to compete. Slashdot carries many articles on different topics, making it more interesting for more people. If all you want is stories that interest you, and don't want any others posted, why don't you found your own site, so that you have the final editorial say?
Good, inexpensive web hosting
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 problems I encountered there (which I solved in java) were far more difficult than the stuff I do at work (as a PHP/Javascript/MySQL lead web dev). One of the Google Code Jam problems was a real brain twister:
Two rocks are dropped in a pond, and create square ripples. For example, a rock of weight 8 is dropped at a point -- at time zero, it creates a ripple of height 8 at the point it was dropped. at time zero, it creates a 3x3 square ripple of height 7, like so:
The problem: given these rules, find the highest ripple height given the locations, drop times and weights of two stones. (If two ripples overlap, the height is equal to the sum of their heights - i.e. if a height 3 and height 4 ripple both occupy the same point, the height at that point is then 7)
The solution 90% of us tried was to simply brute force the problem, creating an array, and updating the array over and over again, comparing the ripple heights to the previous max. The maximum area we were supposed to check was 2000 x 2000 -- so the brute force method timed out (there's a pretty short execution time limit).
The correct solution was to consider time as a third dimension; each rock creates a 4 sided pyramid. Then you only need to check 3 points, which can be done with simple equations: the 'peak' of each pyramid (the height of which happens to be the weight of the corresponding rock) and the intersection of the two pyramids.
Did I mention that there were 4 problems, of which this was the second, all of which had to be solved in a grand total of 90 minutes? And that your score decreases every minute you spend on a problem?
Yeah... TopCoder's rough. And no, custom pre-written libraries won't win this for you -- but they will save you a little time.
So I'm a hot shot junior programmer, ready to take on my assignment. Here was the problem: "You have a number of cities mapped on an x,y grid. A travelling salesman wants to find the shortest route between the cities. Calculate the shortest route." We had two hours or something.
I'd never heard of this problem before.
So I was like, "Hey, no problem. This is eeeeeasy." So I went off in my youthful exuberance with a blank piece of paper, figuring out how to solve it. Hmmm. That idea was good -- except it wouldn't work for this one case. How about this idea -- nope, that one will hang up on this other case.
Minutes ticked away as I sweated the problem. There HAD to be a solution to this. Half an hour, then an hour -- I'm growing desperate. What the hell? This problem is freaking hard. Finally I'm like, "screw it" and threw something together at the last minute. We ended up losing because I spent too much time thinking about it.
I still think it was goddamn unfair to give an UNSOLVED PROBLEM in a programming contest for high school students. I'm still pissed about it to this day. Grrr. :D
Sometimes it's best to just let stupid people be stupid.
My last job had a total of three programmers, and we all worked on different areas of the system, and only towards what was the eventual end of my employment there (I left for a much better job) did we actually interact and connect some of the pieces together.
You're right though, in a team situation, things can be done so much faster if you've got a team leader who can recognize skills and traits and assign tasks accordingly. But not every company will have a team of that many people on everything.
Even at my current job, where we have a very large development team, there are still individual jobs to get done, and there are other jobs that require a team of 3-4 or even collaboration between two or three whole departments.
And that's my $0.02 ;o)
my geeklog
I recently competed in the UNSW ProgComp ('largest competition within Australia'). We only came third place, due to good competition this year (we won in 2003 with VB against Perl, Haskell and C++, heh :).
Although I think the article fails to mention the organisation of 'computer time'. The Australian Computer Programming Competition and the ProgComp both allow three members in a team, but only one computer between the three of them. This means that you have to organise the priority and the division of problems amongst your teammates. Also, learning to code on paper is another important skill, as you won't have access to a keyboard the whole time. Therefore, having access to a printer is extremely helpful as you can just print and debug your code.
Due to the nature of some languages, they restrict languages like Java and Python in the bigger competitions (IOI, ACPC) due to the large amount of standard libraries they get to play with. For example, I wasted half an hour coding Task 4 before I realised we could switch languages halfway through the competition and got it done in 15 lines with Python with regex.
Finally, you do not need to have a team that consists entirely of programmers. In our team (for this year), we had two programmers, one to do the algorithmic ones (my friend, who represented Australia in the International Informatics and returned with a bronze medal), one to do the string-based ones (me), and another person to solve the problems by hand. Although, due to ProgComp deciding to have less algorithmic questions, my friend was only able to use his skill effectively on one question and the rest were split up between us. We had our third team member solve Task 3 though, and just coded a small program to decode it using the supplied decryption matrix.
I won't be able to compete in high school competitions anymore as it is my final year, but I wish the rest of you, who are still able to compete, luck.
Founder of Mirror Moon - Tsukihime Game Trans
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.