Contents
-
First Round
-
Second Round
- Learning Python
- Practice
-
Algorithms and Data Structures
- General Advice
- Ask Questions
-
Final Round
- Practice
-
Algorithms and Data Structures
- Other Contests
-
International Olympiad in Informatics (IOI)
-
External Links
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 familiar with if-statements, for loops, while
loops and basic arrays/lists, then the first round should not be
much trouble.
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 three to five 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.
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.
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! One place you can 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. A more modern resource is
USACO Guide, which has many
explanations of algorithms and data structures as well as
example problems and their solutions.
In the second round, the last problem (as well as sometimes
the one before it) almost always tests algorithms and/or data
structures. The USACO Training Program and USACO Guide mentioned
above have many great articles. Another useful
collection of articles on data structures and algorithms is by
Bruce Merry, the most successful SAPO contestant to date,
available
here.
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
timing 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, C++ 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 last problem (and sometimes also the one before it) will
require a clever solution, even if a brute force solution could
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).
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.
The top ~15 contestants from the second round are invited to
participate in the final round of the SAPO. This is a lot tougher
than the second round, making preparation vital.
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 available
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 and USACO Guide
mentioned above. As you progress you will find that the problems
quickly reach very challenging levels.
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.
Competitive programming has becoming very popular in recent
years and there are now many programming contests.
USACO hosts a number of contests,
although none are between our first and final rounds.
Codeforces is another great
platform which hosts a 2-3h contest every few days.
If you perform well enough at the final round then you will
be invited to the training camps. This forms the basis of team
selection for the IOI and if you make it this far, preparation will
become much more intense.
-
Other Olympiads and training facilities
-
IOI website:
This page has all past IOI problems, as well as
links to many national and regional Olympiads.
You might also find the IOI syllabus to be useful.
-
USACO Guide:
A free collection of curated, high-quality resources
about many common techniques in programming olympiads,
along with extensive problemsets to use for practise.
-
CP-Algorithms:
a resource to learn about competitive programming algorithms
and data-structures. It is a translation of the Russian
website e-maxx.ru/algo.
-
Codeforces:
hosts online contests once every few days. They have
a rating system and most contests are in the afternoon
in South African time.
-
CSES Problemset:
contains a collection of algorithm programming practice problems.
They also host some past papers of a few European Informatics olympiads.
-
UVa online judge:
has thousands of problems with online evaluation.
-
oj.uz:
An online judge that can be used to test solutions to
many past IOI and other olympiad problems.
-
ICPC: the
big international university contest.
-
Programming books
 Handout.png){kind=link}