Match Editorial

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

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;
}

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;
}

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

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

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.

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.