Ioi Syllabus 2015 Diff

The International Olympiad in Informatics Syllabus
changelog for the 2015 version and rationale
1 Change in the definition of Excluded topics

The main change to notice in the new version of the Syllabus is the change
in how Excluded topics are defined. The previous Syllabus version defined
these topics as follows:
Some of the harder algorithmic topics are explicitly marked as

excluded. It is guaranteed that there will not be a competition
task that requires the contestants to know these areas. In other
words, each competition task will have a perfect solution that
can be produced without the knowledge of these topics. This
category mainly contains hard textbook algorithms.
In the new Syllabus, the definition is changed to:
Some of the harder algorithmic topics are explicitly marked as

excluded. It is guaranteed that there will not be a competition
task that requires the contestants to know these areas.
Furthermore, the tasks will be set with the goal that knowledge
of Excluded topics should not help in obtaining simpler solutions
/ solutions worth more points.
This category mainly contains hard textbook algorithms and
advanced areas in mathematics.
Consider the editorial of the Codeforces problem 446E published here:

http://codeforces.com/blog/entry/13036. Clearly, a problem like this
is not something we want to see at the IOI. Still, one could argue that
this problem (with a few minor modifications) would be admissible under
1
The IOI Syllabus – Version 1.2 2
the previous Syllabus: it can be solved in 80 lines using modular addi-

tion/multiplication and divide-and-conquer, and can also be explained ele-
mentarily via summations.
The updated definition makes it clear that this is not the ISC’s intent.
In the cited case, there is a conceptually simpler approach using the Fast
Fourier Transform and Hadamard matrices, and the knowledge of these
advanced topics does make the task easier to solve. This makes it fall in the
Excluded category in the new Syllabus.
2 “Excluded, but open to discussion”

The ISC is currently discussing the fate of a small set of topics that are
labeled this way in the current Syllabus. We would appreciate all input
from the IOI community.
3 A better definition of prerequisites

It is now explicitly stated that the Syllabus is trying to specify two sets of
topics: a small set of topics that are considered prerequisite knowledge and
a second, larger set of topics that may occur in the solutions of competition
tasks.
The current revision specifies that the prerequisite knowledge falls into
the first two categories:
• “Included, unlimited” – e.g., all contestants are expected to know what

is a line segment.
• “Included, to be clarified” – e.g., all contestants are expected to know

what is a directed graph, and to understand the part of the statement
where it is specified whether the graph contains self-loops and/or mul-
tiple edges between the same vertices.
4 Changes in the set of topics

In this final section of this document we list the changes made to the set
of topics. The main motivation for the changes is to pick a set of topics
that is rich enough to generate many interesting problems, and at the same
time knowledge beyond the selected topics should be unlikely to help the
contestant. The intent here is that focusing on problem solving using a set
of well-defined tools can both ease the preparation of students for the IOI,
and remove the need to study out-of-syllabus topics.
4.1 New Explicitly excluded topics

A significant number of topics were added as Explicitly excluded. In effect,
this removes them from the implicit Out of focus category.
• Geometry in three or more dimensions.

• Linear programming in 3 or more dimensions and its geometric inter-
pretations.
• Point-line duality in 2-dimensional geometry.
• Halfspace intersection, Voronoi diagrams, Delaunay triangulations.
• Computing coordinates of circle intersections against lines and circles.
• Topics where linear algebraic perspectives can be helpful, including
the Fast Fourier Transform.
• Burnside lemma.
• Clustering algorithms (e.g. k-means, k-nearest neighbor).
• Primal-dual graph algorithms (e.g. minimum cost arborescence).
• Lexicographical BFS, maximum adjacency search and their properties.
• Hypergraphs.
Additionally, planar graphs were previously Out of focus. Planar graphs

themselves are now Included – a contestant should understand what is a
planar graph. However, non-trivial topics related to planar graphs (no-
tably planarity testing and planar separators) are now listed as Explicitly
excluded.
4.2 Floating-point numbers

Previously, floating-point numbers were Explicitly excluded. The current
Syllabus now lists as Included:
• elementary use of real numbers in numerically stable tasks

• the floating-point representation of real numbers, the existence of pre-
cision issues
but keeps as Explicitly excluded:
• analyzing and increasing precision of floating-point computations

• non-trivial calculations on floating point numbers, manipulating pre-

cision errors
The reason for this change is that the modular interface currently used
in all IOI tasks makes it possible to use tasks where real numbers occur but
precision issues don’t play a role. For instance, a task in which a contestant
computes the lengths of some line segments and outputs the shortest of
those lengths should be perfectly viable.
4.3 Data structures

More details were added to the section on data structures. The set of In-
cluded topics has been updated to cover some of the data structures used
in past IOI tasks, and to add several new data structures that the ISC
considers appropriate for future IOI tasks. The additions:
• Composition of data structures, e.g. two-dimensional statically bal-

anced binary trees.
(These have been used regularly, starting with IOI 2001 task Mobiles,
without being explicitly mentioned in the Syllabus.)
• Augmented binary search trees – storing, modifying and using addi-

tional information in the BST’s nodes.
• Balanced binary search trees.

(Problems may require the use of an efficient data structure that sup-
ports the required operations. There will not be problems that would
require the contestants to know a particular implementation. Hence,
any single implementation – e.g., treaps, splay trees, AVL trees, or
scapegoat trees – should be sufficient knowledge.)
Past submissions have shown that simple and concise implementations
of BBSTs are already known by a significant portion of the target
group of contestants. Already before BBSTs were in the Syllabus,
some contestants preferred them over more complicated static struc-
tures. This ranges back at least to the tasks Elephants (IOI 2011) and
Jousting Tournament (IOI 2012).
• O(log n) time algorithms for answering lowest common ancestor queries

in a static rooted tree.
• Creating persistent data structures by path copying or using fat nodes.

4.4 Other additions and reclassifications

• Finding connected components has been explicitly added as Included.
(This was omitted previously, as it is contained in computing transitive
closures, but we decided that it is better to state it explicitly.)
• Among the applications of depth-first search, algorithms to determine

an Euler path/cycle are now listed explicitly as Included.
• Pointers and references were shifted from Out of focus to Included.

There is no difference between implementations that use them and
implementations that use static arrays and indices instead.
(Additionally, basic understanding of pointers has already been neces-
sary in C to understand the interface of some of the functions provided
by the task library. With this exception, pointers and references still
won’t be used in problem statements.)
• Regarding the running time of implementations, Empirical perfor-

mance measurements were shifted from Out of focus to Included and
Tuning parameters to reduce running time was shifted from Excluded
to Out of focus.
(This is just a better reflecion of the current reality.)
• The basic O(V E) time algorithm for computing maximum bipartite

matching is now Included.
(The algorithm is comparatively simpler than many other algorithms
that are Included. Additionally, ISC surveys consistently show that
even without being on the Syllabus it is actually known by more con-
testants than many of the other Included algorithms.)
• Center of mass of a polygon was shifted from Included to (implicitly)

Out of focus.
• Algorithms for convex hull are still Included, but now it is clarified
that this includes an O(n log n) time algorithm.

Ioi Syllabus 2015 Diff

Uploaded by

Copyright:

Available Formats

Ioi Syllabus 2015 Diff

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ioi Syllabus 2015 Diff

Uploaded by

Copyright:

Available Formats

The International Olympiad in Informatics Syllabus

changelog for the 2015 version and rationale

1 Change in the definition of Excluded topics

Some of the harder algorithmic topics are explicitly marked as

In the new Syllabus, the definition is changed to:

Some of the harder algorithmic topics are explicitly marked as

Consider the editorial of the Codeforces problem 446E published here:

the previous Syllabus: it can be solved in 80 lines using modular addi-

2 “Excluded, but open to discussion”

3 A better definition of prerequisites

• “Included, unlimited” – e.g., all contestants are expected to know what

• “Included, to be clarified” – e.g., all contestants are expected to know

4 Changes in the set of topics

4.1 New Explicitly excluded topics

• Geometry in three or more dimensions.

Additionally, planar graphs were previously Out of focus. Planar graphs

4.2 Floating-point numbers

• elementary use of real numbers in numerically stable tasks

but keeps as Explicitly excluded:

• analyzing and increasing precision of floating-point computations

• non-trivial calculations on floating point numbers, manipulating pre-

4.3 Data structures

• Composition of data structures, e.g. two-dimensional statically bal-

• Augmented binary search trees – storing, modifying and using addi-

• Balanced binary search trees.

• O(log n) time algorithms for answering lowest common ancestor queries

• Creating persistent data structures by path copying or using fat nodes.

4.4 Other additions and reclassifications

• Among the applications of depth-first search, algorithms to determine

• Pointers and references were shifted from Out of focus to Included.

• Regarding the running time of implementations, Empirical perfor-

• The basic O(V E) time algorithm for computing maximum bipartite

• Center of mass of a polygon was shifted from Included to (implicitly)

You might also like