SRM 579

Match Summary

Round Overview
Discuss this match

This match was more accessible than usual with high submission and success rates across both divisions. It was still not easy to shine and win the top places though. Only three coders in division 1 could solve the great hard problem, by ir5, that required some creative usage of probability knowledge. Of them, only two coders solved all three problems. Such a solid performance, in addition to successful challenges brought Petr the division win. cgy4ever got the second place. lyrically got the third place, and bmerry the fourth. Also congratulations to the division 2 winner: niklasb.

PrimalUnlicensedCreatures

Used as: Division Two - Level One:

In this problem, we can always pick any of the creatures that can be defeated. After fighting one of them, our creature’s power level can only increase. So this will not make us unable to beat any other creature.

We can repeat the following logic: Find a creature that has not been defeated yet and has a low enough power level for our creature to defeat. Defeat it, and increase the power level of our creature. Repeat until we can no longer find any creature that can be defeated. Because of the first paragraph, this simulation will always find the maximum number of defeated creatures.

However, to simplify the code, we may still sort the creatures in non-decreasing power level order. If we face creatures in this order, we can easily tell when to stop. When you face creature i, you can assume all creatures with a smaller power level were already defeated. If your power level is still not high enough, there is no way to defeat this creature, and we can stop. Else we can defeat the creature, update the power level and continue with the next one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxWins(int level, vector < int > grezPower) {
  //Sort their power levels:
  sort(grezPower.begin(), grezPower.end());
  int i = 0;
  while (i < grezPower.size()) {
    if (grezPower[i] < level) {
      // defeat it:
      level += grezPower[i] / 2;
      i++;
    } else {
      break;
    }
  }
  // i is as large as the number of defeated creatures:
  return i;
}

UndoHistory

Used as: Division Two - Level Two:

Used as: Division One - Level One:

Understanding the problem

Some problems have heavy problem statements. It is best to make sure to understand them correctly before trying to solve them. A formal way to explain the problem:

• UndoHistory is a set of strings, initially contains “”.

• results list of strings, initially empty.

• buffer a string, initially “”

There are three operations available:

• Enter: Append buffer to results. (Costs 1).

• Type: Append any letter to buffer. UndoHistory = UndoHistory U {buffer}. (Add the new contents of the buffer to UndoHistory. (Costs 1)

• Restore: buffer = (Pick any element of UndoHistory). (Costs 2). This replaces the contents of the buffer. If it appended contents to the buffer, even some of the examples would be impossible (How to empty the buffer without replacing it with “” from the history?).

The objective is to make results = lines (as given by the input) using the minimum cost possible.

The first line

Typing the first line is straight-forward. We can just type all of the needed letters. There is no reason to use the UndoHistory. Then press enter. In total, we need length(**lines[**0])+1.

The second line

It may now be better to restore from the undo history.

The key is to notice that in order to type the first line. Each of the prefixes of lines[0] were at one point or another added to the undo history. We can restore any prefix of lines[0] with a cost equal to 2. If we find that any of these prefixes is also a prefix of lines[1], then we may restore it, complete the remaining characters of line[1] and press enter.

It may also be possible that lines[0] is a prefix of lines[1], in that case it is possible to type the remaining characters of lines[1] and then press enter. For this case only, if this is possible, it is always less expensive to do this.

The solution is then, to check if lines[0] is a prefix of lines[1], if it is , complete it. Else find any prefix of lines[0] that is in the history (Including “”) if it is a common prefix of lines[1], we can restore it and complete it. Pick the prefix that gives the best result.

Any other line

We can actually generalize the logic. When writing lines[i], we can assume that each of the previous lines were written. This means that each of their prefixes were added to the undo history one way or another. (Even if we restored from the history to type a line, it still holds true that each of its prefixes exist in the undo history). Thus we can restore any prefix of any of the past lines with a cost equal to 2.

If lines[i-1] is a prefix of lines[i], we can continue typing without restoring from the undo history. However, it is important to notice that this is not necessarily better than the alternative. There may be a string in the UndoHistory that would yield a better result than using lines[i-1]. Because this time many of the previous lines could be longer than lines[i-1]. An extreme example would be the case where lines[i] is already in the UndoHistory, it would take 3 button presses to type it.

Solution

The solution is to, in each step, simulate all of the alternatives. Make no assumptions and just simulate them all and always pick the alternative that yields the smallest cost. The alternatives could be to restore something from the undo history (Containing all of the prefixes of all the past lines) and the other alternative is to , if possible, continue typing. For the first alternative, we can always restore the largest common prefix between the current line and a past line.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int minPresses(vector < string > lines) {
  int cost = lines[0].size() + 1;
  for (int i = 1; i < lines.size(); i++) {
    int icost = 1000000000; //A large number

    for (int j = 0; j < i; j++) {
      int k = 0;
      while (k < lines[i].size() && k < lines[j].size()) {
        if (lines[i][k] == lines[j][k]) {
          k++;
        } else {
          break;
        }
      }
      // k is the length of the largest common prefix between lines[i] and lines[j]
      int ijcost = 2 + (lines[i].size() - k) + 1;
      if (j == i - 1 && k == lines[j].size()) {
        // lines[j] is a prefix of lines[i], then there is a cost to continue
        // typing lines[i] equal to (lines[i].size() - k) + 1, same as subtracting
        // 2 from ijcost:
        ijcost -= 2;
      }
      icost = std::min < int > (icost, ijcost);

    }
    cost += icost;
  }
  return cost;
}

MarblePositioning

Used as: Division Two - Level Three:

All permutations

The solution can be split in two parts: First we can decide the order in which we place the circles. The second part is to decide the minimum distance between the leftmost and rightmost circle, without overlap.

For the first part, the images in the examples should tell us that there seems not to be a simple logic that can tell easily us what the best order is. But the number of circles will be small. There are at most 8! = 40320 different permutations of circles to try. We can generate all these permutations and find, for each of them, the minimum distance between the left-most and right-most circle. In order to generate all the permutations we can use backtracking. Although it is also possible to generate all permutations iteratively and C++ even has a next_permutation function.

Minimum width

For a fixed order of circles, find the minimum distance. Place the left-most circle in position 0. Start considering the version with only two circles: We need to place circle 1 in such a position greater than 0 and in such a way that circle 1 and 0 do not overlap. In addition making the distance between their points as small as possible.

We put the circles so close to each other that the exact distance between their centers is now (r0+r1). We can actually tell that circle 0’s center is (p0, r0) part of circle 1’s center is unknown (p1, r1). We can try an equation to find (p1-p0) using Euclidean distance as a starting point:

r0 + r1        = sqrt( (p1 - p0)^2 + (r1 - r0)^2 )
(r0 + r1)^2 = (p1 - p0)^2 + (r1 - r0)^2
(p1 - p0)^2 = (r0 + r1)^2 - (r1 - r0)^2
(p1 - p0)^2 = r0^2 + 2*r0*r1 + r1^2 - r0^2 + 2*r0*r1 - r1^2
(p1 - p0)^2 = 4 * r0 * r1
p1 - p0)       = 2 * sqrt( r0 * r1 )

The minimum distance between the two circles is 2 * sqrt(r0 * r1).

When there are 3 circles. We can assume that we first found the minimum distance between the first two circles. There are two cases:

In this case, the new circle touches circle 1.

In this one, the new circle touches circle 0. It may also be possible that the new circle touches both circle 0 and 1. In any case, there should be at least one circle that touches the new circle. We can generalize: For each of the circles with a smaller index, we can find the minimum distance to place the new circle without overlaps. The maximum of these distances will be the result.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int n = 0;
double[] radius;

// Given the radiuses in a fixed order, find the minimum
// p[n-1] - p[0]:
double minWidth() {
  double[] p = new double[n];
  // Place the first marble on point 0.0:
  p[0] = 0.0;
  for (int i = 1; i < n; i++) {
    // Decide where to place marble i:
    p[i] = 0;
    for (int j = 0; j < i; j++) {
      double dis = p[j] + 2 * Math.sqrt(radius[i] * radius[j]);
      // Dis is the minimum distance where we can place i
      // without overlaping with j.
      p[i] = Math.max(p[i], dis);
      // The maximum of all the distances is the best place
      // for p[i]
    }
  }
  return p[n - 1] - p[0];
}

// Use backtracking to generate each of the permutations of
// the original radius array:
void rec(int p) {
  if (p == n) {
    // Remember the permutation with the best result:
    best = Math.min(best, minWidth());
  } else {
    // Decide the radius for position p.
    // We have already decided the smaller positions,
    // so we need to pick a radius from indices >= p:
    double radp = radius[p];
    for (int i = p; i < n; i++) {
      // Swap radius[p] and radius[i]
      radius[p] = radius[i];
      radius[i] = radp;

      // Step in the recursion:
      rec(p + 1);

      // Restore radius[i]
      radius[i] = radius[p];
    }
    radius[p] = radp
  }
}

public double totalWidth(int[] radius) {
  n = radius.length;
  this.radius = new double[i];
  for (int i = 0; i < n; i++) {
    this.radius = (double) radius[i];
  }
  // Start backtracking:
  rec(0);
  return best;
}

TravellingPurchasingMan

Used as: Division One - Level Two:

Travelling salesman

Let us go with a similar problem (so similar, even the name of the problem is quite close). In this version of the problem, the stores are always open. In this version, it is always possible to buy all the products (assuming all stores are reachable) so let us try the minimum time before buying all products. This is quite close to the Travelling salesman problem.

The main differences is that we need to only visit some stores in which buying a product also takes time. We can simplify the problem by reducing it to a problem that has only store N-1 and the interesting stores. The travel distance between two interesting stores can be calculated as the minimum travel distance (direct or indirect) between the stores from the original problem. To calculate these distances we can use any shortest paths algorithm. We will use Floyd-Warshall because the constraints are low and it can be implemented in few lines. After this change, there is no reason to move from a store to another if you do not plan to buy a product from that store.

Describe the state as (x, mask): x is the current store position and mask is a bitmask representing the set of stores from which you already made a purchase. You are at score x, if you decide to move to store y, it would be because you plan to buy the product at y. Moving between x and y takes as many time as the travel time between the stores. Once you reach store y, you make the purchase taking DURATION time. In total, there is a cost to move from (x, mask) to (y, mask | (1<<y).

The result is the minimum time needed to move from (N-1, 0) to (z, 1111…1), for any z. This makes the problem exactly like travelling salesman.

Closed stores

Let us now include the closing time into the problem. Assume all stores are open at time 0, but each store has a closing time. It may no longer be possible to buy from all reachable stores, because time spent in reaching a store and buying a product may make you unable to buy in other stores.

This makes the time at which you arrive to node (x, mask) important. If the current time is t, and moving to store y makes the time increase to a value higher than the store’s closing time, we will not be able to buy the product anymore. If it is so late that it is impossible to buy y’s product, it is better not to even go there, we can make it so there is no edge between (x, mask) and (y, mask | (1<<y) ) depending on the current time.

Let t be the minimum time needed to reach state (x, mask), if at this time it is impossible to move from (x, mask) to (y, mask | (1<<y) ), it will never be possible. Thanks to this we only need to know the minimum time to reach state (x, mask) and it determines the edges to other states. As long as we find the minimum time of the closest states, the rest is still about finding the minimum paths. The other difference is with maximizing the number of purchases. We need to find a state (y, mask2) such that there is a path between (x, mask) and a (y, mask2) and mask2 has as many elements as possible.

Open time

Once we add the open time we have a different issue. The time at which you arrive to a store may be too early and we cannot make the purchase before it opens. However, we can just wait some time until the opening time and then make the purchase, thus we can just consider this as an addition to the purchase duration. We arrive to (x, mask) at time t and the distance between x and y was w seconds. If t + w is less than or equal to the closing time, then it is possible to make the purchase. However, if t + w is less than the opening time, we need to wait up until that time. The minimum time to arrive (y, mask|(1<<y)) will be max(t + w, OPEN_TIME ) + DURATION.

A fast enough solution

Although we have successfully reduced the problem to shortest paths, we need to be careful about the time. There are at most 16 interesting stores, this means there are 2¹⁶ different values for mask and at most 17 values for x(N-1 could be a store that is not interesting). This yields an upper bound for the number of vertices equal to 172¹⁶. The number of edges is smaller, for each vertex, there are at most 16 choices for other stores to visit. 1617*2¹⁶ edges may be too large for some Dijkstra implementations, the good news is that we can use a dynamic programming logic instead.

We will move iteratively in increasing order of the mask. We know that the first state is (N-2, 0). From it we can find the minimum costs of all states that have exactly one purchased product. Then for each (i, mask), we can find new costs for some states (j, mask | (1<<j) ) that will have a larger bit mask.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
final int INF = 1000000000;
int[] distance;
public int maxStores(int n, String[] interestingStores, String[] roads) {
  // Initial distance between any two stores (relevant or not):
  int[][] dist = new int[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dist[i][j] = INF;
    }
    dist[i][i] = 0;
  }
  // Use the roads to fill that distance array:
  for (int i = 0; i < roads.length; i++) {
    String[] s = roads[i].split(" ");
    int u = Integer.parseInt(s[0]);
    int v = Integer.parseInt(s[1]);
    int d = Integer.parseInt(s[2]);
    dist[u][v] = dist[v][u] = Math.min(dist[v][u], d);
  }
  //Floyd-Warshall:
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  // Let us make the new problem that only contains the interesting stores
  // and store N-1 (May or may not be interesting):
  int m = interestingStores.length;
  int[] open = new int[m + 1];
  int[] close = new int[m + 1];
  int[] duration = new int[m + 1];
  int[] storeId = new int[m + 1];
  int[] store = new int[n];
  Arrays.fill(store, 0, n, -1);
  for (int i = 0; i < m; i++) {
    String[] x = interestingStores[i].split(" ");
    int s = i;
    store[s] = i;
    open[i] = Integer.parseInt(x[0]);
    close[i] = Integer.parseInt(x[1]);
    duration[i] = Integer.parseInt(x[2]);
    storeId[i] = s;
  }
  int maskLimit = (1 << m);
  // Add store n-1 in case it was not interesting. Let us make it a interesting
  // store that is permanently closed.
  if (store[n - 1] == -1) {
    storeId[m] = n - 1;
    store[n - 1] = m;
    open[m] = -2;
    close[m] = -1;
    duration[m] = 0;
    m++;
  }
  //distance[mask * m + x] holds the minimum time needed to reach state (x,mask)
  distance = new int[maskLimit * m];
  Arrays.fill(distance, 0, m * maskLimit, INF);
  // At time 0, we start at store (n-1) and no purchases were made.
  distance[0 * m + store[n - 1]] = 0;

  // update the distance array in increasing order of masks:        
  for (int mask = 0; mask < maskLimit; mask++) {
    for (int x = 0; x < m; x++) {
      if (distance[mask * m + s] < INF) {
        int t = distance[mask * m + x];
        // We decide to move to store nx:
        for (int nx = 0; nx < m; nx++) {
          // If we move to store nx, it is because we want to make
          // the purchase. 
          // Time necessary to move:
          int nt = t + dist[storeId[x]][storeId[nx]];
          if (nt <= close[nx]) { //If the store would not be closed:
            // After arriving, we may need to wait until the store
            // opens. Then we need duration[nx] time to make the purchase:
            nt = Math.max(nt, open[nx]) + duration[nx];
            int nmask = mask | (1 << nx);
            int nnode = nmask * m + nx;
            // Update the distance:
            if (distance[nnode] > nt) {
              distance[nnode] = nt;
            }
          }
        }
      }
    }
  }
  // Find the mask that has the best number of purchases and is reachable:
  int res = 0;
  for (int j = 0; j < maskLimit; j++) {
    // Count the number of bits:
    int c = 0;
    for (int i = 0; i < m; i++) {
      if ((j & (1 << i)) != 0) {
        c++;
      }
    }
    for (int i = 0; i < m; i++) {
      if (distance[j * m + i] != INF) {
        res = Math.max(res, c);
      }
    }
  }
  return res;

}

RockPaperScissors

Used as: Division One - Level Three:

The strategy

In the top level, the problem involves the following logic: At each turn, you will remember a list of the results so far: E.g: (Rock - Scissors - Scissors - Rock - Paper - … ). Based on the past results, you need to find out the probability of the next die result being Rock, Scissors or Paper. We will call these P(Rock), P(Scissors), P(Paper)

If you pick your play to be “Paper”, the expected score would be: 3*P(Rock) + 1*P(Paper). Because there is a P(Rock) probability you will earn 3 points and a P(Paper) probability for a tie. Similarly, playing scissors has an expected score of ( 3*P(Paper) + P(Scissors) ) and playing rock yields (3*P(Scissors) + P(Rock) ). The best decision is the one that has the best expected score, if we follow this decision in every turn, the expected total score will be maximized.

Past results

The strategy is currently based on the sequence of past results. The problem is that with n <= 50, there are far too many possible different such sequences. The work around involves to notice that the probabilities P(Rock), P(Scissors) and P(Paper) are based on the probability that each die would be picked in the next turn.

P(Rock) = Sum( For each die i, P( Die i is picked in the next throw) * P(Throwing Die i yields Rock) )

Initially, the probabilities to pick each die are 1/n. These probabilities will change after a sequence of moves. Depending on the results so far, some dice could be more likely than others.

A key observation is that, given a sequence of past results, the actual order of the results does not change the probabilities that each die that could still be inside the bag. For example, consider the results sequences : Rock-Rock-Scissors and Scissors-Rock-Rock. Each combination of 3 dice that can give the first result can also give the second result. Thanks to this observation, we only need to remember the number of Rock, Scissors and Paper results we have seen. We will call these numbers r, s and p, respectively.

Expected turn probability

There are O(n3) triples (r, s, p). We could make a solution based on recursion: F(r, s, p) gives us the expected score after we have seen a total of r rocks, s scissors and p papers. There is another approach though that works nicer in this problem. Note that your decision only has an effect on your score, but it does not have an effect on which dies are thrown and what face they show. The expected value is a linear map. The expected total score is equal to the expected score for each turn.

It is turn #m, there were m turns before and each turn yielded a result. This means that r + s + p = m. There is a probability P(r, s, p) that the number of results for each gesture were (r, s, p). The expected score for the m-th turn is:

E(m-th turn) = Sum( For each (r, s, p = m), P(r,s,p)*Score(r,s,p))

Score(r,s,p) is the expected score when the past results where (r,s,p). We need to find P(Rock | (r,s,p)), P(Scissors | (r,s,p)) and P(Paper | (r,s,p)), the conditional probability the next dice yields each of the gestures assuming the past results were ( r,s,p). Then we pick the best result: 3*(something) + 1*(something else).

The gesture probabilities depend on the remaining dice. Each die will have a conditional probability to be picked: P(Die i | (r,s,p)). For example:

P(Rock | (r,s,p)) = Sum(for each die i, P(Die i | (r,s,p)) * P(Die i rolls Rock) )

There are currently two probabilities that we need to know how to calculate: P(r,s,p) and P(Die i | (r,s,p)).

Die probability

One method is to think: What is the probability that die i is still in the bag? P(i in bag | (r,s,p)). There should be (n - r - s - p) dies in the bag. The probability that die i will be picked is then: P(i in bag | (r,s,p)) | (n - r - s - p).

Consider the probability for the event ( (r,s,p) AND (die i is not picked ) ), we will call it P(i,r,s,p), this is the total probability that the die is in the bag AND (r,s,p). By the definition of conditional probability:

P( Die i is in the bag | (r,s,p) ) = P(Die in the bag AND (r,s,p)) / P(r,s,p)
                                                = P(i,r,s,p) / P(r,s,p)

Another method is with Bayes’ theorem:

P(Die i | (r,s,p)) = ( P( (r,s,p) | Die i) * P(Die i) ) / P(r,s,p)

It does need a work in interpretation P(Dice i), is the probability Die i is picked in the m-th turn this is 1 / (n - r-s-p), because that is the number of remaining dice. P( (r,s,p) | Die i) is the probability (r,s,p) were the results before m-th turn given that Die i is picked next. This is the same as the probability to pick (r,s,p) without using Die i = P(i,r,s,p). Using both methods, the result is the same:

P(Die i | (r,s,p)) = ( P(i,r,s,p) / P(r,s,p) ) / (n - r-s-p)

Getting rid of P(r,s,p)

Instead of calculating P(r,s,p) we will show we do not need to calculate it. This is a interesting although not very significant simplification. Remember that the objective is to find the expected score for the m-th turn:

Sum( For each (r+s+p = m) : P(r,s,p) * Score(r,s,p) )

Score(r,s,p) is equal to 3*(a probability) + 1*(another probability). The probabilities are in the form:

P(die i | (r,s,p)) = (P(i,r,s,p) / P(r,s,p)) / (n-r-s-p)
P(Rock | (r,s,p)) = Sum(For each die i : P(die i | (r,s,p)) * P(die i rolls Rock) )

Therefore, Score(r,s,p) is equal to a number divided by P(r,s,p), since we calculate the product P(r,s,p) * Score(r,s,p) we can just eliminate P(r,s,p).

P’(die i | (r,s,p)) = P(i,r,s,p) / (n-r-s-p)

P’(Rock | (r,s,p)) = Sum(For each die i : P’(die i | (r,s,p)) * P(die i rolls Rock) )
P’(Scissors | (r,s,p)) = Sum(For each die i : P’(die i | (r,s,p)) * P(die i rolls Scissors) )
P’(Paper | (r,s,p)) = Sum(For each die i : P’(die i | (r,s,p)) * P(die i rolls Paper) )

Score’(r,s,p) = max( 3P’(Rock | (r,s,p)) + P’(Paper | (r,s,p))
                                3P’(Scissors | (r,s,p)) + P’(Rock | (r,s,p))
                                3*P’(Paper | (r,s,p)) + P’(Scissors | (r,s,p)) )

Calculating P(i,r,s,p)

We can use dynamic programming. Let f( t, i,r,s,p) be the probability to pick r rocks, s scissors and p papers in (r+s+p) without picking die i, when considering only the first t dice.

• For t = 0, there are no dice, whenever r+s+p = 0, the probability is exactly 1.0 else it is 0.0. This is the base case.

• For t > 0. We can consider die #(t-1). We are calculating probability based on (r+s+p) picks and there are t dies available. The probability die (t-1) will be picked in any of these throws is (r+s+p) / t. If the die is picked, there is a probability it will roll a Rock, Scissors or Paper. For example, If rock is picked, then we need to calculate f( t-1, i, r-1,s,p) to find the probability the rest works out. If the die is not picked then we need to calculate f(t-1, i, r,s,p). An exceptional case is when i=t-1. In this case, we need to ignore the case where the die is picked.

In total we will need O(1) calculations for each of the O(n⁵) possible states for the function. An issue is that naively implementing the O(n⁵) states of the dynamic programming needs around 2.5 GB of memory (TopCoder has a 64MB limit). We still have work to do.

In less memory

For the main solution, we do not need to remember all O(n⁵) states of the function. We only need those where t = n (To consider all the dice available) . Each state is dependent on cases states with smaller (r+s+p) or with identical (r,s,p). It is possible to implement the dynamic programming using only O(n⁴) memory. See the code for more details.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
double P[50][51][51][51]; // P[x][r][s][p]
// probability to get  r rocks, s scissors and p papers
// without throwing die #x.

// This array is barely behind the memory limit:
// 50*51*51*51*8 bytes ~= 50.60 MB

double bestScore(vector < int > rockProb, vector < int > paperProb, vector < int > scissorsProb) {
  int n = rockProb.size();
  memset(P, 0, sizeof(P));
  for (int i = 0; i < n; i++) {
    P[i][0][0][0] = 1.0; //Base case. The other cases for t=0 are 0.0
    // We are calculating f(t,i,r,s,p):
    for (int t = 1; t <= n; t++) {
      // Initially, P[i][r][s][p] contains the results for (t-1)
      // As we update P[i][r][s][p] with results for (t), we
      // need to do it in an order that does not override a
      // result for (t-1) that we might still need later
      for (int m = t; m >= 0; m--) {
        // Each state depends on those with smaller m
        // or identical (r,s,p). So we update in decreasing order of m:
        for (int r = 0; r <= m; r++) {
          for (int s = 0; s + r <= m; s++) {
            int p = m - s - r;
            // Probability die t-1 is picked:
            double q = m / (double) t;
            double qr = rockProb[t - 1] / 300.0;
            double qs = scissorsProb[t - 1] / 300.0;
            double qp = paperProb[t - 1] / 300.0;

            double sum = 0;
            if (r > 0) {
              // Since r-1+s+p < r+s+p, then P[i][r-1][s][p] currently
              // holds the result for f(t-1, i, r-1,s,p)
              sum += qr * P[i][r - 1][s][p];
            }
            if (s > 0) {
              sum += qs * P[i][r][s - 1][p];
            }
            if (p > 0) {
              sum += qp * P[i][r][s][p - 1];
            }
            // Note that P[i][r][s][p] currently holds f(t-1,i,r,s,p):
            if (i == t - 1) {
              // Die t-1 is the one to ignore. Ignore its pick:
              P[i][r][s][p] = (1 - q) * P[i][r][s][p];
            } else {
              P[i][r][s][p] = q * sum + (1 - q) * P[i][r][s][p];
            }
          }
        }
      }
    }
  }
  double res = 0;

  for (int m = n - 1; m >= 0; m--) {
    // How many points can you expect at the m-th throw?
    for (int r = 0; r <= m; r++) {
      for (int s = 0; s + r <= m; s++) {
        // Score'(r,s,p) = 
        int p = m - s - r;
        double prock = 0;
        double pscissors = 0;
        double ppaper = 0;
        for (int i = 0; i < n; i++) {
          // Probability to pick die i:
          double cond = P[i][r][s][p] / (n - m);
          // Add to the rock, scissors and paper probabilities:
          prock += cond * rockProb[i] / 300.0;
          pscissors += cond * scissorsProb[i] / 300.0;
          ppaper += cond * paperProb[i] / 300.0;
        }
        // = Best  of:
        double x[3] = {
          3 * prock + ppaper,
          3 * pscissors + prock,
          3 * ppaper + pscissors
        };
        res += * max_element(x, x + 3); // Pick the maximum value:
      }
    }

  }
  return res;
}