Match Editorial

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

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.

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)

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).

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

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.

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