SRM 656

Match Summary

Round Overview
Discuss this match

CorruptedMessage

There are 26 options for the lower case letter that makes the whole message. What we can do is try each letter ch and count the number of characters that are different to ch in the input. If the number of different characters is K, then we are alowed to say that a string of n times the ch letter is a possible result. We can print any of those results.

It is worth nothing that the letter in question might not appear in the input string, like in example 1).

In languages like Java or c++ , the characters behave as/are integers and we can do a loop from ‘a’ to ‘z’:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string reconstructMessage(string s, int k) {
  char res = 'z';
  // if the result is none of those between a and y, then return z:
  for (char ch = 'a'; ch <= 'y'; ch++) {
    // count differences:
    int d = 0;
    for (char x: s) {
      if (x != ch) {
        d++;
      }
    }
    if (d == k) {
      res = ch; //match
    }
  }
  // make string of s.size() result characters:
  return string(s.size(), res);
}

Or you may have to convert between characters and integers and back. Like in this python solution:

1
2
3
4
5
6
7
8
class CorruptedMessage:
  def reconstructMessage(self, s, k):
  for i in range(ord('a'), ord('z') + 1):
  ch = chr(i)
if sum(x != ch
    for x in s) == k:
  return ch * len(s)
return '!'

RandomPancakeStackDiv2

This is almost the same problem as the division 1 version. The smaller constraints allow for some additional solutions to work. You can implement the solution explained for the division 1 but without using memoization. Or you can even just simulate all the possible permutations of pancakes that roll and calculate the expected value by the simulation.

RandomPancakeStack

Initially, there are n possible options, all of them are allowed and equally likely. Depending on which pancake i is chosen, the expected value is: d[i] + E( [“Pancake " i " on top”] ). Where E( [“Pancake " i " on top”] ) means the expected value of the remaining choices when the stack contains only pancake i on top. Since all of them have probability 1/n to be chosen, the expected value for the initial case is:

sum_(i=0)^(i<n)( (1/n)(d[i] + E( [“Pancake " i " on top”] ) ) )

The expected value is the defined as the sum of each possible value multiplied by its probability. This recursive version relies on that definition but also on the linearity of expectation a property that dictates that E(X + Y) = E(X) + E(Y). In this case there is a sum of a deliciousness d[i] plus the remaining deliciousness.

Let’s try to find the expected value of the remaining choices given the contents of the stack.

If the stack size is s, then there are n - s options for the next pancake that will be picked. Of them, if the pancake has a length larger than the pancake on top, the process will stop. This would mean we won’t add more deliciousness to the stack, the result would be 0.0. For each of the valid options the expected value is: d[i] + E( [“some stack that now has pancake i on top”]), the sum of all these results divided by (n-s) is the answer. Note that this sum considers only the correct options. For wrong options the result is 0.0, 0.0 multiplied by a probability is still 0.0, so they should be ignored.

With this we have defined a recursive function E() that will tell us the expected deliciousness given the contents of the stack. This is not very useful in its current state, for the number of possible stacks for this function might be too large. However, we can notice that we don’t really need to know all the contents of the stack.

In the calculation above, we found that the result depends on the size of the stack and the number of wrong options. The number of wrong options is determined by the top of the stack. We need to note that when the stack is valid, it means that each pancake that was chosen is smaller than the previous one. If the top of the stack is the pancake with index t (0-indexed), it means that none of the t smallest pancakes were chosen before. (The pancakes are sorted by length). Ergo only the pancakes with the t smallest indexes are correct. Remember that we also need to know s, the size of the stack, to know (n - s) so that 1 / (n-s) is the probability to pick a given pancake.

In other words, we only need two numbers to define the state: t, the number of remaining valid options, meaning that all pancakes with index less than t are valid and s, the current size of the stack. So we get to define a function f(s, t):

f(t,s) = sum_(i=0)^(i<t)( (1 / (n-s)) f(i,s+1) )

If pancake i is chosen, t’ becomes i, meaning that we can only pick those pancakes with index smaller than i after this choice. The size of the stack increases by 1.

The base case is when t = 0 or s = n, in both cases there are no more pancakes to pick and the expected deliciousness is 0.

To implement function f(t,s) let’s use dynamic programming and implement this iteratively by keeping a table of the results of f(t,s). Since f(t,s) will always call f(i,s+1) with i<t, we can just calculate the results in increasing order of t . There are O(n^2) combinations of arguments for this function. We need O(n) steps to calculate the sum. The total complexity is O(n^3), which is not that bad for n <= 250.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
double expectedDeliciousness(vector < int > d) {
  int n = d.size();
  // a 2D table of size (n+1) x (n+1)
  vector < vector < double >> dp(n + 1, vector < double > (n + 1, 0.0));

  // The number of valid pancakes:
  for (int t = 1; t <= n; t++) {
    // The size of the stack
    for (int s = 0; s < n; s++) {
      dp[t][s] = 0.0;
      // pick a valid pancake:
      for (int i = 0; i < t; i++) {
        if (s + 1 <= n) {
          dp[t][s] += (d[i] + dp[i][s + 1]);
        }
      }
      // the probability to pick each pancake is 1/(n-s)
      dp[t][s] /= (n - s);
    }

  }

  return dp[n][0];
}

PermutationCountsDiv2

How you represent a problem can be important. I think a way to visualize this problem is to imagine there are N slots where to write the numbers from 1 to N. Each i has a condition, either p(i) > p(i+1) or p(i) < p(i+1). We can picture this as having the next cell move up or below. Like this:

In this example, p(1) > p(2) > p(3) < p(4) < p(5) < p(6) < p(7) > p(8) < p(9) > p(10) > p(11).

Let’s decide where to place the first element of the permutation, 1, the smallest number in the permutation. Since this is the smallest number, we cannot put it in position 2, for example, because position 2 must have a greater element than position 3. There are 3 valid locations for the smallest number: 3, 8 and 11. 11 is a special case, it is in the extreme, but since its the smallest number in its only condition, it is a valid place for 1. Note that we cannot place 1 in position 1, because position 1 must have a number greater than the number in position 2.

Let’s try position 8.

Because 1 is the smallest number in the permutation, we can place any number in positions 7 and 9 and the condition that they must be larger than position 8 will fulfill. So we can ignore position 8 from now on.

When we picture the problem like this, it appears that we split the problem in two parts. The two parts look a lot like instances of the same problem. The only difference is that each side may contain numbers from the whole permutation. We can work around this issue and notice this: The conditions determine the order in which to put the numbers, but we can pick any set of distinct numbers to assign to each of the sides of the problem. For example, we had numbers {2,3,4,5,6,7,8,9,10,11} available to assign to the slots. We can decide to pick numbers {2,3,4,6,8,9,11} for the seven positions in the left side and {5,7,10} for the three positions in the right side:

Consider this, we can count the number of ways to order the numbers we picked for each. They are just smaller instances of the original problem. We just replace 1,2,3,4…7 with the picked numbers afterwards:

Let’s think of a function f(a,b) that counts the number of ways to solve the sub-problem made from interval of positions [a,b) (includes a, excludes b). There are t = b - a numbers in the permutation. We first pick a position i for the smallest number of the permutation. This position must be one that is not required to be greater than another position. This will split the problem in two parts: [a,i) and [i+1,b). There are (i - a) places in the left side. We assign (i - a) elements of the remaining permutation (minus the smallest element that we already assigned) to go to the left side, and the remaining to the right side, this means ((t - 1),(i - a)), where ((n),(k)) is the binomial coefficient, number of ways to select k out of n options. The number of ways to order the two sides are: f(a,i) and f(i+1,b). The product: ((t - 1),(i - a)) times f(a,i) times f(i+1,b) is the total number of ways to have the smallest element in position i. The sum over all valid i positions for the smallest number will be the result for f(a,b). We just need a base case: When b - a <= 1, the permutation is either empty or has one element, there is only 1 way to fill it.

We can implement f(a,b) using memoization or we can implement it iteratively by noticing that f(a,b) will always call versions of f() with smaller intervals. This makes O(n^2) states for the function, each of which needs O(n) to search for the candidate positions i of the smallest element. In total, the algorithm has O(n^3) time complexity and O(n^2) space complexity.

Problems that ask you to return the result modulo 1,000,000,007 (or a similar number) usually do so to allow us to solve problems that have large results without actually using those large numbers in calculations. We can handle these numbers with modular arithmetic. Read this recipe for more info.

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
const int MOD = 1000000007;

int countPermutations(int N, vector < int > pos) {
  vector < vector < int >> C(N + 1, vector < int > (N + 1, 0));
  // Binomial coefficient might be complicated to calculate modulo MOD
  // we can use Pascal's triangle, because it is based on addition.
  // Pascal's triangle:
  for (int i = 0; i <= N; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
  }
  vector < bool > lessThanNext(N);
  for (int x: pos) {
    lessThanNext[x - 1] = true;
  }
  vector < vector < long > > dp(N + 1, vector < long > (N + 1));
  // base cases:
  for (int i = 0; i <= N; i++) {
    dp[i][i] = 1;
    if (i + 1 <= N) {
      dp[i][i + 1] = 1;
    }
  }
  for (int t = 2; t <= N; t++) {
    for (int a = 0; a + t <= N; a++) {
      int b = a + t;
      dp[a][b] = 0;
      // pick a position for the smallest element:
      for (int i = a; i < b; i++) {
        if ((lessThanNext[i] || i == b - 1) && ((i == a) || !lessThanNext[i - 1])) {
          // can be the smallest
          long p = dp[a][i];
          long q = dp[i + 1][b];
          long r = C[t - 1][i - a];
          dp[a][b] += (((p * q) % MOD) * r) % MOD;
        }
      }
      dp[a][b] %= MOD;
    }
  }
  return dp[0][N];
}

PermutationCounts

The larger constraints will make this problem very different to the division 2 version.

Only one kind of condition

A complication is that there are two kinds of conditions. Some positions have p(i) > p(i+1) while others have: p(i) < p(i+1). Let’s try solving the problem ignoring the p(i) < p(i+1) conditions, if we use a notation similar to the one used in division 2, for N = 11, pos = {2,4,7,8}:

Note how once we decide which numbers go to each separated area, the order of the numbers is already established by the > conditions. So all that we need to calculate is the number of ways to assign elements to the areas. First choice is: out of 11 elements, we need 3 for interval [8,11]: ((11),(3)) = ((11),(8)). Then we select 1 out of 8 options: ((8),(1)) = ((8),(7)). 3 out of seven: ((7),(4)). The solution is:

((11),(8)) times ((8),(7)) times ((7),(4)) times ((4),(2)) times ((0),(0))

In this expression , I picked the version of the binomial coefficient that makes it easy to see how each member is linked to the next one.

Inclusion-exclusion

The previous approach ignores < conditions. But we can take advantage of the formula to solve the real problem. The idea is as follows: If we count the permutations ignoring the “less-than” conditions, the result count will include some invalid cases in which p(i) > p(i+1) for some i that needed p(i) < p(i+1) to be true. We can try to subtract the invalid cases. For each i that needs (p(i) < p(i+1)), count the number of permutations with (p(i) > p(i+1)) in addition to the other greater-than conditions. The sum of these counts would contain repetitions, because there might be some permutations that have two i indices such that (p(i) > p(i+1)) when (p(i) < p(i+1)) was needed, so there are some cases we subtracted twice and need to add back. No problem, just add them back, but to count them, we need to use the formula but now using (p(i) > p(i+1)) for two additional indexes instead of one. After this, we will need to subtract the cases with three of those indexes and so and so. This is the inclusion-exclusion principle:

In short:

+ ((11),(8))* ((8),(7))* ((7),(4))* ((4),(2))* ((2), (0))
- ((11),(8))* ((8),(7))* ((7),(4))* ((4),(0))
- ((11),(8))* ((8),(7))* ((7),(2))* ((2),(0))
- ((11),(8))* ((8),(4))* ((4),(2))* ((2),(0))
- ((11),(7))* ((7),(4))* ((4),(2))* ((2),(0))
+ ((11),(8))* ((8),(7))* ((7),(0))
+ ((11),(8))* ((8),(4))* ((4),(0))
+ ((11),(8))* ((8),(2))* ((2),(0))
+ ((11),(7))* ((7),(4))* ((4),(0))
+ ((11),(7))* ((7),(2))* ((2),(0))
+ ((11),(4))* ((4),(2))* ((2),(0))
- ((11),(8))* ((8),(0))
- ((11),(7))* ((7),(0))
- ((11),(4))* ((4),(0))
- ((11),(2))* ((2),(0))
+ ((11),(0))

This is something. Note that all the numbers involved in this are N, 0 or numbers from pos. This would make it simple to implement, except that we would need to use this formula O(2^|“pos”|) times. The size of pos can be very large.

Dynamic programming

So we have K+2 numbers: {0, “pos”[1], “pos”[2], … “pos”[K],N}, where K is the size of pos and we want to calculate the result of that gigantic formula above. We can call the result f(i = K+2) the result of finding that result using all the K+2 numbers. Let’s solve f(i). This is easier with an example. In the example above, we can group the expressions by their first coefficient:

+ ((11),(8))* ((8),(7))* ((7),(4))* ((4),(2))* ((2), (0))
- ((11),(8))* ((8),(7))* ((7),(4))* ((4),(0))
- ((11),(8))* ((8),(7))* ((7),(2))* ((2),(0))
- ((11),(8))* ((8),(4))* ((4),(2))* ((2),(0))
+ ((11),(8))* ((8),(7))* ((7),(0))
+ ((11),(8))* ((8),(4))* ((4),(0))
+ ((11),(8))* ((8),(2))* ((2),(0))
- ((11),(8))* ((8),(0))

- ((11),(7))* ((7),(4))* ((4),(2))* ((2),(0))
+ ((11),(7))* ((7),(4))* ((4),(0))
+ ((11),(7))* ((7),(2))* ((2),(0))
- ((11),(7))* ((7),(0))

+ ((11),(4))* ((4),(2))* ((2),(0))
- ((11),(4))* ((4),(0))

- ((11),(2))* ((2),(0))

+ ((11),(0))

Notice this, in the first group, if we factorize the ((11),(8)) we get:

((11),(8)) * [
+ ((8),(7))* ((7),(4))* ((4),(2))* ((2), (0))
- ((8),(7))* ((7),(4))* ((4),(0))
- ((8),(7))* ((7),(2))* ((2),(0))
- ((8),(4))* ((4),(2))* ((2),(0))
+ ((8),(7))* ((7),(0))
+ ((8),(4))* ((4),(0))
+ ((8),(2))* ((2),(0))
- ((8),(0))
]

This is actually the same as: ((11),(8)) * f("beginning at " 8)

If we keep doing it, we will get:

((11),(8)) * f("beginning at " 8) - ((11),(7)) * f("beginning at " 7) + ((11),(4)) * f("beginning at " 4) - ((11),(2)) * f("beginning at " 2) + ((11),(0)) * f("beginning at " 0)

This is the basis for an O(K^2) dynamic programming approach. The difficult part is in the details, and noticing how the signs work. They alternate in two different ways. Take a look to the source code for more details.

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
const int MOD = 1000000007;
int K;
long dp[2510]; //that mutual-exclusion formula when i-th number is the largest
// used in the first binomial coefficient
long Factorial[1000010];
long Finv[1000010]; // Finv[i] = modular multiplicative inverse of ( i! )

long C(int N, int K) {
  return Ffactorial[N] * Finv[K] % MOD * Finv[N - K] % MOD;
}

int countPermutations(int N, vector < int > pos) {
  Factorial[0] = Finv[0] = 1;
  for (int i = 1; i <= N; i++) {
    Factorial[i] = (Factorial[i - 1] * i) % MOD;
  }
  const int T = 1000000;
  Finv[T] = 397802501; //modular multiplicative inverse of 1000000! :/
  for (int i = T - 1; i >= 1; i--) {
    // n! = (n+1)! / n
    // 1/(n!) = n * (1 / (n+1)! ) 
    Finv[i] = ((i + 1) * Finv[i + 1]) % MOD;
  }

  K = pos.size() + 2;
  vector < int > a(K);
  a[0] = 0;
  for (int i = 1; i < K - 1; i++) {
    a[i] = pos[i - 1];
  }
  a[K - 1] = N;
  sort(a.begin(), a.end());

  // This is the key:
  dp[0] = 1;
  for (int i = 1; i < K; i++) {
    for (int j = 0; j < i; j++) {
      long tmp = dp[j] * C(a[i], a[j]) % MOD;
      // When to use a minus sign, when both are even or both are odd:
      if ((i + j) % 2 == 0) {
        dp[i] = (dp[i] - tmp + MOD) % MOD;
      } else {
        dp[i] = (dp[i] + tmp) % MOD;
      }
    }
  }
  return (int) dp[K - 1];
}

ForkliftTruckOperator

Single-colored row

The exact heights don’t matter

One might wonder why the numbers 1 and \sqrt{2} were picked for the heights of the red and blue boxes, respectively. One nice property of those two numbers is that they are linearly independent, that is, there are no integer constants A, B, C and D, with (A,B) \neq (C,D) such that A + B\sqrt{2} = C + D\sqrt{2}. In other words, in our problem this means that two pallets will only have the same height if and only if they have the same number of red and blue boxes.

Now, after some moves, Bob will be left with at most two heights for the pallets: let these heights be t_1 and t_2 (if it exists). Due to the way the crates are moved, it can be shown that t_1 and t_2 are also linearly independent: that is, a pallet will have the same height as another if and only if it contains the same number of t_1 towers and t_2 towers. This means that this case is essentially equivalent to the first: if we replaced all towers of height t_1 with a red box and all towers of height t_2 with a blue box, we would get the same answer.

What we can determine from this is that the actual heights of the towers don’t matter, as long as they are linearly independent. This means we can ignore the existence of towers and consider that our state is always a sequence of red and blue boxes. Without loss of generality, let’s suppose the first box is red (if it isn’t, we can swap the colors and the answer will remain the same). We can represent any state of the row by a sequence of numbers (s_n) = (s_1, s_2, s_3, …, s_n) indicating we have s_1 red boxes, then s_2 blue boxes, then s_3 red boxes, and so on.

Restricting the available states

The statement mentions that the stacks the lifted blocks are placed onto all have to have the same size. Therefore, all of the blocks in the bottom have to be of the same color.

One thing that immediately stands out in the problem statement is the condition that “after each move there should be at most two different pallet heights”. This seems pretty restrictive, and in fact if one tries some random moves on a position, it’s likely that most of these moves will leave the row with more than two different heights.

Ideally, we would like to have a way to easily determine which moves follow that condition and which don’t. After all, this will considerably reduce the number of possibilities we need to test to check for the smallest solution. It turns out case analysis can come to the rescue here.

Case 1: Both red and blue blocks are lifted by the forklift in the move

The new towers formed will already have two new sizes: the size of the bottom block + red, and the size of bottom block + blue. By the at most two heights condition, we cannot have any more heights. This includes single red and blue blocks: in other words, all of the blocks in the row have to be part of this move. This restricts our options considerably: half of the blocks in the row have to be lifted, and half of the blocks in the row have to be bottom blocks. We only have to decide whether the left half goes on top of the right half or the right half goes on top of the left half. As all of the bottom blocks have to be the same color, the half that has all blocks of the same color has to be the bottom half. In case both halves have all blocks of the same color, then it doesn’t matter which one you pick to be the bottom half.

Case 2: Blocks of a single color are lifted by the forklift in the move

In this case, the new towers formed will all have the same size. This means we get one extra height that can be used to accomodate one of the original heights. However, we had two heights originally, which means one of them has to disappear. The only way this can happen is if all blocks of that color are used on this move. As we only get to pick two consecutive sets to make the move with, all of the blocks of a certain color have to be contained in at most two consecutive sets, and each of these sets has to contain blocks of a single color. Let (s_n) be our state, as described above.

• If n \ge 6, then every color needs at least 3 consecutive sets to be covered. In this case this move is impossible.

• If n = 5, then the only valid moves are placing group 2 onto group 4, or group 4 onto group 2 (the groups of blue boxes).

• If n = 4, we can place group 2 onto group 4 (or vice-versa), or group 1 onto group 3 (or vice-versa).

• n < 4 will be treated later.

Case analysis summary

Based on this analysis, for any n \ge 6, there’s at most a single legal move: either it exists and we should make it, or it doesn’t exist and the case is impossible.

For any 4 \le n < 6, the number of moves is a small constant. Note that every move decreases n by at least 1, so we will reach a case in which n < 4 in at most two moves. It’s also important to note that it’s impossible to reach a state with n \ge 4 from any state with n < 4, so we won’t revisit this case later.

Let’s estimate the maximum number of states we will visit. Based on the two above observations, there is only a small constant amount of states with n > 4 that are reachable. For n < 4, we only have so many ways to distribute 300 blocks in at most 3 groups: to be more precise, C(300, 1)+C(300,2)+C(300,3), which is around 4.5 million. Of these, even less will be actually reachable. In other words, the total number of states visited is quite small.

This allows us to use a very straightforward way to get the optimal strategy for Bob: Breadth-first search. Care must be taken not to leave any possible movement out: the cases n < 4 have several possibilities. See codes for all of them.