Preparation for the South African Programming Olympiad (SAPO)

  1. First Round
  2. Second 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)

First Round

The first round of SAPO is open for one week in July or August. The contest lasts for 1 hour and consists of three questions, each containing usually four to six test cases of varying complexity. The questions will ask you to write and debug a program that solves a given task.

This round tests the basic fundamentals of programming. For example, if you're familar with if-statements, for loops, while loops and basic arrays/lists, then the first round should not be much trouble.

Second Round

The second round is open on a given day, usually within three weeks of Round 1. The contest itself is 2 hours long and consists of either three or four questions of a more challenge nature than that of the previous round. Each question may consist of different subtasks of increasing difficulty. The aim of this round is similar to the previous round (write code to solve a problem), however this time you will be required to submit your code on our online evaluator. It therefore must produce the exact correct output for every test case in order to score full marks.

This round goes beyond programming basics and tests elementary algorithms and data structures. The sections below outline how to prepare for the second round from learning to program to mastering the more challenging questions.

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 as a new programming language.

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 as a PDF here.

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

Practice

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

For those who complete all the past second round papers and want more challenging problems to practice on, there are plenty of such resources! The best place to go is the USACO Training Program, which allows you to progress from easy to very challenging problems as well as testing your code 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 second round, the fourth problem (as well as sometimes the third) 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 four problems in Round 2. 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 less than 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 fourth (and sometimes also third) problem will require a clever solution, even if a brute force solution would work on smaller data.

It's not enough to check that your program works only on the example inputs given in the task statement. Also test larger test cases (up to the highest values the input can be) as well as corner cases (which might not get tested if one only generates random test data).

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 second 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 second round, making preparation vital.

Practice

There is a large collection of past final round and even more challenging training camp problems available here. There is an online evaluation system for the problems going back to 2002 avaiable here, 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.