Academic journal article Australian Mathematics Teacher

The 2005 Australian Informatics Competition

Academic journal article Australian Mathematics Teacher

The 2005 Australian Informatics Competition

Article excerpt

The Australian Informatics Competition is a non-programming competition aimed at identifying students with potential in programming and algorithmic design. It is the first step in identifying students to represent Australia at the International Olympiad in Informatics.

Introduction

Try these problems!

Dungeon

A token (marked X in the diagram) is in a maze. You may move the token around according to the following rule: in each move the token can be moved any distance either horizontally or vertically, but can not pass over or stop on a shaded square.

[ILLUSTRATION OMITTED]

For example, from its starting position the token could travel either one square right, one square down, two squares down or three squares down. What is the minimum number of moves required to ensure that the token can reach any white square from its starting position?

Game

You are playing a rather unusual game on a 4 x 4 grid in which each square contains a number. You begin at the top left square of this grid and you must travel to the bottom right square. You must move one square right or one square down in each move.

To begin with you have a score of 0. Each time you move to a new square, you halve your current score (rounded down if necessary), and add the value of this new square. Your aim is to reach the bottom right square with the lowest score possible. For example, consider the following grid:

[ILLUSTRATION OMITTED]

The smallest possible final score is 12 which can be achieved as follows:

Move    Square   Score

begin              0
down      1        1
right     4        4
down      2        4
right     5        7
right     4        7
down      9       12

What is the smallest possible score for the following grids?

[ILLUSTRATION OMITTED]

These problems were taken from the 2005 Australian Informatics Competition (AIC). The AIC is the first step in identifying students who will represent Australia at the International Olympiad in Informatics (IOI). The IOI is one of a number of olympiads held annually in differing countries. (Other olympiads are held in Mathematics, Biology, Physics and Chemistry.) The IOI is the newest of the olympiads, the first being held in 1989. Australia has participated every year since 1999. About 80 countries participate in the IOI, with four students representing each country.

The road to the International Olympiad in Informatics

The IOI is a programming competition, with a heavy emphasis on algorithmic design. Informatics is not taught at most schools, and the level of algorithmic design required by the IOI is not taught at all. Students with potential are typically self-taught programmers, with no knowledge of algorithm design, and often are not outstanding academically. They must be taught this discipline.

Until 2005, potential students were identified by an Australia wide programming competition, now called the Australian Informatics Olympiad (AIO). Based on their performance in this competition, 20 students were invited to attend a training school. At the end of the training school, selection exams were held and the team chosen to attend the next IOI. In the selection exams, as in the AIO and the IOI, students write computer programs that are automatically marked by running the programs against a set of predetermined data.

The pattern of activities until 2005 was

[ILLUSTRATION OMITTED]

This timeline was less than ideal. Combining team selection with the training school meant that there was no time for students to absorb the material before the selection exam. Another source of concern was the small catchment of about 150 students.

In 2005, a number of changes were made. In particular, a pre-programming competition was introduced to identify students with no programming experience, but with talent in algorithmic design. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.