Tuesday, August 29, 2006 Match summaryThis SRM was the last chance to test coding skills before the TCCC. In a tight contest, first place in Division 1 went to tmyklebu with the very high score of 1622.05 points. Second and third went to benetin and reid respectively. The Division 2 winner was Triple_M followed by gozman and vpj. The ProblemsBiggestRectangleEasyUsed as: Division Two  Level One:
If one of the sides of the rectangle is known and equal to X, the other side can be easily found by the formula (N  2 * X) / 2, which gives the biggest size of the side is possible to achieve using remaining sticks. The problem constraints allow you to iterate through all possible sizes of the one side. Using the formula above it is possible to calculate the size of another side and area of the rectangle. The answer is the biggest area we have. However, it is possible to find the answer without iterating. If one of the sides of the optimal rectangle is N / 4, the other can be found using the formula above. This follows from the fact that sizes of the sides should be as close as possible. Let's consider a rectangle with sides X and Y where X ≤ Y. Let's consider another rectangle with the same perimeter and sizes X1 and Y+1. Its area is (X1)*(Y+1) = X*Y  (Y  X)  1. The resulting area is smaller than the area of the original rectangle X*Y since "Y  X" is a nonnegative number. ReturnToHomeUsed as: Division Two  Level Two: Used as: Division One  Level One:
This problem can be solved by trying all possible ways to get home and choosing the optimal. There are two principle cases: when the starting point is in the radius of one jump from home and when it is not. In the first case there are three variants to get home:
In the second case there are also three variants:
Used as: Division Two  Level Three:
Let A(N, W) be the probability to win if N throws remained and it is required to get W points. To calculate A(N, W) it is necessary to choose the distance to throw the dart. Throwing from the short distance will give P1*A(N  1, W  2) + (1  P1)*A(N  1, W) probability to win. Throwing from the long distance will give P2*A(N  1, W  3) + (1  P2)*A(N  1, W) probability to win. A(N, W) is the maximum of the probability for the short and the long distance. Here is the sample solution by gozman. public class SimplifiedDarts { double[][] x; private double get(int i, int j) { if (j < 0) return x[i][0]; else return x[i][j]; } public double tryToWin(int W, int N, int P1, int P2) { x = new double[N+1][W+1]; double p1 = 0.01 * P1; double p2 = 0.01 * P2; for (int i=0; i<=N; i++) x[i][0] = 1; for (int i=1; i<=W; i++) x[0][i] = 0; for (int i=1; i<=N; i++) for (int j=1; j<=W; j++) { x[i][j] = Math.max(p1*get(i1,j2) + (1p1)*get(i1,j), p2*get(i1,j3) + (1p2)*get(i1,j)); } return x[N][W]*100; } }CyclicGame Used as: Division One  Level Two:
The simplest way to solve the problem is to simulate the process. Let A(N, i) be the expectation of the bank if the current position is cell i and not more than N throws of the dice is left. To calculate A(N, i) it is necessary to take the best of two ways: to end the game or to throw the dice. In the first case A(N, i) is equal to zero. In the second case A(N, i) can be calculated using the following formula: 1/6 * (cells[i+1] + A[N1, i+1]) + : + 1/6 * (cells[i + 6] + A[N1, i + 6]). There is another more accurate  but more difficult in implementation way to solve this problem. If the current position is i, the decision to end the game or throw the dice does not depend on the bank. Let's call the cells where the game should be ended as final cells. Let's iterate through all possible values of the set of final cells. If the set of final cells is fixed, it is possible to write an equation for all nonfinal cells using other cells as variables. The resulting linear equations set can be solved using the Gaussian elimination method. BiggestRectangleHardUsed as: Division One  Level Three:
This task can be solved using dynamic programming. Let A(i, l1, l2, l3, l4) be true if using first i elements of lengths is possible to create four segments with lengths l1, l2, l3, l4 correspondingly. A(i, l1, l2, l3, l4) can be calculated using the following formula: A(i, l1, l2, l3, l4) = A(i1, l1, l2, l3, l4) or A(i1, l1  lengths[i], l2, l3, l4) or A(i1, l1, l2 lengths[i], l3, l4) or A(i1, l1, l2, l3  lengths[i], l4) or A(i1, l1, l2, l3, l4 lengths[i]). The answer is the biggest l1*l3 among all the positive values of A for which l1=l2 and l3=l4. Clearly if the one side of the resulting rectangle is more than 40, the other side is less than 40. This fact allows to reduce the amount of memory required to solve the problem. Here is the sample solution by Vitaliy: public class BiggestRectangleHard{ public int findArea(int[] ll){ int s = 0; for(int i = 0; i<ll.length;i++) s+=ll[i]; int t = s/2; int t1= t/2; int t2=t1; int n =ll.length; boolean[][][][] res = new boolean[t1+1][t1+1][t2+1][t2+1]; res[0][0][0][0]=true; for(int nn = 0;nn<n;nn++) for(int i = t1;i>=0;i) for(int j= t1; j>=0;j) for(int k=t2;k>=0;k) for(int l=t2;l>=0;l) if (res[i][j][k][l]){ if (i+ll[nn]<=t1) res[i+ll[nn]][j][k][l] = true; if (j+ll[nn]<=t1) res[i][j+ll[nn]][k][l] = true; if (k+ll[nn]<=t2) res[i][j][k+ll[nn]][l] = true; if (l+ll[nn]<=t2) res[i][j][k][l+ll[nn]] = true; } int best = 1; for(int i = 1;i<=t1;i++) for(int j=1;j<=ti;j++){ if (res[i][i][j][j]){ int k = i*(j); if (k>best) best = k; } } return best; } } 
