Match Editorial

SRM 253 had a large turnout, and also offered cash prizes to the top finishers in each room. Coincidence? Eryx finished first in division 1, with the fastest time on the 1000-point problem. A successful challenge by snewman lifted him up to second place, with Petr finishing third. tomek followed closely behind, rising to within 7 rating points of the top spot on the coder ranking list.

In division 2, newcomer soul-net finished in first place by a margin of over 100 points, with the fastest time on the 1000-point problem and 5 successful challenges. Such success with challenges is rarely seen from coders competing in their first TopCoder event. killer and motono finished second and third, followed closing by cryst.

The Problems

Value	250
Submission Rate	339 / 373 (90.88%)
Success Rate	271 / 339 (79.94%)
High Score	RizLA for 247.85 points (2 mins 39 secs)
Average Score	208.52 (for 271 correct submissions)

To solve this problem, you must simply loop over all the boxes in the input, test each one to see if the object will fit inside, and keep track of the area of the smalled box. Here is a sample solution:

    int smallBox(int objWidth, int objLength, vector<int> boxWidth, vector<int> boxLength) {
        int ret = -1;
        for (int i=0; i<boxWidth.size(); i++) {
            const int W = boxWidth[i];
            const int L = boxLength[i];
            if ((W ≥ objWidth && L ≥ objLength) || (W ≥ objLength && L ≥ objWidth))
                if (ret == -1 || W*L < ret)
                    ret = W*L;
        }
        return ret;
    }

The only tricky part is that you need to test the box in each of the two possible orientations.

Value	500
Submission Rate	201 / 373 (53.89%)
Success Rate	153 / 201 (76.12%)
High Score	gcdart for 482.45 points (5 mins 27 secs)
Average Score	280.17 (for 153 correct submissions)

Value	250
Submission Rate	269 / 282 (95.39%)
Success Rate	251 / 269 (93.31%)
High Score	antimatter for 247.05 points (3 mins 6 secs)
Average Score	186.78 (for 251 correct submissions)

The solution to this problem has three parts: 1) finding the frequency of letters appearing in the encoded text, 2) sorting these letters by frequency, and 3) replacing them with those given in the frequencyOrder string. To see how these steps can be coded efficiently, let's dissect antimatter's solution, which took him just over 3 minutes to write. (I have expanded some macros and renamed the parameters to the function, for purposes of clarification.)

    vector<string> decipher(vector<string> encoded, string
frequencyOrder) {
        map<char, int> foo;
        for (int i = 0; i < encoded.size(); i++) {
            for (int j = 0; j < encoded[i].size(); j++) {
                if (encoded[i][j] != ' ') foo[encoded[i][j]]++;
            }
        }

The first few lines loop over each character of each line in the encoded text, making a histogram of the letter occurrences. He uses an STL map to keep a count of how many times each letter appears.

        vector<pair<int,char> > X;
        for (map<char,int>::iterator i = foo.begin(); i != foo.end(); ++i) {
            X.push_back(make_pair(-i->second, i->first));
        }
        sort(X.begin(), X.end();

The next 5 lines sort the letters by frequency. He first creates an STL vector data structure of pairs, where each pair contains the frequency and the letter. The STL sort() algorithm sorts the pairs based on the first element in each pair (the letter frequency). Note that only letters that appear in encoded will have been added to the map, and therefore only those letters will be present in the vector. Also note that this implicitly implements the tie-break case in the problem statement, because the letters will be read out of the map in alphabetical order, and sort() will not swap two letters that have the same frequency.

        map<char,char> rev;
        for (int i = 0; i < X.size(); i++) rev[X[i].second] = frequencyOrder[i]; 

He can get the letters sorted by frequency by looking at the second element in each of the sorted vector of pairs. He copies these letters into a second STL map to creating a remapping table. This code relies on the fact that X will contain the same number of elements as there are characters in frequencyOrder.

        for (int i = 0; i < encoded.size(); i++) {
            for (int j = 0; j < encoded[i].size(); j++) {
                if (encoded[i][j] != ' ') encoded[i][j] = rev[encoded[i][j]];
            }
        }
        return encoded;
    }

These last few lines simply loop over each character of each line of encoded, and replace them using the remapping table created above.

Value	1000
Submission Rate	104 / 373 (27.88%)
Success Rate	33 / 104 (31.73%)
High Score	soul-net for 901.29 points (9 mins 37 secs)
Average Score	676.34 (for 33 correct submissions)

Several coders were tempted to solve this function with a recursive function. Starting at each 'A' in the grid and recursing on each neighboring 'B'. The recursive function would then call itself on each neighboring 'C', and so on, until it reaches the end of a path. Such a solution does it fact find every path of consecutive letters and works fine for small input cases. But the problem is that some input cases contain billions of paths, and the simple recursive solutions timed out in the system tests.

A more efficient solution is instead of finding each path, mark all the letters that are part of a path. For example, consider the grid given in the problem statement:

A B E
C F G
B D H
A B C

We'll use uppercase letters to represent letters that are part of a path. Since all paths start with 'A', every 'A' is in a path and we'll initialize them to uppercase and all other letters to lowercase:

A b e
c f g
b d h
A b c

Now, the next step is to loop over all the letters and look for any 'b' that is next to an uppercase 'A', and change those 'b's to uppercase:

A B e
c f g
B d h
A B c

Then, loop over all the letters and look for any 'c' that is next to an uppercase 'B':

A B e
C f g
B d h
A B C

And then 'd':

A B e
C f g
B D h
A B C

The search for an 'e' next to an uppercase 'D' doesn't result in any matches. Therefore, the longest path is from 'A' to 'D', 4 letters long. A solution could also use a second 2-dimensional array of boolean values to mark which letters are reachable, rather than changing them from lowercase to uppercase. Note that the maximum running time of this algorithm is the size of the largest grid (50x50) times the longest possible path (26), much smaller than the billions of paths a simple recursive solution would have to find.

If you enjoyed this problem, and are looking for something similar but a little more challenging, try solving the next problem "AlphabetCount" in the division 1 practice room.

Value	500
Submission Rate	243 / 282 (86.17%)
Success Rate	177 / 243 (72.84%)
High Score	HardCoder for 497.78 points (1 mins 54 secs)
Average Score	369.71 (for 177 correct submissions)

This was a straightforward dynamic programming problem, solved by keeping a count of subpaths to each letter. Create a 2-dimensional array, and initialize it with a 1 corresponding to each 'A' in the grid, and a 0 for all other letters. Then, for each 'B' in the grid, set its value to the sum of the values of all adjacent 'A's. Next, for each 'C' in the grid, set its value to the sum of the values of all adjacent 'B's. Repeat for all letters up to the limit specified as a parameter to the problem, and then return the sum total of the values for that letter. The only thing you need to be careful about is avoiding arithmetic overflow.

For an example of a clean, easy-to-read implementation, see HardCoder's solution, which he wrote in under 2 minutes!

Value	1000
Submission Rate	37 / 282 (13.12%)
Success Rate	14 / 37 (37.84%)
High Score	Eryx for 670.23 points (22 mins 23 secs)
Average Score	518.47 (for 14 correct submissions)

The first key to this problem is expressing the pitcher's chance of success (a strike out) as a 2-dimensional function of the probabilities that the pitcher and batter use to select a pitch. The second key is to then solve for the two values of those probabilities that define the "equilibrium point", the point where neither the batter nor the pitcher can improve their situation.

Imagine the function as a terrain, and the equilibrium point as a ball on that terrain. The pitcher wants to get the ball to as high an elevation as he can, but can only roll it north and south. The batter wants to get the ball to as low an elevation as he can, but can only roll the ball east and west. The (an) equilibrium point is a location on the terrain where if the pitcher were to roll the ball north or south, the batter would then immediately be able to roll the ball east or west to a lower elevation, thus improving his situation. And, at the same time, at this point if the batter were to roll the ball east or west, the pitcher would then immediately be able to roll the ball north or south to a higher elevation, improving his situation.

In this problem, the function that expresses the pitcher's chance is a linear combination of his chances of success for each of the 4 possible combinations of the batter and pitcher choosing a fast ball or a curve ball. Since this function is bilinear, the equilibrium point described above is either at one of the four corners, or where the gradient is zero. When the count is 3 balls and 2 strikes, these chances come directly from the stats parameter to the problem. For other counts, they also depend on the solution to the problem with balls+1 and with strikes+1, which can be obtained with a recursive call to the method.

Here is my solution to this problem:

    public double strikeOut(double[] stats, int balls, int strikes) {
        double P_strike = (strikes < 2) ? strikeOut(stats, balls,
strikes+1) : 1;
        double P_ball   = (balls < 3)   ? strikeOut(stats, balls+1,
strikes) : 0;
        double A = P_ball * stats[0] + P_strike*stats[1];
        double B = P_ball * stats[2] + P_strike*stats[3];
        double C = P_ball * stats[4] + P_strike*stats[5];
        double D = P_ball * stats[6] + P_strike*stats[7];
        if (A ≥ B && C ≥ D) return Math.max(B, D);
        if (A ≤ B && C ≤ D) return Math.max(A, C);
        if (A ≥ C && B ≥ D) return Math.min(A, B);
        if (A ≤ C && B ≤ D) return Math.min(C, D);
        return (A*D - B*C) / (A+D-B-C);
   }

See the discussion in the forums for an even shorter solution by snewman.