JOIN
 Match Editorial
SRM 249
Wednesday, June 29, 2005

Match summary

An amazingly difficult Division 1 Easy/Division 2 Hard gave this SRM an unusual flavor. Less than one-third of Div 1 received credit for the problem. Not a single Div 2 Hard submission passed system tests. Despite the round's oddities, natori and jdmetz took the top 2 spots with first rate performances. In Division 2, sempiq won by a comfortable margin.

# The Problems

ChatTranscript
Used as: Division Two - Level One:
 Value 250 Submission Rate 231 / 246 (93.90%) Success Rate 169 / 231 (73.16%) High Score Sleeve for 249.51 points (1 mins 16 secs) Average Score 231.28 (for 169 correct submissions)

This problem is easily solved using the available string processing routines. Java code follows:

```public int howMany(String[] transcript, String name) {
int ret = 0;
for (int i = 0; i < transcript.length; i++)
if (transcript[i].startsWith(name+":")) ret++;
return ret;
}
```

FieldPairParse
Used as: Division Two - Level Two:
 Value 500 Submission Rate 142 / 246 (57.72%) Success Rate 119 / 142 (83.80%) High Score sempiq for 459.22 points (8 mins 37 secs) Average Score 303.66 (for 119 correct submissions)

In this problem, we loop through each column checking whether it is entirely blank or not. When a blank column is found, we count the adjacent blank columns, and store this value in an array. When this loop is done, the array contains all necessary information. The constraints eliminate the potentially tricky cases where delimiters occur on the ends. Java code follows:

```public int[] getPairs(String[] data) {
ArrayList<Integer> al = new ArrayList();
int cnt = 0;
for (int c = 0; c < data[0].length(); c++) {
boolean allSpaces = true;
for (int r = 0; r < data.length; r++)
if (data[r].charAt(c) != ' ') allSpaces = false;
if (!allSpaces && cnt > 0) {
al.add(cnt);
cnt = 0;
}
if (allSpaces) cnt++;
}
int[] ret = new int[al.size()];
for (int i = 0; i < ret.length; i++) ret[i] = al.get(i);
return ret.length % 2 == 0 ? new int[0] : ret;
}
```

TableSeating
Used as: Division Two - Level Three:
 Value 1100 Submission Rate 6 / 246 (2.44%) Success Rate 0 / 6 (0.00%) High Score null for null points (NONE) Average Score No correct submissions
Used as: Division One - Level One:
 Value 350 Submission Rate 102 / 233 (43.78%) Success Rate 73 / 102 (71.57%) High Score venco for 253.32 points (19 mins 9 secs) Average Score 195.76 (for 73 correct submissions)

This problem asks for the expected number of seats filled. An expectation is computed by summing Prob{e}*Value(e) over all possible events e. Prob{e} is the probability that event e will occur. Value(e) is the value we associate with event e. Following the above explanation, we must consider all possible seating arrangements, counting how many tables are used in each.

Our recursive solution will take the current seating arrangement as a parameter (perhaps in a bitmask), and return the expected number of tables used. For each possible group size, we must consider all ways of seating them, and then recursively call our function with the new configuration. For example, suppose there was an empty restaurant with 10 tables, and a group requiring 2 tables enters. Each way of seating them occurs with probability 1/9 (on top of whatever probability is associated with a group arriving that requires 2 tables). One possible way is drawn below (T for empty table, U for used table):

```   T   T   T   U   U   T   T   T   T   T
```
Our function can now be called recursively with this seating configuration. Combining the expectations associated with each possible seating (accounting for their respective probabilities), we can compute the total expectation. Sadly, the method described here is too slow to work. Fortunately, we can quickly fix it by caching the expectation associated with each seating configuration.

More information on probability can be found in the following TopCoder tutorial: Understanding Probabilities. Information about expected values and the linearity of expectation can be found in any text on probability and statistics, and many texts on algorithms.

ChatExit
Used as: Division One - Level Two:
 Value 500 Submission Rate 105 / 233 (45.06%) Success Rate 52 / 105 (49.52%) High Score jdmetz for 455.96 points (9 mins 0 secs) Average Score 326.94 (for 52 correct submissions)

Problems like this are always a little funny. Tricky to solve yet easy to code. The algorithm described here simulates the chat with the provision that lower numbered people should leave as early as possible. Our simulation is made easier by the fact that message order is irrelevant between user exits. This gives rise to the following pseudcode:

```    For 1 .. (number of people)
1) Allow everyone who can write a message do so (see below).
2) Let the lowest numbered person that can leave do so.
If no person can exit, return invalid.
```
Now we explain who can write a message. If everyone in the chat room needs to see a particular person write a message, then that person is allowed to do so. Otherwise, writing a message would cause someone to see too many messages. This process is repeated until noone can write.

CultureGrowth
Used as: Division One - Level Three:
 Value 850 Submission Rate 65 / 233 (27.90%) Success Rate 35 / 65 (53.85%) High Score sean_henderson for 828.87 points (4 mins 33 secs) Average Score 661.05 (for 35 correct submissions)

Abstracting away the unnecessary details of the problem, we have a set of points and a method for generating new points. We can immediately throw out the cases with 1 point, or where the initial points are colinear, since the resulting figure will have 0 area. Otherwise, we have at least 3 non-colinear points. Making justified assumptions about how the organisms reproduce, we end up with a figure that has positive area (we either assume that the organisms each have some very small positive area, or that a particular organism could have been created after an infinite number of reproductions). This figure is precisely the convex hull of the original set of points. Finally, we return the area of this hull. The reader is directed toward the following TopCoder tutorials on geometry: Convex Hull and Polygon Area.

By brett1479
TopCoder Member