Judges' Comments on the Solutions

Problem A: Average is not Fast Enough!

This is the next to easiest problem in this contest. It's the best thing to convert all times to seconds, first. Then pay attention to calculate minutes per kilometers, not the other way round. Finally, the results must be rounded, not truncated to the next second. The calculation in seconds also helps avoiding overflows from seconds to minutes.

Judges' test data consisted of a relay with 7 sections and 511 teams. The data was taken from the SOLA 2001 Zurich.

Rating: Easy

SOLA Zurich 2001
Running times for the first 7 sections
http://www.sola.asvz.ethz.ch/

Problem B: Bound Found

The naive algorithm calculates the sum of every possible sequence and thus has complexity O(n³). It can be improved by first calculating the partial sums of the sequence which leads to O(n²). But this is not enough, since n can be as large as 100000.

By sorting the partial sums however, we can scan through them with two pointers. If the sum in a range is too small, we increment the upper pointer which makes the sum larger. Otherwise the lower pointer is incremented which makes the sum smaller. The best solution is updated and remembered during the process. The run-time behaviour is dominated by sorting the sequence which is O(n*log(n)).

Judges' test data was constructed from many queries with very short sequences, several queries with a sequence of length 1000 with random targets, and a few queries with a sequence of maximal legal length with random targets. The total number of queries is 829. Since there may be multiple correct answers for the test cases, a special verification program was written by slightly modifying the judges' solution.

Rating: Hard

Reference

Bentley, J.L.
Programming Pearls
Problem 7.7.4, Page 78, Addison-Wesley, 1986
ISBN 0-201-10331-1

Problem C: Code the Tree

The parser can be implemented in a recursive-descent manner. It constructs an adjacency set representation of the tree. For the generation of the Prufer code, any straight-forward algorithm can be applied, since runtime is no problem, when n<=50. An O(n*log(n)) algorithm, which keeps track of the current leaf nodes in a priority queue, is of course more efficient.

Judges' test data was created from an exhaustive test of the n<=3 cases and 100 random-generated tests. Total number of test cases is 120.

Rating: Medium

Is is not sufficient to represent the tree by storing the parent nodes, since the "artificial" root of a tree could become a leaf in the process of building the Prufer code.

Ural State University Personal Contest Online February 2001 Students Session
Problem A: The Prufer Code
http://acm.timus.ru/en/problem.asp?id=1069

University of Ulm Local Contest 2001
Problem D: Decode the Tree
Ulm, 2001

Problem D: Decode the Tree

Observe, that exactly all the nodes, that do not appear in the Prufer code, are the leafs of the tree to be reconstructed (except maybe the node with number n). According to the definition of the Prufer code, the first number in the code is adjacent to the leaf with the smallest number. Thus, one edge is constructed. If the first number in the code appears another time somewhere in the code, it is no leaf yet. But if it does not appear one more time, it has become a leaf now. In this case, insert it into the set of leafs. Now, repeat the same precedure n-2 times, to get the other edges. Again, straight-forward algorithms or efficient priority-queue based algorithms can be used. Obviously, the pretty-printer is best implemented in a recursive-descent manner.

Judges' test data was essentially the output of the judges' solution running on the judges' input for Problem C. Total number of test cases is 120.

Rating: Hard

Since the tree is constructed now, an adjacency list representation is sufficient. A special verification program had to be used, because the output is not uniquely defined. However, it it not difficult to construct the verification program: let c be the function that solves Problem C and d the function that solves Problem D. Then c_^od=id, thus verification is done by diff input_^oc.

Ural State University Personal Contest Online February 2001 Students Session
Problem A: The Prufer Code
http://acm.timus.ru/en/problem.asp?id=1069

University of Ulm Local Contest 2001
Problem C: Code the Tree
Ulm, 2001

Problem E: Etaoin Shrdlu

This is the third-easiest problem in this contest. Just read the input line by line, build a two-dimensional table with the frequencies, and output the top five entries.

Judges' test data consisted of 8 test cases, ranging from classical literature, music lyrics, literary essays over book reviews to the digits of Pi.

Rating: Easy

Joyce, J.
Ulysses
?
ISBN ?

Goethe, J.W.
Faust I
Reclam, 1986
ISBN 3-15-000001-7

Goethe, J.W.
Faust II
Reclam, 1986
ISBN 3-15-000002-5

Finnish Folklore
Joulupuu on rakennettu

Guns 'n' Roses
You Could Be Mine

Goldhurst, W.
Of Mice and Men: John Steinbeck's Parable Of The Curse Of Cain
Western American Literature, Colorado, Vol 6, 1971, pp 123-135

Twain, M.
Megszelídítem a kerékpárt
Európa Könyvkiadó, Budapest, 1980, text from back cover
ISBN 963-07-2036-1

The Circle
Pi
Digits 1-3141

Problem F: Fiber Network

This is a transivie hull problem, which can be solved with the standard Floyd-Warshall algorithm. Since n<=200, the a runtime of O(n^3) is sufficient. The number of queries is not limited, so any Single-Source algorithm is too slow, if not used with memoization.

However, in the worst case, 26 transitive hulls have to be computed, one for each company. This computation can be done in parallel by coding the companies as bits of a 32-bit-integer. The and, or operations from the transitive hull computation extend to bit-wise and, or computations, which can be performed in O(1) supposing a uniform complexity measure.

Judges' test data was built from several hand-crafted test cases, along with several randomly generated tests, one of which had indeed the maximum allowed number of nodes. The total number of test cases is 17.

Rating: Medium

Problem G: Global Roaming

This is a standard 3D-geometry problem. A satellite is visible, if it is on the other side of the plane that touches the earth in the location of observation (tangential plane). This plane is best described by its normal vector, which is just the vector from the earth's center to the point of observation. To see, on which side of the plane the satellite is, amounts to calculate a scalar product of cartesian coordinates (which have to be calculated first). A common mistake is to take the vector from the center of the earth to a satellite instead of the vector from the location of observation to it.

Judges' test data was built from several hand-crafted test cases, along with data obtained from the Internet. The total number of test cases is 6, and the total number of queries is 4453.

Rating: Medium

Problem H: Hard to Believe, but True!

This is the easiest problem in this contest. You can avoid parsing the numbers by first reversing the equations, and then using "scanf" or something equivalent to read the numbers in reversed form.

Judges' test data was built from several hand-crafted test cases, along with several randomly generated tests. The total number of test cases is 108.

Rating: Easy

Stoy, J.E.
Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory
Page 27 (in the fifth printing from 1989), MIT-Press, 1977
ISBN 0-262-69076-4