Saturday, December 9, 2006 Match summary
Over 1100 coders registered for this round. In division 1, bmerry was first to submit all three problems, but eventually the current TCO and TCCC champion Petr took first place, scoring over 1500 points in the coding phase and securing his victory with a successful challenge. tomek took second place, thanks to 150 points scored in the challenge phase, and bmerry took third place in the final ranking.
The ProblemsVowelEncryptorUsed as: Division Two  Level One:
The algorithm here is quite straightforward: for every word in the input array, remove all vowels from it and either store the result in the output array or, if no letter is left, copy the original word to the output array. There are several possible approaches to removing all vowels from a word.
String noVowels = text[i].replaceAll("[aeiou]",""); text[i] = noVowels.equals("") ? text[i] : noVowels;In C++, one of the possible approaches would be: string::iterator it = partition(text[i].begin(), text[i].end(), isVowel); if (it != text[i].end()) text[i].erase(text[i].begin(), it);Where isVowel is a predicate that checks whether the provided char is a vowel. RailroadSeatNumeration Used as: Division Two  Level Two: Used as: Division One  Level One:
First, one could notice that for every seat, its number in the international numeration is always larger than it is in the domestic numeration. Thus, if every element in the input array is a valid seat number in both international and domestic numerations, we can safely return "AMBIGUOUS". If the data is not ambiguous, we can either determine which numeration method is used in the input array and convert the array to the international numeration, or return "BAD DATA" if the provided numbers don’t fit into any numeration. Pseudocode follows. bool isInternational = true bool isDomestic = true for each x in tickets: isInternational = isInternational AND (x/10 == 1..9) AND (x%10 == one of 1, 3, 4, 6) isDomestic = isDomestic AND (x == 1..36) if isInternational AND isDomestic: return "AMBIGUOUS" if isInternational: return string representation of tickets if isDomestic: for i = 0 .. number of tickets  1: tickets[i] = 1 tickets[i] = (tickets[i] / 4 + 1) * 10 + (tickets[i] % 4) * 2 + (tickets[i] % 4 < 2) return string representation of tickets return "BAD DATA"ProbabilisticTranslator Used as: Division Two  Level Three:
This problem can be solved using a dynamic programming (DP) approach. Let n be the total number of words in the text. When we have translated the first k words of the text, translation of the other (n  k) words depends only on the translation of the k^{th} word and doesn’t depend on translation of the first (k  1) words. In other words, the only information that is needed to translate the last (n  k) words is the translation variant that was chosen for the k^{th} word. Thus the following recurrence relation can be used to solve this problem: f_{k, t} = maximum over all possible t’ (f_{k  1, t’} + frequency_{t’, t})f_{k, t} is the fidelity of translation of the first k words if the k^{th} word is translated as t. f_{k  1, t’} is the fidelity of translation of the first (k  1) words if the (k  1)^{th} word is translated as t’. frequency_{t’, t} is the frequency of the corresponding pair of words. The answer for the problem is max(f_{n, t}) where t can be any translation variant of the last word of the text. Since the total number of words in the text doesn’t exceed 50 * 50 / 2 = 1250, the number of possible translations for any word is less than 50 / 2 = 25, we need at most 25 operations to calculate any f_{k, t}, and the total number of operations to solve the problem is less than 1250 * 25 * 25 = 781250 if we use arrays to store values of f_{k, t} and frequencies. It is also possible to store those values in maps, which may make the code shorter but slightly slower. LogCutter Used as: Division One  Level Two:
First thing to notice here is that DP approach with O(K * C) complexity won’t work here because it is too slow and may require too much memory. On the other hand, if we knew the length of the longest piece of the log, we could easily find the minimum number of cuts needed, as well as the smallest coordinate of the first cut, for the given number of allowed cuts. This can be done by a greedy algorithm that maximizes the length of the last piece of the log, then maximizes the length of the last but one piece, and so on. The reason to start with the last (rightmost) piece here is that such an approach minimizes the length of the leftmost piece, which is equal to the coordinate of the leftmost cut. If the greedy algorithm ends up with no more than (C + 1) pieces, then it is possible to cut the log with the given length of the longest piece, otherwise a larger length of the longest piece is needed.
left = 1 right = L while left < right: v = (left + right) / 2 first = firstCut(v) if first == 0: left = v + 1 else: right = v return left + " " + firstCut(left)RPSChamps Used as: Division One  Level Three:
This problem involves simple dynamic programming and some probability theory.
P_{0, 0} = 1 P_{a < 0, b} = P_{a, b < 0} = 0 P_{a, b} = 1/3 * P_{a  1, b} + 1/3 * P_{a, b  1}Now, let f_{n} be the expected number of rounds in a tournament with n participants. Let’s see what happens if a players cast Scissors and b players cast Paper in the first round of a tournament with n = (a + b) players, where both a and b are positive integers. The probability of such result of the first round is P_{a, b}, and the expected total number of rounds in the tournament would be 1 + f_{a} + f_{b}. Since there are 3 possible figures in the game, 3 * P_{a, b} is the probability that after the first round the tournament will split into two subtournaments of a players and b players, so that the a players will take places 1 through a, and the other b players will take places (a + 1) through (a + b). If we iterate over all possible pairs of a and b and add up the values of 3 * P_{a, b}, we will get the probability of the first round of a tournament with n = (a + b) players not being replayed. P_{no replay} = sum for each i = 1 .. n  1 (3 * P_{i, n  i})The following recurrence relation can be used to calculate f_{n} if we know the value of f_{N  1}. f_{n} = P_{replay} * (1 + f_{n}) + sum for each i = 1 .. N  1 (3 * P_{i, N  i} * (1 + f_{i} + f_{n  i}))P_{replay} is the probability of the first round being replayed, which is equal to 1  P_{no replay}. We can transform the last relation for f_{n} as follows: f_{n} * P_{no replay} = P_{replay} + sum for each i = 1 .. N  1 (3 * P_{i, N  i} * (1 + f_{i} + f_{n  i}))And here is a Java solution that implements the described approach. public double numberOfMoves(int N) { double P[][] = new double[N+2][N+2]; P[0][0] = 1; for (int i = 0; i <= N; i++) { for (int j = 0; j <= N; j++) { P[i][j + 1] += P[i][j] * 1/3.; P[i + 1][j] += P[i][j] * 1/3.; } } double f[] = new double[N]; // f[i] = number of moves for i+1 players. f[0] = 0; for (int i = 1; i < N; i++) { f[i] = 0; double p = 0; // probability of no replay for (int j = 1; j < i+1; j++) { // j players beat the other i + 1  j players p += 3 * P[j][i + 1  j]; f[i] += 3 * P[j][i + 1  j] * (f[j  1] + f[i  j]); } f[i] += 1; f[i] /= p; } return f[N1]; } 
