JOIN
 Match Editorial
SRM 253
Saturday, July 23, 2005

Match summary

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

ObjectPacking
Used as: Division Two - Level One:
 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.

Decipher
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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.

ABCPath
Used as: Division Two - Level Three:
 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.

AlphabetCount
Used as: Division One - Level Two:
 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!

Pitches
Used as: Division One - Level Three:
 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.

By legakis
TopCoder Member