Match Editorial

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

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))
         ret++;
   return ret;
}

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)

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];
      };
   };
   Arrays.sort(names);
   for (int i = 0; i < names.length; i++) {
      String[] s = names[i].split(" ");
      names[i] = s[1] + " " + s[0];
   };
   return names;
}

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

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

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.