Saturday, May 27, 2006 Match summary
This match was a popular one, with 965 members participating. One reasons for the high participation may have been that this was the last SRM before the upcoming Google Code Jam Europe, so a lot of Europeans took this SRM as a training opportunity.
The ProblemsRugSizesUsed as: Division Two  Level One:
This problem was pretty straightforward as you needed to count the number of ways you can multiply two natural numbers a and b so that the result is the area. To avoid counting the same pair twice we impose that a<=b. The problem also requires that if a!=b, then a or b must be odd. This translates into the following code: public class RugSizes { public int rugCount(int area) { int res = 0; for (int a = 1; a * a <= area; a++) { if (area % a == 0) { b = area / a; if (a == b) res++; else if (a % 2 != 0  b % 2 != 0) res++; } } return res; } }MovingAvg Used as: Division Two  Level Two:
To solve this problem we need to find the average of every contiguous subsequence of k numbers in the array, find the maximum and minimum of these values and return their difference. public class MovingAvg { public double difference(int k, double[] data) { double min = 1000000, max = 1; for (int i = 0; i <= data.length  k; i++) { double sum = 0; for (int j = 0; j < k; j++) { sum += data[i + j]; } if (min > sum) min = sum; if (max < sum) max = sum; } return (max  min) / k; } }This solution has O(n * k) complexity. Other solutions in O(n) are possible. For example, when computing the sum of the next subsequence of the lenght k, one can reuse the sum of the current subsequence. It suffices to add the next element and substract the first element of the current subsequence Yet another O(n) approach would be to consider a sum array so that sum[i] = data[0] + data[1] + ... + data[i]. Using this array we can compute the sum data[i] + data[i + 1] + ... + data[j] as sum[j]  sum[i  1]. PolyMove Used as: Division Two  Level Three: Used as: Division One  Level One:
This task was a tricky one mainly due to the small numbers of examples. First let's see how do we move the vertex A from a triangle ABC such that we maximize the resulting area. The area depends on the length of the altitude from the vertex A, and on the length of the side BC. To maximize the area by moving a vertex A we need to maximize the length of the altitude. So we move A perpendicularly to the side BC and we get an increase in the area equal to BC * 1/2. The greedy approach that a lot of people took was to move every second vertex of the polygon first beginning from the first vertex of the polygon and then beginning from the second vertex. But this aproach failed on tests like the one suggested by dskloet in the forums. To solve the task correctly we needed to use dynamic programing. To make the problem linear (not circular) we must split the polygon at one point. Now we have three different cases, first we don't move the point with the index 0 or the point with index n  1, second we move the point with index 0, third we move the point with index n  1. We use the best[i] array to find the best area difference we can get by moving the points 1 .. i  1. It is obvious that best[i] = max( best[i  1], best[i  2] + distance(Point[i  2], Point[i]) / 2). public class PolyMove { double dist(long x, long y, long x1, long y1) { return Math.sqrt((x  x1) * (x  x1) + (y  y1) * ( y  y1)); } public double addedArea(int[] x, int[] y) { int n = x.length; double[] best = new double[n]; // first case best[0] = 0; best[1] = 0; for (int i = 2; i < n; i++) { best[i] = Math.max(best[i1], best[i  2] + dist(x[i2], y[i2], x[i], y[i])* 0.5); } double res = best[n  1]; //second case Arrays.fill(best, 0); best[0] = 0; best[1] = dist(x[n1], y[n1], x[1], y[1])* 0.5; best[2] = best[1]; for (int i = 3; i < n; i++) { best[i] = Math.max(best[i1], best[i  2] + dist(x[i2], y[i2], x[i], y[i])* 0.5); } res = Math.max(best[n  1], res); //third case Arrays.fill(best, 0); best[0] = dist(x[n2], y[n2], x[0], y[0])* 0.5; best[1] = best[0]; for (int i = 2; i < n  1; i++) { best[i] = Math.max(best[i1], best[i  2] + dist(x[i2], y[i2], x[i], y[i])* 0.5); } res = Math.max(best[n  2], res); return res; } }Conditional Used as: Division One  Level Two:
We will solve the problem using dynamic programming, but first we will need to find the state space. Let's try to reduce the problem to a simpler one that we can easily solve. Also let’s require to have no dice throw with the result v. Then let’s find the probability that after i throws the result will be equal to j and no dice will have the value v. We will call this probability prb[i][j]. How would we compute this probability? Well, we've reached state (i, j) of this problem from a state (i  1, j  diceValue) with a probability 1/maxSide when we threw a dice with the result diceValue, and diceValue != v. So we conclude that prb[i][j] =
(prb[i  1][j  1] + prb[i  1][j  2] + ... + prb[i  1][j  diceValue + 1] + prb[i  1][j  diceValue  1] + ... + prb[i  1][j  maxSide])/maxSide. Now that we know how to compute prb[i][j], lets think about the modified problem of finding prb1[i][j] which is the probability that from i dice throws at least one of the results was v and the sum of dice values is equal to j. We either could get in the state (i, j) from other states (i  1, j  diceValue) from this problem where diceValue is any number from 1 to maxSide, or from the state (i  1, j  v) of the previous problem. We conclude that prb1[i][j] = (prb1[i  1][j  1] + prb1[i  1][j  2] + ... + prb1[i  1][j  maxSide] + prb[i  1][j  v]) / maxSide.
public class Conditional { public double probability(int nDice, int maxSide, int v, int theSum) { double[][] prb = new double[nDice + 1][nDice * maxSide + 1], prb1 = new double[nDice + 1][nDice * maxSide + 1]; prb[0][0] = 1; double pb = 1.0/maxSide; for (int i = 0; i < nDice; i++) { for (int j = 0; j <= nDice * maxSide; j++) { if (prb[i][j] != 0  prb1[i][j] != 0) { for (int k = 1; k <= maxSide; k++) { if (k != v) { prb[i + 1][j + k] += pb * prb[i][j]; prb1[i + 1][j + k] += pb * prb1[i][j]; } else prb1[i + 1][j + k] += pb * prb[i][j] + pb * prb1[i][j]; } } } } double res = 0, res1 = 0; for (int i = 0; i <= nDice * maxSide; i++) { if (i >= theSum)res += prb1[nDice][i]; res1 += prb1[nDice][i]; } return res/res1; } }TheXGame Used as: Division One  Level Three:
This problem was a hard one and at least three of the participants with correct submissions guessed that their solution would work but did not have any proof. To solve it we have to be familiar to concepts in game theory, particularly in impartial combinatorial games.

