Judges' Comments on the Problems and their Solutions

Problem A: All Discs Considered

The key observation is that one starts either with the first DVD or with the second DVD. For both cases, the installation process is simulated. Each simulation proceeds by maintaining two queues to store those packages from both discs that may be installed because all dependent packages have already been dealt with.

Judges' test data consists of several large test cases with many packages and/or dependences having different patterns, along with exhaustive small test cases. The total number of test cases is 226.

Rating: Easy

Problem B: Boolean Logic

Parse the input according to the specified grammar. Identify the proposition symbols and their positions. Generate all assignments by backtracking or a brute-force approach. For each assignment, evaluate all subformulas and output the result, correctly formatted. Although this solution is relatively straight-forward, the constructed program is quite complex and long.

Judges' test data consists of 33 hand-crafted test cases, the most costly of which contains 13 different propositional symbols.

Rating: Hard

Reference

Chapter 1.2, p. 19, in:
van Dalen, D.
Logic and Structure
Springer-Verlag, 2nd edition, 3rd printing, 1989
ISBN 0-387-12831-X

Problem C: Code

Imagine the finite state machine that controls the safe lock. You can view it as a directed graph with 10^n-1 nodes, one for each state. Every node has 10 outbound edges, one for each possible key press.

Every sequence of k key presses, where k>=n-1, entered to the lock corresponds to a path of length k-(n-1) in the directed graph. The first n-1 key presses determine the start node, and every following key press adds an edge to the path.

A sequence of key presses that contains each n-digit sequence corresponds to a path that traverses every edge of the directed graph at least once. The problem statement asserts the existence of a sequence of length 10ⁿ+n-1 that corresponds to a path of length 10ⁿ. This means that there is a path that traverses every edge of the directed graph exactly once.

Since every node of the directed graph has the same in-degree as its out-degree (viz. 10) such a path is actually a circle, a so called Euler tour. Indeed, the existence of an Euler tour is granted by virtue of this special structure of the directed graph, too.

Therefore, all that has to be done is to find an Euler tour. This can be accomplished by a depth-first traversal in the directed graph.

Judges' test data consists of testing the code-lengths 1,...,5 twice and the maximum code length 6 once. Since there may be more than one Euler tour, a verification program supports the judging process.

Rating: Medium

Reference

Safebreaker
SWERC 1997, Problem S, posed by Falk Bartels

Problem D: In Danger

The value of n can be as large as 99000000. Thus simulating the "game" for every test case is too slow. There are several possibilities to overcome this problem:

Observe that there are at most 10*10*7 different test cases, since this is the number of different combinations that are allowed for x,y,z. So you could simulate all these test cases on your own computer, where your time limit is 5 hours. However, you still have to invest quite a bit in coding, if your computer has limited memory (i.e., less than 512 MB).

During a simulation, if you remove a person, you have reduced the problem from size n to size n-1. This suggests a dynamic programming solution. Let J(n) be the solution for the problem of size n. The first person who leaves, has number 2. The remaining persons are: 3, 4, 5, ..., n-1, n, 1. The solution of the similar problem, where the persons have numbers 1, 2, ..., n-1 is J(n-1). The transformation is J(n)=((J(n-1)+1) mod n) + 1. If you do not store the values, this removes at least the memory problems, however the runtime restriction still applies.

Now, precalculate the function J once at the beginning of your program. The runtime is no longer a problem, and if you only store the value of J at the possible input values of n, memory is no longer, too.

The reduction from size n to size n-1 can be generalised to a reduction to size n/2. Observe that the first n/2 persons leaving are always those with numbers 2, 4, 6, ..., n/2. Then, similar transformations can be found. You have to consider separately the two cases of n being an even or an odd number to complete the reduction: J(2*n)=J(n)*2-1 and J(2*n+1)=J(n)*2+1. With these formulas you have reduced the runtime to O(log n).

You can further try to calculate several values of J manually (or write any inefficient program), to get an intuition of the function. The first values are: 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1. You may notice that J(n) is always odd and starts anew from 1 with every power of 2. It increases through all successive odd numbers until it is about to reach the next power of 2 when it again drops to 1. Let k be the largest integer with 2^k<=n. Now, it is not difficult to set up a closed formula for this sequence of numbers: J(2^k+t)=2*t+1. The correctness of this formula is easily proved by induction with the help of the recursive formulas. Actually, there are means to solve the recursion equations explicitly. By the way, looking at the closed formula, note that in binary notation, J(n) is n rotated 1 bit to the left.

Judges' test data consists of all 693 different test cases.

Rating: Medium

Reference

Chapter 1.3, p. 8, in:
Graham, R.L. ; Knuth, D.E. ; Patashnik, O.
Concrete Mathematics
Addison-Wesley, 2nd edition, 1994
ISBN 0-201-55802-5

Problem E: Run Length Encoding

The input file is processed line by line. Every line is processed by a loop that checks if a sequence of consecutive repetitions starts at the current position. If this is the case, the length of the repetition is calculated up to a maximal length of 9 characters, and its encoding is output. Otherwise, the next sequence of consecutive repetitions, if any, is located and the intermediate characters are encoded and output. This procedure is continued until the end of the line is reached.

Judges' test data consists of several hand-crafted and several randomly generated lines. Altogether, the input file contains 225 lines with at most 100 characters each.

Rating: Easy

Reference

Run Length Encoding
Problem C from an unknown preliminary contest, posed by an unknown author

Problem F: Fractran

It is not difficult to code the simulation using arbitrary-precision integers, but the numbers can get pretty large and the operations then take too much time. Every integer number, however, has a unique representation through its prime factorisation. The necessary operations to perform the simulation are then easily implemented. For example, multiplication and division boil down to addition and subtraction of corresponding exponents. The Sieve of Eratosthenes can be used to calculate the prime numbers.

All the prime numbers that will have to be handled in a simulation must be prime factors of numbers given in the input. Since theses numbers are bounded by 1000 just prime factors less than 1000 will occur, and there are 168 of them. It follows also that a number occurring in one of the fractions can have at most 4 different prime factors, whereas the current state of the computation may have many more. It is, therefore, efficient to store the current state of the computation as an array of integers denoting the exponents corresponding to all prime factors less than 1000, and numerators and denominators as lists containing only the occurring prime factors. Testing if the current state is a power of 2 is efficiently performed by additionally caching the total number of primes in its factorisation.

Judges' test data consists of 12 hand-crafted test cases.

Rating: Medium

Reference

Conway, J.H.
Fractran: A simple universal programming language for arithmetic
Chapter 2, in:
Cover, T.M. ; Gopinath, B.
Open problems in communication and computation
Springer-Verlag, 1987
ISBN 0-387-96621-8

Problem G: Huffman's Greed

Due to the lexicographic ordering, any sub-tree must contain a continuous sequence of labels K_i,K_i+1,...,K_i+d. The cost of arranging these keys in a tree depends only on the probabilities q_i,p_i+1,q_i+1,...,p_i+d,q_i+d. This calls for a dynamic programming approach where each of the labels K_i,...,K_i+d is tried as the root of the tree. If, e.g., K_k is the root, the labels K_i,...,K_k-1 must be placed into the left sub-tree, and the labels K_k+1,...,K_i+d must go into the right sub-tree. The arising sub-problems are, by dynamic programming, already solved. The cost of arranging the labels in a tree is calculated from the costs of the sub-trees plus a certain constant amount (since the levels of the nodes in the sub-trees increase by 1, and the root is added).

This approach leads to a runtime of O(n³), fast enough for n<=200. See the reference for an improvement to O(n²).

Judges' test data consists of 27 hand-crafted test cases and 100 randomly generated test cases.

Rating: Medium

Reference

Chapter 6.2.2, pp. 436-442 in:
Knuth, D.E.
The Art of Computer Programming, Volume 3: Sorting and Searching
Addison-Wesley, 2nd edition, 1998
ISBN 0-201-89685-0

Problem H: Binary Search Heap Construction

Since the labels and the priorities are unique, there is exactly one treap for every test case. It is constructed in a straight-forward way as follows. Find the node with the greatest priority, which will become the root of the treap. Split the remaining nodes into two sets: those with labels less than that of the root and those with labels greater than that of the root. From the first/second set of nodes construct the left/right sub-treap by applying this strategy recursively. If the set of nodes is empty, we have reached a leaf, and the recursion terminates.

In a straight-forward implementation using lists we need linear time to find the maximum priority node and linear time to split the set of nodes, too. Therefore, in the worst case, we get a runtime of O(n²), too slow for values of n up to 50000. Compare this, e.g., to the worst case of the quicksort algorithm.

We may, however, reduce the amount of time needed to split the set of nodes by sorting them (using an O(n*log(n)) complexity algorithm) according to their labels in the beginning. Then, the kind of subset of nodes needed for our procedure is represented by an interval indicating the smallest and the greatest element. In each recursive step, an interval is split into two sub-intervals. Still, we need linear time to find the maximum priority in such an interval, leaving us with a quadratic worst-case-time.

We can find the maximum priority in logarithmic time by augmenting the list of elements with an order-statistic tree. To this end, we build a complete binary tree large enough to hold n numbers (the priorities) at its bottom level. Every internal node is marked with the maximum of the priorities below that node. Such a tree can be constructed in linear time in a bottom-up fashion. With this additional information, we no longer need to scan through a complete interval in search of the maximum priority but can use the combined maximum numbers stored in the internal nodes. Thus, we are able to find the maximum priority in logarithmic time by a bottom-up search in the order-statistic tree from both ends of the interval. We then add a top-down search to find the element of the interval having that priority. Hence, the total runtime of our algorithm is O(n*log(n)).

Judges' test data consists of 14 hand-crafted test cases, 50 randomly generated test cases, and 3 large test cases (one of which is randomly generated).

Rating: Hard

Reference

Treaps
Problem F from an unknown preliminary contest, posed by an unknown author