Get Time
statistics_w  Match Editorial
SRM 227
Saturday, January 22, 2005

Match summary

In Division 2, Marto and valo_bg took first and second, with Dan [Popovici] in a very close third. Partway through the match, three newbies held the top three spots, but that changed before too long.

Nobody was terribly surprised in Division 1, when tomek took top honors. marian and misof were second and third, by good margins. marian deserves a lot of credit for a good fight, after working his way up to second with a dominating eight successful challenges. Also notably, RalphFurmaniak rung up six competitor's problems in the challenge round.

The Problems

StringCompare discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 232 / 236 (98.31%)
Success Rate 211 / 232 (90.95%)
High Score supernova for 249.35 points (1 mins 27 secs)
Average Score 233.43 (for 211 correct submissions)

This problem was very straightforward, and pretty much everyone used the same basic approach to solving it. Loop through the characters, starting at the beginning, until you get to the end of one or both strings (By using the min function on the lengths of the strings), incrementing a counter value whenever the characters were the same.

public int simpleDifference (String a, String b) {
   int ret = 0;
   for (int i = 0; i < Math.min(a.length(), b.length()); i++)
      if (a.charAt(i) == b.charAt(i))
   return ret;
ClientsList discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 194 / 236 (82.20%)
Success Rate 159 / 194 (81.96%)
High Score eoj for 487.18 points (4 mins 37 secs)
Average Score 353.26 (for 159 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 240 / 242 (99.17%)
Success Rate 229 / 240 (95.42%)
High Score marian for 248.24 points (2 mins 23 secs)
Average Score 223.47 (for 229 correct submissions)

This problem was again, pretty straightforward, as indicated by the fairly high success rates. However, it took a little more effort to work out a solution here. Depending upon one's level of confidence and understanding of their standard libraries, using a custom comparison method was certainly one option. However, with a fairly short list (no more than 50 total), one could afford to be very inefficient, and so a less-than-elegant, but fast to code solution was equally successful. This one passes through the list once, putting everyone's names in "Last, First" format. Then, it uses the standard sort method on the array. (In the "Last, First" format, this works just fine!) Finally, it puts everyone's names into the required "First Last" format.

public String[] dataCleanup(String[] names) {
   for (int i = 0; i < names.length; i++) {
      if (names[i].indexOf(',') > -1)
         names[i] = names[i].replaceAll(",", "");
      else {
         String[] s = names[i].split(" ");
         names[i] = s[1] + " " + s[0];
   for (int i = 0; i < names.length; i++) {
      String[] s = names[i].split(" ");
      names[i] = s[1] + " " + s[0];
   return names;
TreePlanting discuss it
Used as: Division Two - Level Three:
Value 1000
Submission Rate 94 / 236 (39.83%)
Success Rate 34 / 94 (36.17%)
High Score valo_bg for 945.04 points (6 mins 55 secs)
Average Score 607.28 (for 34 correct submissions)

Here, we need to get a little creative to come up with a workable solution. Consider placing f fancy trees along a total of n locations, so that no two are adjacent. Call our function, C, the number of ways to do this. At our first location, we can either plant a fancy tree, or not plant a fancy tree. If we plant a fancy tree, then we can't plant a fancy tree in the second spot, and hence will have n-2 locations in which to plant the remaining f-1 fancy trees. If we don't plant a fancy tree in the first spot, then we have n-1 locations in which to place all f fancy trees. This gives us our recursive formula, C(n, f) = C(n - 2, f - 1) + C(n - 1, f). Our starting values are of course, C(1, 1) = 1, and C(0, 0) = 1.

However, with the problem constraints as they are, a simple recursive function by itself is not sufficient. We either need to implement memoization, whereby we store the values of previous recursive calls, to avoid recalculating them repeatedly, or we can use dynamic programming, as shown here:

public long countArrangements(int total, int fancy) {
   long[][] count = new long[total + 1][fancy + 1];
   count[0][0] = 1;
   count[1][1] = 1;
   for (int i = 0; i < = total; i++) 
      for (int j = 0; j < = fancy; j++) {
         if (i > 0)
            count[i][j] += count[i - 1][j];
         if (i > 1 && j > 0)
            count[i][j] += count[i - 2][j - 1];
   return count[total][fancy];
TreeSpreading discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 178 / 242 (73.55%)
Success Rate 83 / 178 (46.63%)
High Score Per for 488.70 points (4 mins 20 secs)
Average Score 375.10 (for 83 correct submissions)

This problem was homologous to the division 2 hard problem, but with the twist that there are now four different kinds of trees, none of which can be next to another of the same variety. So, unlike it's division 2 counterpart, the proper recursion (or more typically, DP model) was not as obvious. As an interesting side note, the presence of four types of trees also makes the number of possible arrangements increase much faster than with only two types of trees. The constraints, of no more than ten of each kind of tree, may seem low, but were actually in place to avoid overflowing a 64-bit signed integer value.

What we need to keep track of programmatically as we solve this is the number of each kind of tree planted so far, and the type of the last tree that was planted. This way, we know what type of tree we cannot plant next. A simple recursion with memoization is plenty fast enough for this problem, but some might argue that a DP solution is a bit cleaner.

public long countArrangements(int a, int b, int c, int d) {
  if (a == 0 && b == 0 && c == 0 && d == 0)
    return 1;
  long[][][][][] count = new long[21][21][21][21][4];
  count[1][0][0][0][0] = 1;
  count[0][1][0][0][1] = 1;
  count[0][0][1][0][2] = 1;
  count[0][0][0][1][3] = 1;
  for (int w = 0; w < = 20; w++)
    for (int x = 0; x < = 20; x++)
      for (int y = 0; y < = 20; y++)
        for (int z = 0; z < = 20; z++) 
          for (int i = 0; i < = 3; i++) {
            if (w > 0 && i != 0)
              count[w][x][y][z][0] += count[w - 1][x][y][z][i];
            if (x > 0 && i != 1)
              count[w][x][y][z][1] += count[w][x - 1][y][z][i];
            if (y > 0 && i != 2)
              count[w][x][y][z][2] += count[w][x][y - 1][z][i];
            if (z > 0 && i != 3)
              count[w][x][y][z][3] += count[w][x][y][z - 1][i];
  return count[a][b][c][d][0] + count[a][b][c][d][1] + count[a][b][c][d][2] + count[a][b][c][d][3];
QuadrilateralSearch discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 83 / 242 (34.30%)
Success Rate 26 / 83 (31.33%)
High Score misof for 831.12 points (13 mins 22 secs)
Average Score 533.14 (for 26 correct submissions)

This problem was intended to involve a lot of time thinking. With lots of geometry, trig, a pseudo-random generator function, and constraints large enough to make timeout a very real problem, there was plenty to consider in formulating a solution. As it turned out, a few types of solutions actually worked for this. The most typical method was to determine the x and y coordinates of the red points, and use the Sum(xi * yj - xj * yi) method of calculating the area of the polygon, and after brute-force choosing the first three points, pick the best fourth point. With a reasonably efficient code base, this worked out.

The originally devised solution for this, although much less obvious at first, is to brute force consider every pair of points as being a diagonal of the quadrilateral. Then, one can quickly find (by binary search) the "furthest away" points on each side of the diagonal. That is, the point closest to midway between the two points of the diagonal. Why is this the largest? I'll leave a formal proof as an exercise to the reader, but to put it simply, the diagonal divides the quadrilateral into two triangles, and each triangle's area is maximized when the third point is as far away from the diagonal as possible.

To calculate the area in a way other than the usual polynomial area function, one has to take advantage of the fact that the quadrilateral is cyclic (inscribed in a circle). The four points create four arcs, proportional to the difference in the indices of the two points. For instance, with n = 360, points 2 and 20 would be exactly 18 degrees apart. Now, imagine lines drawn from the center of the circle to the four points. This creates four triangles, and the angles in the center are exactly the same as the degree measures of the arc lengths. The area of one of these triangles, where t is the angle in the center of the circle is then given by (d/2 * cos(t/2)) * (d/2 * sin(t/2)). Remembering the double angle formula for the sin function, this reduces to d^2 * sin(t) / 8. If we first cache the values of this for each possible t (of which there are at most 500 choose 2, or roughly 125,000), then this is fairly efficient.

As another interesting note, the above method of calculating area offers a proof that the largest possible area of an inscribed quadrilateral is, in fact, a square.

By timmac
TopCoder Member