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.
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.
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.
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.
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