Wednesday, June 29, 2005 Match summary An amazingly difficult Division 1 Easy/Division 2 Hard gave this SRM an unusual flavor. Less than onethird 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 ProblemsChatTranscriptUsed as: Division Two  Level One:
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:
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: Used as: Division One  Level One:
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. T T T U U T T T T TOur 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:
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:
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 noncolinear 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. 
