Preparation for the South African Programming Olympiad (SAPO)

  1. Talent Search
  2. First Round
    1. Learning Python
    2. Practice
    3. Algorithms and Data Structures
    4. General Advice
    5. Ask Questions
  3. Final Round
    1. Practice
    2. Algorithms and Data Structures
    3. Other Contests
  4. International Olympiad in Informatics (IOI)

Talent Search

The talent search round of the SAPO is like an aptitude test. Therefore you should not need to prepare for it.

First Round

The first round is a test of programming and basic algorithms and data structures. It is considerably different to the talent search, although a high mark in the talent search is an indication of potential to do well in the first round. The sections below outline how to prepare for the first round from learning to program to mastering the ultimate fifth problem.

Learning Python

If you have no experience with programming then Python is a great language to start with. If you have learned Java, Pascal or Delphi at school, or any other language for that matter, you might also be interested in learning Python due to the large cash prizes available, as well as being generally interested in learning a new programming language. Note: As of 2014, using Python does not give an additional cash prize for the final round.

The free ebook A Byte of Python is targeted at beginner programmers (i.e. if you have little or no knowledge of programming). You can read it online or download a PDF. It covers downloading and installing Python so those instructions won't be repeated here.

Dive Into Python is another free ebook, but targeted at experienced programmers looking for a rapid jump into Python. It is useful if you are already thoroughly understand another programming language. You can read it online or download a PDF.

Using Python in the SAPO after learning it the night before is a bad idea!

Practice

The Computer Olympiad website has a collection of the first round papers dating back to 2003 here. Some solutions are available here. Solving these problems as practice will prepare you well for the first round. You should also time yourself, remembering that the paper is two hours long.

For those who complete all the past first round papers and want more challenging problems to practice on, there's plenty such resources! The best place to go is the USACO Training Program, which allow you to progress from easy to very challenging problems as well as testing them against secret test data. This is an excellent resource and has several problems with a wide range of difficulty.

Algorithms and Data Structures

In the OPEN division, the fifth problem (as well as sometimes the fourth) almost always tests algorithms and/or data structures. The USACO Training Program mentioned above has some articles as you proceed through the problems. Another useful collection of articles on data structures and algorithms is by Bruce Merry, the most successful SAPO contestant to date, available here.

General Advice

There are many aspects of contest programming that differ from everyday programming. You do not need to check that the input matches the constraints -- these are only there to give you a guarantee on the input.

Time is everything. You only have two hours to solve five problems. If you think the problems are easy, try time yourself while doing one of the past papers. This is where Python becomes useful as the code is almost always at least half the length of Java or Pascal code. You do not need to go for the most complex solution, just one that solves the problem for the provided test cases in a reasonable amount of time and memory. The fifth (and sometimes also fourth) problem will require a clever solution, even if a brute force solution would work on smaller data.

The "Test your program with" inputs are the ones used in marking, so make sure you do test your program on them and that once you are satisfied with the answers move on to the next problem. There is also an additional 5 marks per problem (in addition to the 15 for correct answers) assigned to your code, so don't try hard coding the answers! And while you don't have to spend half the time beautifying your code, don't send us hideous code either.

Ask Questions

The best way to learn is to ask questions. For questions regarding administration and general matters, send an e-mail to info@olympiad.org.za. For training matters, please approach your IT teacher, or on of the many forums that deal with algorithms or specific languages.

Final Round

The top +/- 12 contestants from the first round are invited to the University of Cape Town to participate in the final round of the SAPO. This is a lot tougher than the first round, making preparation vital.

Practice

There is a large collection of past final round and even more challenging training camp problems available here. There are online evaluation systems for the problems going back to 2002, where you can submit solutions for evaluation. The evaluation system is the same as you will use for the final round, so it would be a good idea to become familiar with it beforehand.

Continue churning through the USACO Training Program mentioned above. As you progress you will find that the problems quickly reach very challenging levels.

Algorithms and Data Structures

Algorithms and data structures become far more important in the final round. With a decent understanding of dynamic programming and graph theory you will do well.

There is an archive of presentations from IOI training camps available here as well as a long list of algorithm tutorials on TopCoder

Other Contests

Competitive programming has becoming very popular in recent years and so there are now many programming contests. USACO host a number of contests, although none are between our first and final rounds. TopCoder has weekly algorithm contests, which are only 75 minutes long. There are many more, especially once you make it into university level.

International Olympiad in Informatics (IOI)

If you come in a top ranking in the final round then you will enter a full training programming at the University of Cape Town. This forms the basis of team selection for the IOI and if you make it this far then preparation gets a lot more intense.