The 1996 International Olympiad in Informatics
- Return to IOI '96 Home
By Don Piele
Accompanying Pictures from IOI '96
Our adventure began when head coach Rob Kolstad and I met up with
the rest of our delegation at London's Heathrow Airport.
We had arrived in separate planes from different locations in
the United States. Deputy team leader, Greg Galperin, arrived
from Boston with Joseph Turian, 16, Great Neck H.S.,Great Neck,
NY, and Keldon Jones, 18, Oklahoma School of Science and Math,
Oklahoma City, OK. Dan Adkins, 16, McKinley High School, Baton
Rouge, LA and Matt Craighead, 14, St Paul Academy, St. Paul, MN,
flew in from Philadelphia. We all flew together to Budapest and
boarded a bus for a two hour trip to Veszprém, the site
of the 1996 International Olympiad In Informatics, July 25 - Aug 1.
For these four deserving American high school students, the IOI
was the culmination of a year long selection process called the
USA Computing Olympiad. It began in January with the qualifying
round, continued in March with the competition round, and ended
in June at the week long final round at the University of Wisconsin-Parkside.
Through a similar selection process, 57 countries sent a team
of four to represent their country at the eighth annual IOI in
Hungary.
We arrived in Veszprém, put our bags in our dorm rooms,
and took a short walk to the modern Vetesi Albert Secondary School,
where the contest would be held. This year's IOI was another event
in the year long celebration of Hungary's 1,000 birthday celebration.
Hosting the competition was the John von Neumann Computer Society,
which runs the Hungarian National computing competitions.
Our guide, Livia Czakker, greeted us and showed us the way to
the opening ceremonies held at the center of town in the old Castle
area. We were welcomed by performances from the Garrison Orchestra,
the Veszprem folk dancers, the mayor and other dignitaries before
walking to the official flag raising ceremonies near the Town
Hall.
That evening, the general assembly, made up of leaders from each
country, met to discuss the first set of problems and translate
the tasks into their native language. This job took over five
hours for some countries. We wrote our own translation of the
official ìEnglishî version to iron out a few unusual
expressions. The contestants get the official English version
along with a translation in their language and any other language
they may request. The dutch requested our USA version.
This year, for the first time, team leaders and participants had
separate living quarters. Thus we could pick up our problems and
translate them in the evening and then go to bed instead
of getting up early in the morning and doing the task. This enabled
the participants to begin the competition at 8 am instead of later
in the afternoon, when it was hotter.
The Competition Days
The first day's schedule began with a five-hour session from 8
am to 1 pm. Each student, working on a Compaq Pentium PC, attempted
to solve three problems. The programming problems are algorithmic
and focus on the design of correct and efficient programs. All
tasks can be solved in standard Pascal, C/C++ or Quick BASIC.
On the first day, two of the problems were the standard batch
programs that accepted input data in a specified format and produced
the answers in output files. The third was a game program, requiring
the program to react to the moves of another program that would
be testing the algorithm.
After five hours, the programming stopped and the grading began.
At the appointed time, the team leader, a participant and a grading
coordinator sat down to begin the automated grading process. One computer
was used to grade the program running
in the contestants computer. With the exception of a minor glitch,
the grading proceeded very quickly. Afterward, we gathered together
with the team to discuss the results.Some were satisfied with
their performance; others were not. There is no official announcement
of the results from the first day so the usual trading of results
went on between team leaders. If you needed to know how any another
team was doing, you could ask Vladimir Kotov from Belarus -- he
shamelessly collected results from everyone.
The second competition day was a carbon copy of the first day
except that the problems were a bit easier. So those who had dreams
of making up ground on the second day
would find it very difficult. After it was over, the participants
released their tension at a disco party.
Sight Seeing Near Veszprém
Lake Balaton, the largest fresh-water lake in Central Europe is
located 15 km south of Veszprém. During the summer, the
southern shore is a popular vacation spot and our destination
for the day of rest between competitions. The water was green
and warm enough to eventually attract everyone with a bathing
suit. Keldon and I rented a double kayak and spent an hour touring
the picturesque shoreline. The warm sun and water
helped us all relax and get to know other teams.
Pannonhalma is the seat of the first abbey of the Benedictine
order in Hungary. The monastery, which stands on a hill overlooking
a village, was our first stop on a
busy day of excursions. We were treated to an organ recital in
its chapel and a chance to visit the library that once possessed
more than 70 codices from the 11th century. Nowadays it houses
300,000 volumes, which makes it the fifth largest collection of
books in the country. We ended the day back at Lake Balaton with
a scenic boat ride amid the sail boats on a warm summer cruise.
On the day before the final ceremony, the team leaders were treated
to a wonderful Hungarian evening, complete with folk singers,
musicians and a sumptuous meal at a country restaurant. This was
a time for true relaxation which lasted long into the evening.
The hard work was over and it was time to relax and reflect on
the unique opportunity at hand. Many team leaders return every
year and have become good friends; this was time reserved for
them to renew old friendships.
The Award Ceremony
The awards ceremony was held on the last evening at the central
town theater. Our team members had carried their coats and ties
all the way to Hungary for this moment. After
a ragtime band warmed up the audience, the ceremony began by bringing
to the stage the bronze medal winners. Only half of the 220 participants
are allowed to get medals of any kind. The bronze, silver and
gold are awarded to this half in a 3-2-1 ratio. A total of 51
participants were called to the stage in groups of 12 to receive
their bronze medal, a gift, and applause. Two of our team members,
Keldon Jones, and Matt Craighead were among this group. The next
group of 38 participants came forward to receive the silver medal
including Dan Adkins, our lone veteran. Last year in Holland,
Dan received the bronze medal. Finally, 20 students lined up to
receive the coveted gold metal. Unfortunately, none of our contestants
made it into this elite group this year. China, however, finished
with four gold medals, and the Russian team had three gold and
one silver. The top student, Daniel Kral from the Czech Republic,
scored 196 out of 200 and received a special
trophy and a Pentium PC from Compaq.
Peter Hanak, President of the IOI'96, delivered his "Words
of Farewell." I have known Peter since we first met at IOI'92
in Bonn, Germany, the first year the US competed at IOI. He proved
to be an effective organizer with a calm and confident manner.
He assembled a highly competent team that presented for our enjoyment
another excellent olympiad. Thank you Peter.
Finally, the flag was passed to South Africa, which will host
the IOI'97 in Cape Town.
----------------------------------------------------------------
Problems used at IOI'96
Day 1
1. A Game
Consider the following two-player
game. The game board consists of a sequence of positive integers.
The two players move alternately. When a player moves, he selects
a number from either the left or the right end of the sequence.
The selected number is deleted from the board. The game is over
when all numbers have been selected. The first player wins if
the sum of the numbers he has selected is at least as much as
selected by the second player. The second player plays his best.
The first player starts the game.
If the board initially contains an
even number of elements, then the first player has a winning strategy.
You are to write a program that implements the strategy of the
first player to win the game. The second player's response is
provided by a given computer program. The two players communicate
with three procedures of the module Play that is made available
to you. These procedures are StartGame, MyMove and YourMove. The
first player should initiate the game by executing the parameterless
procedure StartGame. If the first player selects a number from
the left end, he executes the procedure MyMove('L'). Similarly,
executing the instruction MyMove('R') sends a message to the second
player indicating that the first player has selected a number
from the right end. The second player, i.e. the machine moves
immediately, and the first player can learn this move by executing
the instruction YourMove(C), where C is a character type variable(in
C/C++ you write this as YourMove(&C)). The value of C is 'L'
or 'R' depending on whether the selection has been made either
from the left or the right end.
Input Data
The first line of file INPUT.TXT contains
the size N of the initial board. N is even and 2<=N<=100.
The remaining N lines contain one number in each line, the contents
of the initial board in left to right order. Each number is at
most 200.
Output Data
When the game is over, your program
should write the final result of the game to the file OUTPUT.TXT.
The file contains two numbers in the first line. The first number
is the sum of the numbers selected by the first player and the
second number is the sum of the numbers selected by the second
player. Your program must play a game and the output must correspond
to the game played.
Example Input and Output
INPUT.TXT
6
4
7
2
9
5
2
OUTPUT.TXT
15 14
2. Job Processing
A factory is running a production
line. Two operations have to be performed on each job: first operation
"A", then operation "B". There is a certain
number of machines capable of performing each operation. A type
"A" machine takes a job from the input container, performs
operation "A" and puts the job into the intermediate
container. A type "B" machine takes a job from the intermediate
container, performs operation "B" and puts the job into
the output container. All machines can work in parallel and independently
of each other, and the size of each container is unlimited. The
machines have different performance characteristics, a given machine
works with a given processing time.
Give the earliest time operation "A"
can be completed for all N jobs provided that the jobs are available
at time 0. (Subtask A). Also compute the minimal amount of time
that is necessary to perform both operations on N jobs (Subtask
B).
Input Data
The file INPUT.TXT contains positive
integers in five lines. The first line contains N, the number
of jobs (1<=N<=1000). On the second line, the number M1
of type "A" machines (1<=M1<=30) is given. In
the third line there are M1 integers, the job processingtimes
of each type "A" machine. The fourth and the fifth line
contain the number M2 of type "B" machines (1<=M2<=30)
and the job processing times of each type "B" machine,
respectively. The job processing time is measured in units of
time, which includes the time needed for taking a job from a container
before procersing and putting it into a container after processing.
Each processing time is at least 1 and at most 20.
Output Data
Your program should write two lines
to file OUTPUT.TXT. The first line should contain one positive
integer: the solution of subtask A. The second line should contain
the solution of subtask B.
Example Input and Output
INPUT.TXT
5
2
1 1
3
3 1 4
OUTPUT.TXT
3
5
3. Network of Schools
A number of schools are connected
to a computer network. Agreements have been developed among those
schools: each school maintains a list of schools to which it distributes
software (the "receiving schools"). Note that if B is
in the distribution list of school A, then A does not necessarily
appear in the list of school B
You are to write a program that computes
the minimal number of schools that must receive a copy of the
new software in order for the software to reach all schools in
the network according to the agreement (Subtask A). As a further
task, we want to ensure that by sending the copy of new software
to an arbitrary school, this software will reach all schools in
the network. To achieve this goal we may have to extend the lists
of receivers by new members. Compute the minimal number of extensions
that have to be made so that whatever school we send the new software
to, it will reach all other schools (Subtask B). One extension
means introducing one new member into the list of receivers of
one school.
Input Data
The first line of file INPUT.TXT contains
an integer N: the number of schools in the network (2<=N<=100).
The schools are identified by the first N positive integers. Each
of the next N lines describes a list of receivers. The line i+1
contains the identifiers of the receivers of school i. Each list
ends with a 0. An empty list contains a 0 alone in the line.
Output Data
Your program should write two lines
to the file OUTPUT.TXT. The first line should contain one positive
integer: the solution of subtask A. The second line should contain
the solution of subtask B.
Example Input and Output
INPUT.TXT
5
2 4 3 0
4 5 0
0
0
1 0
OUTPUT.TXT
1
2
Day 2
4. Sorting a Three-Valued Sequence
Sorting is one of the most frequently
done computational tasks. Consider the special sorting problem,
where the records to be sorted have at most three different key
values. This happens for instance when we sort medalists of a
competition according to medal value, that is, gold medalists
come first, followed by silver , and bronze medalists come last.
In this task the possible key values
are the integers 1, 2 and 3. The required sorting order is non-decreasing.
Sorting has to be accomplished by a sequence of exchange operations.
An exchange operation, defined by two position numbers p and q,
exchanges the elements in positions p and q.
You are given a sequence of key values.
Write a program that computes the minimal number of exchange operations
that are
necessary to make the sequence sorted.
(Subtask A). Moreover,
construct a sequence of exchange operations
for the respective sorting (Subtask B).
Input Data
The first line of file INPUT.TXT contains
the number of records N (1<=N<=1000). Each of the following
N lines contains a key value.
Output Data
Write on the first line of file OUTPUT.TXT
the minimal number L of exchange operations needed to make the
sequence sorted (Subtask A). The following L lines give the respective
sequence of the exchange operations in the order performed. Each
line contains one exchange operation described by two numbers
p and q, the positions of the two elements to be exchanged (Subtask
B). Positions are denoted by the numbers from 1 to N.
Example Input and Output
INPUT.TXT OUTPUT.TXT
9 4 2 1 3 2 4 7 1 9 2 3 5 9 3 3 2 3 1
5. Longest Prefix
The structure of some biological objects
is represented by the sequence of their constituents. These constituents
are denoted by uppercase letters. Biologists are interested in
decomposing a long sequence into shorter ones. These short sequences
are called primitives. We say that a sequence S can be composed
from a given set of primitives P, if there are n primitives p1,...,pn
in P such that the concatenation p1...pn of the primitives equals
S. By the concatenation of primitives p1,...,pn we mean putting
them together in that order without blanks. The same primitive
can occur more than once in the concatenation and not necessarily
all primitives are present. For instance the sequence ABABACABAAB
can be composed from the set of primitives
{A, AB, BA, CA, BBC}.
The first K characters of S are the
prefix of S with length K. Write a program which accepts as input
a set of primitives P and a sequence of constituents T. The program
must compute the length of the longest prefix, that can be composed
from primitives in P.
Input Data
The input data appear in two files. The file INPUT.TXT describes the set of primitives P, while the file DATA.TXT contains the sequence T to be examined. The first line of INPUT.TXT contains N, the number of primitives in P (1<=N<=100). Each primitive is given in two consecutive lines. The first line contains the length L of the primitive (1<=L<=20). In the second line there is a string of uppercase letters (from 'A' to 'Z') of length L. The N primitives
are all different.
Each line of the file DATA.TXT contains
one uppercase letter in the first position. This file ends with
a line containing a single period ('.').
The length of the sequence is at least
1 and at most 500,000.
Output Data
Write into the first line of file
OUTPUT.TXT the length of the longest prefix of T that can be composed
from the set P.
Example Input and Output
INPUT.TXT DATA.TXT OUTPUT.TXT
5 A 11
1 B
A A
2 B
AB A
3 C
BBC A
2 B
CA A
2 A
BA B
C
B
6. Magic Squares
Following the success of the magic
cube, Mr. Rubik invented its planar version, called magic squares.
This is a sheet composed of 8 equal-sized squares (see Figure
3).
1 2 3 4
8 7 6 5
Figure 3 Initial configuration
In this task we consider the version
where each square has a different colour. Colours are denoted
by the first 8 positive integers. A sheet configuration is
given by the sequence of colours obtained by reading the colours
of the squares starting at the upper left corner and going in
clockwise direction. For instance, the configuration above is
given by the sequence (1,2,3,4,5,6,7,8). This configuration is
the initial configuration.
Three basic transformations, identified
by the letters 'A', 'B' and 'C', can be applied to a sheet:
'A': exchange the top and bottom row,
'B': single right circular shifting of the rectangle, 'C': single
clockwise rotation of the middle four squares.
All configurations are available using
the three basic transformations.
A: 1 2 3 4 8 7 6 5 1 2 3 4 8 7 6 5
B: 1 2 3 4 4 1 2 3 5 8 7 6 8 7 6 5
C: 1 2 3 4 1 7 2 4 8 6 3 5 8 7 6 5
Figure 4: Basic transformations
The effects of the basic transformations
are described in Figure 4. Numbers outside the squares denote
square positions. If a square in position p contains number i,
it means that after applying the transformation, the square whose
position was i before the transformation moves to position p.
You are to write a program that computes
a sequence of basic transformations that transforms the
initial configuration of Figure 3 to a specific target configuration
(Subtask A). Two extra points will be given for the solution if
the length of the transformation sequence does not exceed 300
(Subtask B).
Input Data
The file INPUT.TXT contains 8 positive
integers in the first line, the description of the target configuration.
Output Data
On the first line of file OUTPUT.TXT
your program must write the length L of the transformation sequence.
On the following L lines it must write the sequence of identifiers
of basic transformations, one letter in the first position of
each line.
Tool
MTOOL.EXE is a program in the task
directory that lets you play with the magic squares. By executing
"mtool input.txt output.txt" you can experiment with
the target configuration and the sequence of transformations.
Example Input and Output
INPUT.TXT OUTPUT.TXT
2 6 8 4 5 7 3 1 7 B C A B C C B
-------------------------------------------------------------
Our Sponsor
USENIX, the premier technical UNIX Users group, is our main sponsor.
They have been a contributor since the first USACO in 1992. We
are grateful to USENIX for its generous sponsorship.
Contributor
Microsoft is a much appreciated financial contributor.
USACO World Wide Web Home Page
All past and current information about the USACO appears on our
home page: http://usaco.uwp.edu/
1997 USACO
To be placed on the USACO mailing list and to receive the USACO
Newsletter, contact the author at the address given below.
Dr. Donald T. Piele
Director, USACO
University of Wisconsin-Parkside
Kenosha, WI 53141-2000;
Ph 414/595-2231;
e-mail piele@cs.uwp.edu
http://usaco.uwp.edu
