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

migration rejected from stackoverflow.com Jan 2 at 21:30

This question came from our site for professional and enthusiast programmers. Votes, comments, and answers are locked due to the question being closed here, but it may be eligible for editing and reopening on the site where it originated.

closed as too broad by gnat, World Engineer Jan 2 at 21:30

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs. If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer 1

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