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.
The ProblemsStringCompareUsed as: Division Two  Level One:
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; }ClientsList Used as: Division Two  Level Two: Used as: Division One  Level One:
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 lessthanelegant, 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; }TreePlanting Used as: Division Two  Level Three:
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 n2 locations in which to plant the remaining f1 fancy trees. If we don't plant a fancy tree in the first spot, then we have n1 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 Used as: Division One  Level Two:
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 64bit 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 Used as: Division One  Level Three:
This problem was intended to involve a lot of time thinking. With lots of geometry, trig, a pseudorandom 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 bruteforce 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. 
