Problem A: All in All
The greedy solution works, i.e. use a pointer into the supposed subsequence that is advanced if a character matches while you iterate through the supersequence.
Judges' test data was created from hand-crafted data. Total number of test cases is 13.
Rating: Easy
Problem B: Balanced Food
The pizza falls down, if its center of gravity lies outside the slice-shaped (convex) table. This can be tested by elementary geometrical means. The center of gravity of the pizza is the arithmetic mean of the center of gravity of its slices. These can be calculated by integration (by hand).
There are n! different ways to eat the slices. The brute force solution would be to try every permutation. This can be improved upon by backtracking. Remove the slices one-by-one - if the center of gravity of the remaining pizza lies outside the table you can cut off this branch.
Judges' test data was constructed from a test set of possible and impossible problems with different pizza sizes and locations and the unit-quarter-circle as table for every legal value of n. 100 random-generated test cases were added leading to a total of 156 test cases. There are test cases with relatively long execution times using the backtracking solution.
Rating: Hard
Reference
Bronstein, I.N. ; Semendjajew, K.A. ; Musiol, G. and Mühlig, H.
Taschenbuch der Mathematik
Tab. 7.4: Anwendung von Doppelintegralen, Page 318, Harri Deutsch, 1. edition, 1993
ISBN 3-8171-2001-X
Problem C: California Jones and the Gate to Freedom
The index of the given combination of n/2 numbers from n numbers is calculated with the help of a recursive formula. Combinations are ordered in such a manner that taking the k-th stone from a list always leads to a combination with smaller index than a combination where the k-th stone is not taken (the first k-1 stones having the same status). Binomial coefficients have to be calculated. Although the resulting coefficients always fit into a 32-bit int, the calculation must be done carefully to ensure that no overflows occur (double helps).
Judges' test data was created from some hand-crafted data, along with an exhaustive test of the n=4 case. Finally 50 random-generated tests were added, each with 10 sub-cases of which at least 1 was correct. Total number of sub-cases is 561.
Rating: Medium
Reference
ACM University of Ulm Local Contest 1997
Problem B: Binomial Showdown
Ulm, 1997
Problem D: Diplomatic License
The Foreign Offices are best represented as complex numbers. The meeting location of point p and point q is (p+q)/2.0 (and thus needs not to be integer).
Judges' test data was created from hand-crafted data, as well as from randomly generated data. The test cases are identical with those for problem E. Total number of test cases is 107.
Rating: Easy
Reference
Dijkstra, E.W.
A Collection of Beautiful Proofs
EWD 538, pp. 174-183 of:
Selected Writings on Computing: A Personal Perspective
Springer Verlag, 1982
ISBN 0-387-90652-5
Problem E: Polygon Programming with Ease
The meeting locations are best represented as complex numbers. A linear equation relating each meeting location to the two involved Foreign Offices can be set up. This system of n equations for n unknowns can be solved if n is odd.
It is also possible to notice that the sequence of n reflections about the meeting locations rotates the wanted polygon about 180 degrees and transforms the first Foreign Office onto itself. This sequence of reflections is therefore equivalent to a reflection about the first Foreign Office. Hence, you can take an arbitrary point p in the plane, undergo this transformation to get a point q, and calculate the first Foreign Office as (p+q)/2.0.
Judges' test data was created from hand-crafted data, as well as from randomly generated data. The test cases are identical with those for problem D. Total number of test cases is 107.
Rating: Medium
Reference
Dijkstra, E.W.
A Collection of Beautiful Proofs
EWD 538, pp. 174-183 of:
Selected Writings on Computing: A Personal Perspective
Springer Verlag, 1982
ISBN 0-387-90652-5
Problem F: The Sierpinski Fractal
This problem is best solved recursively, as its specification suggests.
Judges' test data consists of all 10 possible test cases arranged in a pseudo-random order.
Rating: Medium
Reference
Mandelbrot, B.
The Fractal Geometry of Nature
W.H. Freeman and Co., 1988
ISBN 0-7167-1186-9
Problem G: Paths on a Grid
Given the size of the rectangle n and m we could have stated the problem as well as: calculate (n+m) choose n. So the task was to calculate binomial coefficients. This can be done by a standard algorithm (for the sake of efficiency the algorithm must not be too naive). Observe that a dynamic programming approach calculates exactly a part of Pascal's triangle. However, this fails due to the large numbers permitted in the input.
Judges' test data was created from the input file of a similar problem from a previous local contest, along with several rectangles of width or height 0 or 1. Finally 0<=n,m<10 was tested exhaustively. Total number of test cases is 241.
Rating: Medium
Reference
ACM University of Ulm Local Contest 1997
Problem B: Binomial Showdown
Ulm, 1997Gries, D. and Schneider, F.B.
A Logical Approach to Discrete Math
Example 16.35, p. 351, Springer-Verlag, 1993
ISBN 0-387-94115-0
Problem H: Hall of Fountains
The fountains act periodically, their period may be any even number from 2 to 20. Thus the whole system has a period of maximally lcm(2,4,6,8,10,12,14,16,18,20)=5040, where lcm denotes the generalized least common multiple function. The person walking the hall can at each moment be in one of n+2 positions. Together, person and fountains can be in maximally 102*5040=514080 different states. Search this space with standard breadth first search.
Judges' test data was created from some hand-crafted data, along with an exhaustive test of the n=1 case and the n=2,p1<=2,p2<=3 case. Finally 50 random-generated tests were added. Total number of test cases is 125.
Rating: Hard