The 1996 International Olympiad in Informatics

Veszprém, Hungary
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




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


1 1
3 1 4



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


2 4 3 0
4 5 0
1 0



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

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 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


5                      A             11 
1                      B 
A                      A 
2                      B 
AB                     A 
3                      C 
BBC                    A 
2                      B 
CA                     A 
2                      A 
BA                     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.


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.

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:

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;