Australian Informatics Olympiad

Thursday 4 September, 2014

Senior Paper

Duration: 3 hours
3 questions
All questions should be attempted

Australian Informatics Olympiad 2014 (Senior) Important Notes

Important Notes
Some final reminders for competitors:
Solutions may be submitted in C, C++, C#, Pascal, Java, PHP or Python.
Solution templates can be downloaded from the submission website. These templates perform
all the necessary file input and output for each question. We strongly recommend using these
as a starting point for your solutions.
You should submit your solutions directly via the internet during the three hours of the
contest. Please read the Contest Rules in the Information Booklet if you have not yet done
so.
Some languages have special constraints:
Pascal programmers may not import any units except for Math, Strings and/or SysUtils.
Java programmers may not use any classes aside from those in packages java.lang,
java.io and java.util. Solutions must be contained in a single class called Solution,
and must be run from the routine
public static void main(String[] args)
within this Solution class.
PHP programmers may not use any functions provided by extensions or external libraries.
Python programmers may not import any packages except for sys.
If you are not sure about how your program should be structured, see the submission site
http://orac.amt.edu.au/aio/ for sample solutions to past problems in each of the supported languages (you are welcome to browse these during the contest).
It is particularly recommended that Java and PHP programmers visit this site, due to the
unusual constraints described above.
Dont leave all your submissions until the last few minutes! Submitting your solutions may take a little time, and once your three hours are over the submission site will not
accept any more solutions.
The best strategy is to submit solutions as you write them. If you improve a solution later
in the contest, you can always resubmit it.
If you have any queries, please ask your teacher to email aioquery@amt.edu.au and we will
respond as soon as possible. For urgent issues (such as losing your internet connection),
please ask your teacher to contact either Mr Jarrah Lacko on 02 8091 2321 or Mr Robert
Newey on 0432 748 904.
Please see the full contest rules for further information.
Good luck!

Australian Informatics Olympiad 2014 (Senior) Why Did I Score Zero?

Why Did I Score Zero?

Candidates sometimes score zero even though they believe that they have a working solution to a
problem. Below are some of the common reasons that good solutions score zero.
Note that examples of solutions that score 100% in the various AIO languages can be found on
the website http://orac.amt.edu.au/aio/.

Incorrect Input and Output Files

Each problem statement lists the names of its input and output files, similar to the example below.

Input File: zeroin.txt

Output File: zeroout.txt
In this example, if you try to open any of
"a:\zeroin.txt"
"c:\mydir\zeroin.txt"
"input.txt"
then the file you are looking for will almost certainly not be on the judging machine and your
program will score zero. Just open "zeroin.txt" without any additional directory information.
The same goes for the output file.

Keyboard and Mouse Input

Your program should not be interactive. It should not have a graphical user interface. It should
simply read from the input file, write to the output file, and exit. If your program requires any
input from the user, the judging software will not supply this input and you will exceed the time
limit. Examples include:
Please enter the following value...
Press any key to exit...
Providing a form on which the user has to click a button to start the program.

Incorrect Output Format

Each problem is very precise about how the output file should be formatted. Your score is assigned
by a judging program which tries to automatically extract your solution from your output file.
Every problem statement includes sample input and output files, as a way of illustrating these
formats. For Problem 1 on the Senior paper, the first sample output file contains the single line:
4
In this example, the following output files would almost certainly score zero:
The answer is 4.
"4"

Violating Contest Rules

Each year a few programs are submitted that violate the contest rules. Be sure to read the Program
Restrictions section of the rules, which details specific restrictions for each programming language.
If you are unsure about anything then please email aioquery@amt.edu.au for clarification.

Australian Informatics Olympiad 2014 (Senior) Giant Hippos

Problem 1
Giant Hippos
Input File: hippoin.txt
Output File: hippoout.txt
Time Limit: 1 second
Your backyard has been overrun by preposterously large hippos, and they are eating the tulips!

You have a line of N tulips, labelled from 1 to N . There are H hippos standing next to different
tulips . . . and they are already eating them! If you dont act fast, they will eat all the tulips in
your garden.
You have enough plywood to build up to F fences. Each fence will be built between two tulips
that are next to each other. Hippos cannot go through fences (or over them, or under them, or
around them).
Once you have built your fences, the hippos will roam back and forth along the line of tulips,
eating all the tulips they can reach without crossing your fences. What is the greatest number of
tulips you can save?

Input
Your program should read from the file hippoin.txt.
The first line of input will contain three space-separated integers N , H and F : the number
of tulips, hippos, and fences you can build respectively.
The next H lines will each contain an integer describing which tulip one hippo is eating.
These will be in increasing order. No two hippos start at the same tulip.

Output
Your program should write to the file hippoout.txt. Your output file should contain one line with
one integer: the greatest number of tulips you can save.

Australian Informatics Olympiad 2014 (Senior) Giant Hippos

Sample Input 1

Sample Output 1

9 3 3
2
5
7

Sample Input 2

Sample Output 2

7 2 1
1
7

Explanation

In the first sample case, as illustrated above, if we put a fence between tulips 2 and 3, between
tulips 4 and 5 and between tulips 7 and 8, no hippo will be able to reach tulips 3, 4, 8 or 9. There
is no placement of fences that will save more tulips, so 4 is the correct answer.
In the second sample case, no matter where you place the one fence you will not be able to save
any tulips.

Constraints
To evaluate your solution, the judges will run your program against several different input files.
All of these files will adhere to the following bounds:
1 N 1 000 000
1 H 1 000 and H N
1F <N
As some of the test cases will be quite large, you may need to think about how well your solution
scales for larger input values. However, not all the cases will be large. In particular:
For 50% of the available marks, H = F = 3.

Australian Informatics Olympiad 2014 (Senior) Chimera

Problem 2
Chimera
Input File: chimin.txt
Output File: chimout.txt
Time Limit: 1 second
Next week is your schools Mad Science Fair, and everyone is hard at work on their mad science
projects. For example, Gru is building a rocket big enough to steal the moon, whilst Elsa is
tinkering with her freeze ray. For your project, you are breeding a chimera.
A chimera is a monster that is part lion, part snake, and part goat. Your plan is to take the
DNA sequences of each of the three creatures and combine them into a new DNA sequence for the
chimera. A DNA sequence is a string of N letters, each one of A, T, C or G.

G A T T A T A
C A G G A T A
T A T T A C A

C A T T A T A

The list above shows an example of three DNA sequences of length 7 representing lion, snake
and goat DNA. The bottom DNA sequence is one possible sequence of chimeras DNA. Letters in
bold in the top three lines are the same as the letter in the chimeras DNA at the same position.
The lionishness of your chimera is defined as the number of positions in which the lion DNA
and the chimera DNA have the same letter. In the example above, the lionishness of your chimera
is 6, as they match in all but the first position. The snakiness and goatism of your chimera are
defined similarly. In the example above, the snakiness and goatism of your chimera are both 5.
The task before you is to construct the chimeras DNA sequence. You will be given the DNA
sequences for lions, snakes and goats. The mark for your project will be whichever is lowest: the
lionishness, snakiness or goatism of your chimera. You must determine the highest mark you can
possibly achieve.

Australian Informatics Olympiad 2014 (Senior) Chimera

Input
Your program should read from the file chimin.txt.
The first line of input will contain one integer N : the length of each DNA sequence.
The next three lines will represent lion, snake and goat DNA respectively. Each of these will
contain a sequence of N letters, each one of A, T, C, or G.

Output
Your program should write to the file chimout.txt. Your output file should contain one line with
one integer: the highest possible mark you can achieve. (Remember, your mark will be whichever
is lowest: the lionishness, snakiness or goatism of your chimera.)

Sample Input 1

Sample Output 1

7
GATTATA
CAGGATA
TATTACA

Explanation
The sample data reflects the case described on the previous page. There is no chimera DNA
sequence that will receive a mark higher than 5.

Constraints
To evaluate your solution, the judges will run your program against several different input files.
All of these files will adhere to the following bounds:
1 N 100 000
Furthermore,
For 30% of available marks, the lion and snake DNA sequences will be exactly the same.
For 50% of available marks, all DNA sequences will only use the letters A and T.

Australian Informatics Olympiad 2014 (Senior) Wormhole

Problem 3
Wormhole
Input File: wormin.txt
Output File: wormout.txt
Time Limit: 1 second
You are the lead programmer of Wormhole, a widely anticipated computer game. The premise
of Wormhole is rather thrilling: test subject Chaz is trapped in a rectangular grid of orange and
blue chambers each containing one cupcake. Chaz chooses a chamber to start in, and then needs
to collect all the cupcakes by visiting every chamber at least once. If this is possible the level is
considered solvable.
The chambers are walled off from each other by thick glass, such that Chaz can only see
chambers which are directly north, south, east or west of his current position. Conveniently Chaz
has a wormhole gun, which he can use to shoot through the glass into any chamber he can see and
so be instantly teleported there. However, a wormhole can only be created between two chambers
of different colours. This means that if Chaz is standing in a blue chamber, he can only move to
an orange chamber, and vice versa.
That is, Chaz can teleport to another chamber if:
It is of a different colour to his current chamber.
It is directly north, south, east or west (i.e. in the same row or column) of his current
chamber.

c
c
Arrows indicate possible teleports Chaz can make. From those chambers he may continue to
teleport to other chambers.
You have been stuck in a meeting for hours now where the designers are interested in how
modifications to the chamber colours affect a level. Each modification involves changing the colour
of one chamber. After each change they make, the designers want to know how many more
modifications are needed to make the level solvable that is, the smallest number of chambers
that need to have their colour changed so that Chaz can reach every chamber from a starting
chamber of his choosing.
As working everything out by hand gets more and more tedious, you escape from the meeting
and whip out your trusty laptop to write a computer program that will answer the designers
questions after each modification.

Australian Informatics Olympiad 2014 (Senior) Wormhole

Input
Your program should read from the file wormin.txt.
The first line of input contains three space-separated integers, R, C, and Q. There will be
R rows and C columns in the grid, and Q modifications made by the designers.
The next R lines each contain C characters, representing the initial design of the game. An
O represents an orange chamber, while a B represents a blue chamber.
The following Q lines each contain two integers ri and ci . This represents a modification to
the grid that changes the colour of the chamber in row ri and column ci . Rows are labelled
from 1 to R (from top to bottom) and columns are labelled from 1 to C (from left to right).

Output
Your program should write to the file wormout.txt. The output should contain Q + 1 lines. The
first line should contain the smallest number of modifications required to make the level solvable.
The next Q lines should correspond to the Q modifications in input. After each modification has
been made (including all previous modifications), your program should write one line containing
the smallest number of modifications required to make the level solvable (or 0 if it is already
solvable).

Sample Input 1

Sample Output 1

5 5 2
BBBOB
BOBOB
OBBOB
BBBOB
OOOOB
2 2
2 4

0
0
1

Explanation

The left image is the inital grid (with blue chambers represented by gray and orange chambers
represented by white). It is already solvable there exists a sequence of valid moves starting from
some chamber that will visit every chamber at least once. After the first modification, the grid
(the middle image) is still solvable. After the second modification, as shown on the right, the grid
is no longer solvable but by reversing the modification it can be made solvable again.

Australian Informatics Olympiad 2014 (Senior) Wormhole

Sample Input 2

Sample Output 2

5 6 3
OOBBBO
OOOOOO
OOBBBO
OOOOBO
BOBOBO
3 4
4 5
1 6

1
1
2
1

Constraints
To evaluate your solution, the judges will run your program against several different input files.
All of these files will adhere to the following bounds:
1 R, C 300
1 Q 10 000
For 50% of test cases, 1 R, C 50 and 1 Q 5000.
Furthermore, your program will be given 50% of available marks for a test case if it correctly
distinguishes between solvable and unsolvable grids (that is, you will be marked on whether
each line of output is 0 or non-zero).