JOIN
Get Time
statistics_w  Match Editorial
Archive
Printable view
 Match Overview
Discuss this match
SRM 329
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.

In division 2, UdH-WiNGeR came in first with an impressive 1250 points, followed by newcomer kood_pl. The third place went to bySerge. All three advanced to Division 1.

The rating gap between Petr and tomek decreased by 7 points, and the gap between Russian Federation and Poland increased by some 15 points.

The Problems

VowelEncryptor rate it discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 524 / 573 (91.45%)
Success Rate 463 / 524 (88.36%)
High Score charsi420 for 248.30 points (2 mins 21 secs)
Average Score 208.76 (for 463 correct submissions)

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.

In Java, one of the easiest ways to process a word would be the following: 

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 rate it discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 420 / 573 (73.30%)
Success Rate 122 / 420 (29.05%)
High Score UdH-WiNGeR for 452.76 points (9 mins 22 secs)
Average Score 286.05 (for 122 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 480 / 486 (98.77%)
Success Rate 308 / 480 (64.17%)
High Score Michael_Levin for 241.53 points (5 mins 21 secs)
Average Score 189.96 (for 308 correct submissions)

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 rate it discuss it
Used as: Division Two - Level Three:
Value 1000
Submission Rate 46 / 573 (8.03%)
Success Rate 12 / 46 (26.09%)
High Score goons_will_rule for 575.11 points (29 mins 28 secs)
Average Score 486.34 (for 12 correct submissions)

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 kth 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 kth word. Thus the following recurrence relation can be used to solve this problem: 

fk, t = maximum over all possible t’ (fk - 1, t’ + frequencyt’, t)
fk, t is the fidelity of translation of the first k words if the kth word is translated as t. fk - 1, t’ is the fidelity of translation of the first (k - 1) words if the (k - 1)th word is translated as t’. frequencyt’, t is the frequency of the corresponding pair of words. The answer for the problem is max(fn, 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 fk, 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 fk, t and frequencies. It is also possible to store those values in maps, which may make the code shorter but slightly slower.

LogCutter rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 198 / 486 (40.74%)
Success Rate 126 / 198 (63.64%)
High Score andrewzta for 447.80 points (9 mins 56 secs)
Average Score 292.04 (for 126 correct submissions)

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.

Assume that we have a function firstCut(maxPart) that returns the smallest possible coordinate of the first cut when the maximum allowed length of a piece of the log is maxPart, or zero, if it is impossible to cut the log into pieces that are not longer than maxPart using at most C cuts. We can implement such function using the greedy approach described above. Then we can find the minimum value of maxPart using binary search taking into account that maxPart can vary in range from 1 to L. Pseudocode follows. 

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 rate it discuss it
Used as: Division One - Level Three:
Value 900
Submission Rate 67 / 486 (13.79%)
Success Rate 60 / 67 (89.55%)
High Score Petr for 822.34 points (8 mins 54 secs)
Average Score 567.34 (for 60 correct submissions)

This problem involves simple dynamic programming and some probability theory.

Let Pa, b be the probability that in a round with (a + b) players a of them will cast Scissors and the other b players will cast Paper. We can calculate values of Pa, b using the following recurrence relation: 

P0, 0 = 1
Pa < 0, b = Pa, b < 0 = 0
Pa, b = 1/3 * Pa - 1, b + 1/3 * Pa, b - 1
Now, let fn 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 Pa, b, and the expected total number of rounds in the tournament would be 1 + fa + fb. Since there are 3 possible figures in the game, 3 * Pa, 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 * Pa, b, we will get the probability of the first round of a tournament with n = (a + b) players not being replayed. 
Pno replay = sum for each i = 1 .. n - 1 (3 * Pi, n - i)
The following recurrence relation can be used to calculate fn if we know the value of fN - 1. 
fn = Preplay * (1 + fn) + sum for each i = 1 .. N - 1 (3 * Pi, N - i * (1 + fi + fn - i))
Preplay is the probability of the first round being replayed, which is equal to 1 - Pno replay. We can transform the last relation for fn as follows: 
fn * Pno replay = Preplay + sum for each i = 1 .. N - 1 (3 * Pi, N - i * (1 + fi + fn - 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[N-1];
}

Author
By dmytro
TopCoder Member