JOIN
 Match Editorial
SRM 318
Tuesday, August 29, 2006

## Match summary

This 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 Problems

BiggestRectangleEasy
Used as: Division Two - Level One:
 Value 250 Submission Rate 411 / 434 (94.70%) Success Rate 395 / 411 (96.11%) High Score stupidcoder for 249.62 points (1 mins 7 secs) Average Score 219.10 (for 395 correct submissions)

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 X-1 and Y+1. Its area is (X-1)*(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 non-negative number.

ReturnToHome
Used as: Division Two - Level Two:
 Value 500 Submission Rate 216 / 434 (49.77%) Success Rate 86 / 216 (39.81%) High Score v18h0r for 495.47 points (2 mins 43 secs) Average Score 289.06 (for 86 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 356 / 417 (85.37%) Success Rate 292 / 356 (82.02%) High Score reid for 247.98 points (2 mins 34 secs) Average Score 182.63 (for 292 correct submissions)

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:

• Walk directly to home (like in example 3).
• Make one jump in the direction of home and make the walk back (like in the example 1).
• Make two jumps (like in example 5).

In the second case there are also three variants:

• Walk directly to the home (the case when D > T).
• Make several jumps in the direction of home while the remaining distance will be less than D and walk the remaining distance (like in the examples 0 and 4).
• Make one jump more than in the previous variant. The covered distance will be greater than the distance from the starting point to the home and it is possible to get home using this number of jumps by moving by some arc (like in the example 2).

SimplifiedDarts
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 52 / 434 (11.98%) Success Rate 23 / 52 (44.23%) High Score gozman for 867.66 points (11 mins 27 secs) Average Score 626.76 (for 23 correct submissions)

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(i-1,j-2) + (1-p1)*get(i-1,j),
p2*get(i-1,j-3) + (1-p2)*get(i-1,j));
}

return x[N][W]*100;
}
}
```

CyclicGame
Used as: Division One - Level Two:
 Value 600 Submission Rate 135 / 417 (32.37%) Success Rate 103 / 135 (76.30%) High Score ACRush for 585.48 points (4 mins 29 secs) Average Score 414.17 (for 103 correct submissions)

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[N-1, i+1]) + : + 1/6 * (cells[i + 6] + A[N-1, 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 non-final cells using other cells as variables. The resulting linear equations set can be solved using the Gaussian elimination method.

BiggestRectangleHard
Used as: Division One - Level Three:
 Value 900 Submission Rate 104 / 417 (24.94%) Success Rate 67 / 104 (64.42%) High Score marek.cygan for 824.14 points (8 mins 47 secs) Average Score 532.85 (for 67 correct submissions)

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(i-1, l1, l2, l3, l4) or A(i-1, l1 - lengths[i], l2, l3, l4) or A(i-1, l1, l2- lengths[i], l3, l4) or A(i-1, l1, l2, l3 - lengths[i], l4) or A(i-1, 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=t-1;
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<=t-i;j++){
if (res[i][i][j][j]){
int k = i*(j);
if (k>best)
best = k;
}
}
return best;
}
}
```

By Andrew_Lazarev
TopCoder Member