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.
My programing skills came from Necessity, a group of people I was with needed a website and nobody could do it. I knew the basics of C programing so I picked up PHP and went from there. Tidbits like this can be very helpfull to the self taught, school taught and clueless.. Personal experiences with programing is golden, always.
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)).
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.
I used to compete in programming competitions during my junior and senior years in a Texas high school. I competed in TCEA and UIL. I did pretty well, though there were never any cash prizes. I always had a lot of fun due to the camaraderie with fellow classmates from my school, and I guess I got recognition for winning. However, the problems were relatively easy, with no complicated graph theory problems and the like.
My school had a great computer club with a enthusiastic sponsor that went to local programming contests held by other high schools about once or twice a month. HP (previously Compaq) also holds their own annual competition in Houston, called Code Wars. I guess it was easy for me to get involved because this was part of a school club.
Now I'm in college and the ACM ICPC and high level TopCoder problems kick my butt. I need to learn more algorithms.
Fetch Text URL - Firefox Extension
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
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
If I hit my head against this wall, that almost makes sense.
I know a couple of the comments he makes to make you better like creating a template can and most likely are against the rules (I can attest to at least one competition that it is). And he is correct that more languages you know the easier it is if you switch between them. I remember one problem, that was easily solved in 2 short lines of Perl, which required the C coders to write quite a few more then that.
Your hair look like poop, Bob! - Wanker.
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.
In 2004, my team won the eliminations in New Zealand and we went on to the ICPC World Finals in Prague. Up to the finals, we were expected to write clever programs using efficient algorithms that ran blazingly fast. Then, at the finals, it was all about hacking up crude semi-brute-force approaches that didn't work efficiently at all but got the job done. We were by far not the only team to do badly because at the finals because it took us hours to figure out that the clever algorithms we were coming up with were not necessary here at all.
So, my advice is, try to find out as soon as possible (preferably before the competition, at the very beginning otherwise) whether they want smart algorithms or just something that works. It can save you a lot of time during the contest.
Online contests are a good practice. For example, the Saratov State University (http://acm.sgu.ru/) has harsh time and memory limits while other contest sites give you heaps of resources to use.
Live online contests are also great fun and practice. I remember winning a T-Shirt and some money at Bitwise a couple of years ago solving some neat problems in the process.
Finally, practice makes perfect. Get old problems and practice, practice, practice, ...
I wrote the Canadian Computing Competition (Junior Level) last year. I was in grade 10, most of the contestants were grade 11, and I placed tenth out of about 550. If I had read that article beforehand, I would still have placed tenth out of about 550.
I have always been reluctant to try a hand at programming competitions because of the time factor that they entail. Different kinds of problems are suited for different kinds of programming languages. In a competition where the programmers are hammered with one problem after another, it is difficult to make a switch from one programming language to the other in a matter of minutes, even if you have been programming extensively in two or three languages. Refering to books and other resources for syntactic reference doesnot do good as it takes time. I find these competitions more a measure of typing speed and quick fix solutions rather than an assessment of creativity, quality programming and problem solving skills. In my opinion, a problem solving contest would be a better idea, where contestants could write down or type algorithmic solutions to problems and the most efficient solution would get rewarded. Ofcourse, evaluating such a contest would be more difficult too.
I was part of a University team that did quite well during the years. Our best result was 2nd in New Zealand for one competition.
Anway - some tips:
1. Read the question extremely closely before you start. It is frustrating to miss an important detail *after* you've written a lot of code.
2. Plan carefully before you start. One of my team members was very talented at finding approaches that would work without problems. The other two members of our team could then implement them reliably. You cannot waste time on an incorrect approach.
3. Have some algorithms pre-prepared. Examine previous questions for clues. Generally, we always saw date style problems (what day of the week is 24 November, 3100?) and area style (take a sheet of metal, cut out some shapes, what area is left?) problems. Both of those tended to be difficult and worth a lot to fix. Having an infinite precision math library ready to go is very useful.
4. Keep track of time and don't ever give up coding. You might get the answer in just before the deadline and that can be the difference.
I think there was too much focus on the coding itself in the guide. When it comes down to it, its the ability to solve problems.
The best way to practice for a programming competition is to treat it like a math competition. If you can think of efficient solutions and apply them quickly, you will do well. Remember that a lot of these competitions have runtime limits (usually 2-3 seconds on a predetermied isolated machine), so coding up the simplest solution won't always work.
Practice is also very important. Try ACSL, there are some sample problems available there, practice doing them and time yourself!
Also, for those who say that programming competitions are useless, they have no clue what they are talking about. What sets you apart in real-world development involves thinking up efficient solutions to difficult problems. Making the code easy to maintain and expand is just a simple step up when you do development in the industry.
As with many things this story can be understood by relating it to Rounders the movie. When Knish says, "Alimony, child support, my kids eat. I'm not playing for the thrill of f**king victory." Competitive programming, oh my, I program for money, not prizes. Even if those prizes are some cash. At the end of the day I want my check every time, I don't care if I am the absolute best, crap, I am better than most without even putting effort in. If I want to gamble I go to the Hold'em tables.
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 did a couple Regional ACM competitions, a few local ones, etc. They were fun, after the first one. My recommendations:
1. Know your environment. The competitions I've been to give you some time on the computers before the competition to get to know the environment, compiler, IDE, etc. Make good use of it. If they have Eclipse, what version of Java, gcc, pascal, etc. Know the editor you are going to use. Do they have emacs, vi, etc? Knowing your environment will greatly reduce your write-compile-test time, which is critical during a competition.
2. If writing templates beforehand is not allowed, bring one in on paper and take the 2 minutes beforehand (with the fastest typest in the group) to type it up. Ours consisted of an input loop/string parser with a loop that could be easily changed to accept input from the terminal (required for submitted programs) or a file (easier for testing sample input files.)
3. Know your language(s). Know what's allowed in the competition, have several references handy for each language you plan to use. My team tended to use Java, but at the time there wasn't a built-in priority queue in Java. Dijkstra's shortest path algorithm requires a priority queue, so I spent some time before hand coming up with a very easy to type ( 1 page) general purpose priority queue. We weren't allowed any electronic resources, but if you can type fast enough, you can create any basic structure you need very quickly. When built-in structures are available, USE THEM, and use them extensively.
4. Do the easiest problems first. Simple math will show you that you get the most points this way.
5. Study existing problems. The local competitions tended to repeat problems from other regional (or national) competitions. We used those to practice from, so it made it a breeze when those problems came up.
6. Don't get hung up on a problem. You'll waste tons of time, and there's ALWAYS the possibility that the submission checker is WRONG and your problem is right. Its happened at both regional competitions. They eventually find their mistake and your previous submission will be counted as correct.
7. Practice. You'll get used to the problems and be able to analyze how long a particular problem will take much easier. You'll get to know your teammate's strengths and weaknesses. One teammate of mine was very good at solving problems but his coding skills were a bit off. He'd write up the solution, I'd debug his programs. We did quite well that way.
Competitive programming looks like fun and I think you can learn quite a bit from it. You can also earn reputation capital that can help in getting a job. I would think most employers would be more impressed with a high rank on a competitive site than with paid certs.
That said, I think "undiscovered developers wanting to get a break" should spend most of their time writing some useful software or web application instead. You get more experience than just solving puzzles at breakneck speed. Writing a good piece of software or site that your interviewer has used goes further than anything short of a personal recommendation. When people use your software and are impressed with your skillz, work comes to you. Plus, you could end up founding a software business that makes you a millionare.
There are a lot of opportunities out there.
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.
I'm not a big fan of programming competitions. They score people on bad programming practice. The skills that make you the best competitor are frequently the same habits that make you the guy everyone venomously whispers about in the cafeteria.
They reward you for coding fast, hacking out make-shift solutions (i.e. Code that could never pass QA), and the given problems are too narrow to be representative of a real programming problem. You can ignore things like portability issues, standards compliance, elegance, orthogonality, modularity and maintainability.
Real programming skills, the things that really set the master programmers apart, play absolutely no role. Namely: Source control and documentation. Most types of "competitive science" won't work well. At least the type where you can't build your project ahead of time. You're going to get the same quality work out of "speed programming" that you'll get out of "speed chemistry". Wouldn't that be fun? Get a room full of chemists together with a bunch of components and tell them to mix real fast, no time for measuring!
That's my take on the whole Competitive Coding atmosphere.
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.