Judges' Comments on the Problems and their Solutions

Problem A: Ambiguous permutations

This problem is the easiest of the problemset. Just form the inverse permutation of the given permutation, then check whether it is different or not.

for i := 1 to n do
	inv[ p[i] ] := i
end

Then, use another for loop to check whether for all i p[i] = inv[i].
It is also possible to avoid using another array for the inverse permutation. Since inv[i] gives the position of integer i in p, p[ inv[i] ] = i. Therefore, the check inv[i] = p[i] is equivalent to i = p[ p[i] ].

Judges' test data consists of 80 test cases: all possible test cases with n<=4, 43 random test cases with n <= 10000, and 4 test cases with n = 100000.

Rating: Easy

Problem B: Bullshit Bingo

This problem is the second easiest of the problemset. Basically, you have to extract the words from the given text, detect the word "BULLSHIT", which marks the end of a game, and count the number of different words in each game. A method to compare the words in a case-insensitive way is to convert them to uppercase.
The given limits allow inefficient solutions, there is no need to use a hashtable for storing the different words. However, using a data structure of a library of the programming language of your choice can simplify the problem a lot.

In order to produce the reduced fraction, it is fast enough to check all numbers from 2 to <number of games> if they divide both the numerator and the denominator. However, a more elegant solution calculates the greatest common divisor of the numerator and the denominator using the Euclidean algorithm.

Judges' test data is derived from the manual of the programming language INTERCAL.

Rating: Easy

Reference

Bullshit Bingo
INTERCAL programming language

Problem C: 106 miles to Chicago

This problem is quite easy if you are familiar with shortest path algorithms.
First, you should convert the given percentage values into absolute values by dividing by 100. Then, the safety value of a path is just the product of the probabilities of the streets used.

The judges' solution uses a modified Floyd-Warshall algorithm. Instead of updating the best path from point a to b using the sum of the paths from a to c and c to b, we take the product of the values of the paths.

Judges' test data consists of 80 randomly generated test cases.

Rating: Easy

Reference

Blues Brothers
Floyd-Warshall

Problem D: Decorate the wall

There is a simple solution to this problem, but if you do not see it, the problem becomes quite tricky.
First, you have to observe that the number of positions you have to try to appoint to the lower left corner of the given painting is limited. It makes no sense to place it somewhere where its left side does not touch another painting (or the wall). The same is true for the bottom of the painting.
This observation reduces the number of points you have to try to O(n²). For each point, check in O(n) if the painting intersects with another painting. Thus, the overall complexity is O(n³).

There is also a O(n²) scanline algorithm, which is more difficult to code.

Judges' test data consists of 199 test cases with different values of n. Most of the test cases are random-generated.

Rating: Medium

Problem E: European railroad tracks

It is important not to underestimate the difficulty of this problem. It is clear that the given limits allow a backtracking solution, and in fact we do not know if a polynomial solution for this problem exists.

First, we can place one rail at position 0. Then, the backtracking procedure tries to place a new rail in such a way that its distance to an already existing rail is one of the given distances. If there are already k rails, for each rail the procedure tries to place the new rail at the required distance before or after that rail. However, it is not enough to try to construct the required distances in the given order; this construction method requires to try all permutations of the given distances.

The complexity of this algorithm is O(2ⁿ*(n!)²). However, the restriction that there will always be a solution with ≤ 5 rails reduces it to a maximum of 2⁵*(5!)*(n!) steps.

Judges' test data consists of 28 test cases, 16 of them are hand-crafted, 12 are random-generated.

Rating: Hard

Reference

Perfect Ruler
Railway gauges

Problem F: Any fool can do it

The easiest way to solve this problem is to follow the informal description of a set. One function returns if the string is a set or not. This function calls another function which determines if a string is a list. A list is either empty, has one element or has a ',' character which separates an element from the remaining list. An element is either a set or consists of only one character (a letter of the given alphabet).

However, since in the function which checks if the string is a list we have to try all ',' as a separator, we would calculate some results more than once (in fact, the number of calculations grows exponentially). The standard trick is to store the intermediate results and return a result directly instead of calculating it again.

Other methods to solve this problem:

• Use dynamic programming, which calculates the results with increasing length of the substrings.
• Convert the given grammar into Chomsky Normal Form and use the Cocke-Younger-Kasami (CYK) algorithm.
• Use an automaton-based approach which will lead to an O(n^2) algorithm (http://www.informatik.uni-ulm.de/acm/Locals/2005/solution/other/fool_peter.cc)

Judges' test data consists of 1200 test cases. It contains all possible strings of length <= 6, 5 timeout cases for recursive solutions without memoization and 103 random test cases.

Rating: Medium

Reference

CYK algorithm

Problem G: Game schedule required

This problem would be a lot easier if the number of teams were always a power of 2. Just sort the teams by number of remaining games, and you will know which team will be eliminated in which round. However, if the number of teams is no power of 2, it may happen that a team winning the tournament has only one game, but always gets a wildcard in the rounds before the final.
Obviously, teams with more than one remaining game have to advance to the next round (either by winning a game, or by getting a wildcard). Consequently, teams with only one remaining game are candidates for elimination.
If the number of teams in the current round is even, half of the teams will have only one remaining game, so you just have to schedule these games in such a way that these teams will be eliminated.
If the number of teams in the current round is odd, there are two cases:

• There are n div 2 teams with only one remaining game. Then, after scheduling these games, there will be one team which has more than one game left and plays no game in the current round and thus has to get the wildcard.
• There are n div 2 + 1 teams with only one remaining game. According to the pidgeonhole principle, there must be two teams with one remaining game which require the same opponent. One of these two teams has to get the wildcard, and it is easy to see that it doesn't matter which of them.

Judges' test data consists of 50 test cases, 45 of them are random-generated.

Rating: Hard

Reference

Pidgeonhole principle

Problem H: Help the problem setter

As the inductive definition of a binary search tree suggests, this problem is best solved using recursion.
Obviously, if the tree has only 1 node, there is only one binary search tree, so we can use any frequency (for example 1). Now assume we want to calculate the frequency for an inner node. First, we calculate the frequencies of the nodes in its left and right subtree by recursive calls. Now, we have to think about what happens if we do not use the current node as the root of its subtree. This means, that either a node of the left subtree or of the right subtree becomes the root. Without loss of generality, assume that a node L of the left subtree becomes the root. This means that some nodes may move from the left subtree to the right subtree. Obviously, this will only increase the access cost for the right subtree, so if we want to determine the lowest possible access cost, we keep the cost of the right subtree artificially constant. This can be done if we allow the new root to have 4 children.

Because the frequencies of the subtrees were determined in such a way that there is a unique optimal binary search tree, the structure of the left subtree does not change, but all nodes of the left subtree move one level up. That means that the access cost of the data structure decreases by the sum of the frequencies of nodes in the left subtree.
The new root gets two additional children: the old root and the root of the right subtree. For the same reason as above, the structure of the right subtree does not change. Obviously, converting this data structure to a binary search tree with the root L will only increase the access cost.

Now let the frequency F of the old root be 1 plus the sum of the frequencies of all nodes in the left and right subtree. As it is no longer the root, its access cost increases by F, i.e. the overall access cost increases by more than it decreases. Therefore we will get worse results if we use another node as the root.

It remains to show that the frequencies calculated by this method will not exceed 2⁶³-1.
We claim that the sum of the frequencies in a tree with n nodes is < 2ⁿ. This is proved by induction on the number of nodes.
With only one node, the node gets a frequency of 1, which is smaller than 2¹.
Now assume the claim is true for any number of nodes between 1 and n-1 nodes. Lets look at a tree with n nodes with r nodes in the right subtree and n-r-1 nodes in the left subtree. The root gets the sum of the frequencies in the left and right subtree + 1 as its frequency. According to our assumption, this sum is <= 2^n-r-1-1 + 2^r-1 + 1. Therefore, the sum of the frequencies of all n nodes is 2*(2^n-r-1-1 + 2^r-1) + 1. It is obvious that this value is largest if r is 0 or n-1. In that case, the sum of all frequencies is 2*(2^n-1-1)+1 = 2ⁿ-1, which proofs the claim.
As a corollary, we can derive that the worst case is a degenerated tree in the form of a linear list.

Judges' test data consists of 200 test cases; most of them are random-generated.

Rating: Medium

Reference

University of Ulm Local Contest 2004, problem G