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.
Competitive programming is a great way in the way that sex for sport is good.
/ rapid-prototyping-boot-camp"]
"Game in a Day" [/url] type ideas, as you can learn an immense amount by just 'doing', and even better, just 'doing' it with someone else to see where you go wrong.
If you're nervous, scared of your skills, etc: nothing's better then just straight immersion. You can't get too anxious if you're just *doing* it. You have to jump in with both your feet and start, or else you'll never get anywhere.
It's really great for those of us who are scared of a particular domain, of not understanding problems, and all in all it really does help in solidifying domain ideas and promoting learning.
A good example is something like the [url="http://www.unearthedgames.com/main/devdiary
Yes, I used programming and sex in the same sentence; it's one of those things I've always wanted to do.
- - - -
KickingDragon
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.
Simple really... to see if your skills best the other students. Nothing tests and grows one skills like competition.
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 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 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.
The worst that could happen is you not get any questions right. Funny thing is, you'd probably do better than at least 10 teams.
I've done college level programming contests, and the atmosphere was always "ok, be prepared, but this is for fun" We had a free lodging, free travel, and free food for the entire weekend. It was cool. Did we win? God no, we came in 12th IIRC, but it was a fun learning experience.
Some tips I remember:
1. Know who's good at what. We could only let 1 person from our 4 man group in the computer room at a time. He had to be able to type fast, correctly, and fix our mistakes. Basically the star of the show.
2. Know how your group works best. We found out the hard way that we worked 10x faster in 1 group on the same problem than 3 people + 1 on the computer working on different problems. I solve this problem, you help with that part, we move as fast as the fastest guy, and we provide each aspect. Algorythm, code, SA+D, etc.
3. Sometimes is good to write down the different parts of the problem. Especially on the graphical questions, and geometrical problems.
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.