tags:

views:

156

answers:

4

Hi folks-

I'm on the Irish team heading to the International Olympiad of Informatics in Bulgaria at the start of August, and from the great pools of wisdom of SA, I wish to ask a few questions of those of you who have competed in programming competitions (or indeed, the IOI) before.

Mainly, what tidbits of advice can you give for those competing? What's the best way (in your eyes) to go about solving a problem? I've got my own methods, but I am interested to hear your point of view.

How do you manage time? Is it worth loading troublesome code up in gdb to try to work out tricky bugs, or is it best to try to hack solutions? Is there even time to debug things properly?

I have been memorizing some algorithms, such as graph search algorithms, brute force algorithms, recursive algorithms, etc. What other common algorithms do you think are useful?

Thanks in advance.

A: 

It's been a while since I've been in a programming competition, but what I've found useful is to sit down AWAY from the computer, take out a pencil and paper, and start pseudocoding solutions with teammates. Talk about the pseudocode, and make sure it looks sound. Only then should you proceed to code it up and test it to see if it works.

Time management is pretty difficult in these competitions (as it's supposed to be). I'd say plan ahead of time how long you will spend writing pseudocode upfront and do not go beyond that amount, if it can be helped.

As for finding bugs etc., the best use of time would be to maximize the number of problems solved. This means you should attempt to debug a program, but do not do this for too long or you risk neglecting the other problems at hand. The faster your teammates finish other, easier problems, the more time they'll have to help with the more difficult problems.

AlbertoPL
Unfortunately, the IOI involves solo problem solving only :(Thanks for the advice, however.
sipefree
Really? In that case, go for the problems you know you stand a fair chance at getting correct quickly with minimal bug fixes.
AlbertoPL
In IOI I always started by turning off the monitor and using at least the first hour on pure paper.
Thomas Ahle
+3  A: 

Make sure to really understand the question and requirements before starting any coding. The biggest waste of time is solving the wrong problem!

Larry Watanabe
+1  A: 

instead of hacking, start with 1. getting requirements down correctly. 2. write english language test cases for each requirement 3. write an english language test case for each common case 4. code up the test cases 5. code up a stubbed program that can run all of the test cases (fine if it fails all of them)

At this point, you have nailed down your requirements, test cases, and interface. You now have gotten a better understanding of the problem in this process. Everyone is on the same page regarding what you are doing.

Now start 1. design - done together - some kind of informal document or whiteboard. 2. map test cases to design components 3. see if you can break down design into fairly modular components. 4. divide up components amont team. They now have a design component, set of test cases, and requirements each teammember can work on fairly independently. 5. Design interfaces for each component 6. Have each team member create and publish interface for ther components with stubs so it can be invoked. 7. Now each team member codes up their part. Some might be better at hackng, some might be better at designing on paper, then coding. It's an individual thing.

For some problems, it doens't make sense to split up among team members. If this is the case, you might just want to do pair or tea mprogramming.

Larry Watanabe
Unfortunately, as I mentioned above, it's not a group programming competition. It's solo only.
sipefree
+1  A: 

Practice ahead of time.

Read through all the problems quickly first. Figure out which problems will be easy and which will be hard. If you don't think you will be able to complete them all, do the easy ones first. If you do think you'll be able to do them all, start with the harder ones so that as you brain gets fatigued, you'll be working on easier problems.

Try to organize them so that you don't work on similar ones back-to-back so that you don't confuse yourself.

(I realize that August has long passed, but figured someone might run across this)

David Oneill