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.

Comments

Programing out of Necessity

[guildsolutions]

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.

Re:Programing out of Necessity

[Nuclear Elephant]

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.

Re:Programing out of Necessity

[w98]

well, not every situation in life is a team effort though - there are tasks that one must do alone at work from time to time, so being able to at least sludge your way through a project on your own can be a real benefit to the company.

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)

Re:Programing out of Necessity

[ScrewMaster]

On the other hand (and I'm not really disagreeing with you, but) historically, the greatest works of art in any field have been created by individuals. Bach, Michelangelo, Leonardo Da Vinci ... all were inspired individuals with the vision and the talent to create a masterwork.

Of course, you're correct in that a lot of modern engineering tasks (software or any other kind) are complex beyond any single person's abilities, no matter how much of a genius they may be. And yes, teamwork is the way. However, if you look at most of the best engineering teams (I've been fortunate to work with a few along the way) there is often one individual that is the creative spark. He or she is the one that the others go to for inspiration, and that keeps the original vision of the project alive until it is complete. What makes a good team, in that context, is having someone capable of providing a stable sense of direction, and teammates that are happy working within the context of someone else's vision.

Of course, having a good design in the first place helps a lot too.

Good Public Relations

[dshaw858]

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

Re:Code before competition

[chrisjrn]

If you don't get your own teminal, sometime it can only be what you can write in 1-5 minutes. So generally, you can only code what I put in the article.

Why?

[NumberOneFan]

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.

Re:Why?

[Helios1182]

As opposed to the non-intellectual circle jerk that makes up most high school sports? These are students that like to program, ar probably good at it, and enjoy some competition. You can compete in almost everything. Chess, cooking, football, programming, rock climbing, gardening... If it drives you to become better at something you love, whats wrong with it?

Re:Code before competition

[Aneurysm]

Did you get preparation time before the questions were unveiled to write some preemptive code?

Re:Code before competition

[Aneurysm]

Cool, thanks for the replies and info. Know of any competitions in England by any chance? :)

Re:wow, another new low...

[techno-vampire]

this is not newsworthy and it's not very interesting

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?

Don't be too smart when brute force will do

[cos(x)]

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

Programming Competitions? - Booooooooo!

[Neelay Thaker]

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.

Problem solving is key

[xRelisH]

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.

Rounders

[Nuttles1]

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.

Write some software instead

[burris]

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.

Re:Real World competitive programming.

[Anonymous Coward]

When your Real Product needs some Real Power years from now, will you be happy with whatever language decision you made?

Competition based on speed can be rather stupid.

Coding Competitions Reward Bad Practice

[Jekler]

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.