Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Feb 28 '11 at 18:09

This question came from our site for professional and enthusiast programmers.

6 Answers 6

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

share|improve this answer

1) Read all tasks before starting. Order them in order of difficulty and do them from easiest to hardest.

2) The first thing to look at in every tasks is input range/amount and execution time. Using this information you will be able to roughly estimate what kind of algorithm they are expecting(eg is it linear, logarithmic, polynomial...) For example if in the task you will need to get through 1000000 input values in less then a second, that you can be assured that algorithm should be linear and start thinking in this direction without trying to implement any quicksorts or anything like that. So estimate O() first then think about algorithms.

3) Think before you do. Do not go straight to coding(unless you know the correct solution or solved similar task before). Spend a bit of time with pen and paper to solve the task in your mind. You should start coding only when you know how you are going to approach the problem.

4) Hack. Forget about good coding practice. You will not need to maintain this code later. So if you can save few minutes by hacking your way around - do it. 5) Do not optimize your code(unless you have finished all the tasks you could do and you have some spare time). If you have selected and implemented the correct algorithm you will almost always get at least 90% of scores for this task. Spending lots of time on getting the last 10% when you still have few tasks to finish is not a good idea.

6) Take couple of 5 minute breaks. (This helps me, but some say that they loose their concentration and advise against it)

share|improve this answer

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.

share|improve this answer
    
Unfortunately, as I mentioned above, it's not a group programming competition. It's solo only. –  sipefree Jul 27 '09 at 12:46

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)

share|improve this answer

I competed in the IOI back in '96 and did fairly well (top competitor from the UK, world bronze medal).

Here are some thoughts on preparation:

  • Practice all the core algorithm types. In particular, dynamic programming, divide-and-conquer recursive solutions, breadth-first-search and depth-first-search seemed to come up a lot.
  • Make sure you know all the shortcut functions in whatever language you are going to be using from memory. Simple string manipulation and maths you need to know off by heart for example as you don't want to waste any time looking things up.
  • Do all the past questions you can find. Possibly do them several times over. Invent some variations to test yourself.
  • Really know your algorithmic complexity. In the IOI, the difference between an O(n^2) and an O(n log n) algorithm can make all the difference. Some problems are specifically designed, for example, so that a O(n^2) approach is guaranteed to fail on the larger input sizes.

Here are some thoughts for the coding itself:

  • Have a read of all the problems first. You'll want to pick the easy ones to target first, plus I found that a couple of times I had a random brainwave that helped solve one of the later problems when I was working on an earlier one.
  • Time is limited, but not so limited that you don't have enough time to think. Stay calm and don't rush, you'll just make mistakes.
  • There is often an insight / shortcut that you can gain by really thinking about the problem. For example, reasoning about the properties of possible solutions can help you to optimise a search algorithm by pruning large impossible branches of the search tree. These kind of optimisations can make a real difference to the feasibility of your approach.
  • Don't start hacking blindly. I would usually solve the problem on paper first then start coding once I was sure I had the right approach / algorithm.
  • Look at the problem data size constraints. This will give you a clue about whether you can get away with a quick to code O(n^3) algorithm or not
  • Avoid debugging if you can - it's too time consuming. Try to write code very cleanly so that it is self-evident if you make a mistake. However it's probably worth writing one or two quick test cases as a sanity check if something isn't working.
share|improve this answer

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.

share|improve this answer
    
Unfortunately, the IOI involves solo problem solving only :( Thanks for the advice, however. –  sipefree Jul 22 '09 at 17:15
    
Really? In that case, go for the problems you know you stand a fair chance at getting correct quickly with minimal bug fixes. –  AlbertoPL Jul 22 '09 at 17:34
    
In IOI I always started by turning off the monitor and using at least the first hour on pure paper. –  Thomas Ahle Apr 12 '10 at 17:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.