SRM 606

Match Summary

Round Overview
Discuss this match

The SRM 606 problem set was brought to you by espr1t (most problems) and ir5 (div1) hard) . When the match began, division 1 coders had to deal with an ad hoc problem that required some clever analysis. The medium was a traditional problem that had a minimal memory limit. The div1 hard was called an implementation problem by one admin and a beautiful problem by the other admin. Regardless, only two coders could solve it correctly. pieguy wins the match with 3 correct problems and a successful challenge. goie got a wonderful second place by being the only other problem to solve 3 problems correctly. Almost doubling the score of Lunarmony, who is still at an impressive third place, consider that they beat tomek’s fourth place. Congratulation also to division 2 winner: Newcomer ForeverZyh.

EllysSubstringSorter

Used as: Division Two - Level One:

This is an implementation problem. The number of possible `i` values is at most 50 (When `n = 50`, `L = 1`). We can just simulate them all and pick the lexicographically first of them all. This is the kind of problem in which good knowledge of the language can really help get a good score. For example:

• Picking the lexicographically first of two strings is usually part of the String library/class or a native feature. Lexicographical is a common ordering of string objects.

• The string of `L` characters beginning at index `i` is a substring. Also available as part of the library.

• Use the library sort functions/methods

• Beware of off by-one errors. A common mistake during the match was to make code that doesn’t try the last `L` characters of the string. The valid `i` values include `n - L`.

Implementation - Java

Java is special in which you need to first convert the substring from `i` to `i+L-1` into an array before being able to sort it. That’s why we use the toCharArray method. Afterwards, we need to turn the char[] back into a String, that’s where the String constructor comes handy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String getMin(String S, int L) {
  String res = "zz"; // a String that is guaranteed to be lexicographically
  // larger than anything we could find.

  for (int i = 0; i + L <= S.length(); i++) {
    // extract substring as a char[]
    char[] t = S.substring(i, i + L)
      .toCharArray();
    // sort it
    Arrays.sort(t);
    // rebuild a new string by joining the 3 substrings, including the
    // modified middle one. 
    String x = S.substring(0, i) + (new String(t)) + S.substring(i + L);
    // lexicographical compare, if it returns -1 , x is lesser.
    if (x.compareTo(res) < 0) {
      res = x;
    }
  }
  return res;
}

Implementation - c++

One c++ advantage is that we can actually sort the contents of a substring in-place (after copying the string). This is a trick that requires some knowledge of how iterators work ( [1], [2], [3]). The < operator is implemented for std::string which allows std::min to return the lexicographically-smallest of two strings.

1
2
3
4
5
6
7
8
9
10
11
string getMin(string S, int L) {
  string res = S; //fun exercise: why is S guaranteed to be larger than the result? 
  for (int i = 0; i + L <= S.length(); i++) {
    string t = S;
    // sort the substring starting at index i and finishing before index i + L:
    sort(t.begin() + i, t.begin() + i + L);
    // grab lex-smallest:
    res = std::min(res, t);
  }
  return res;
}

Implementation - python

Like in c++, the min function solves our problem. Like in Java, we need to turn a list of strings into a single string. That is where the join str method comes into play.

1
2
3
4
5
6
7
8
9
10
class EllysSubstringSorter:
  def getMin(self, S, L):

  # generate device output
for i
def device(i):
  return S[0: i] + (''.join(sorted(S[i: i + L]))) + S[i + L: ]

# pick minimum(lexicographically - first) possible output:
  return min(device(i) for i in range(len(S) - L + 1))

EllysNumberGuessing

Used as: Division Two - Level Two:

Used as: Division One - Level One:

The two candidates

We need to find out if there is a unique number `(1 <= x <= 10^9)` such that, for each `i`: `|“guess”[i] - x| = “answer”[i]`. The condition needs to be true for every `i`, that includes `i=0`. So the very first clue we have about `x` is: `|“guess”[0] - x| = “answer”[0]`.

Find numbers `x` such that: `|“guess”[0] - x| = “answer”[0]`. The distance between `“guess”[0]` and `“answer”[0]` should be exactly `x`. This means that we have found two possible values of `x`:

• `x_0 = “guess”[0] + “answer”[0]`

• `x_1 = “guess”[0] - “answer”[0]`

For any valid `x`, the first condition must be true. This means that no solution other than `x_0` and `x_1` can exist. Notice that no `answer[i]` can be 0, thus we should have: `x_0 != x_1`. For each of them, verify that it is a valid answer. A valid answer is within the specified bounds `(1 <= x_i <= 10^9)` and also we verify that it would give the specified answer for each `i`.

If exactly one of `x_0` or `x_1` is a correct answer, the result is that answer. If both `x_0` and `x_1` are valid, the result is -1. If neither `x_0` or `x_1` are valid, return -2.

Implementation

Some common implementation advice. Avoid repetitive operations. We can verify both `x_0` and `x_1` using the same code.

In c++:

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
int getNumber(vector < int > guesses, vector < int > answers) {
  // find the two candidates:
  int options[] = {
    guesses[0] + answers[0],
    guesses[0] - answers[0]
  };
  int res = -2;
  // for each candidate:
  for (int x: options) {
    // must be within bounds
    bool valid = (1 <= x && x <= 1000000000);
    // must obey all the conditions
    for (int i = 0; i < guesses.size(); i++) {
      valid = valid && (abs(guesses[i] - x) == answers[i]);
    }
    if (valid) {
      if (res != -2) {
        res = -1; // found a previous answer, set result to -1
      } else {
        res = x; // save answer
      }
    }

  }
  return res;
}

In python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class EllysNumberGuessing:
  def getNumber(self, guesses, answers):
  res = -2
def allValid(x):
  return not any(abs(guesses[i] - x) != answers[i]
    for i in range(len(guesses)))

for x in (guesses[0] + answers[0], guesses[0] - answers[0]):
  if (1 <= x <= 10 ** 9) and allValid(x):
    if res == -2:
  res = x
else:
  res = -1
return res

EllysCandyGame

Used as: Division Two - Level Three:

States of the game

Let’s take a game theory perspective. We can describe the state of the game by 3 factors:

• The number of candy in each of the boxes. Let’s call it a list of values `b_i`

• The number of candy Elly already got: `e`

• The number of candy Kris got: `k`

• Whose turn is it (Elly / Kris): `t`

When a player makes a decision it will modify the state (Picking box `i` empties it, increases the player’s candy and doubles the neighbor boxes’ candy). Each of the decisions leads to a game state (sub-state). Assume a player can predict the final outcome of each of these sub-states. Then the player would pick the one that gives the best outcome.

The base case is when all boxes are empty. Then there is nothing to do and we can compare `k` and `t`.

The challenge in this problem is to simplify this initial idea as much as possible until it can be done through simulation or further optimized with memoization.

The game is symmetrical

The game functions in a similar way for both the players. Each has the same objective - to win or to reach a draw (if it is not possible to win). This allows us to simplify the game so that it is always from the perspective of the next player to move.

Redefine the state as:

• The number of candy `b_i` in each box `i`.

• The number of candy `c_0` , the next player has.

• The number of candy `c_1` , the next player has.

Now the game works as follows: In each state, player 0 chooses a box with `b_i` candy in it. The number of candy in each box is updated. Then `c_0` increases by `b_i`. Now notice that to simulate the sub-state of the game, the amounts of candy would get swapped (The player that is currently player 0 will become player 1). So the state will move from `(b, c_0, c_1)` to `( “updated b” , c_1, c_0 + b_i)`.

We care only about the difference

At the end, we do not care that much about the actual values of `c_0` or `c_1`, we need only know if one is higher than the other. So we should always just remember `d = c_0 - c_1`. The state is now `(b, d)`, the list of candy in each box and the difference between current player and the other one.

The player wants to maximize the difference

Remember, player 0 wants to win or draw if it is not possible to win. Since `d` is the difference between the first player and the second player’s candy, this means the player wants the difference to be positive or 0 if the a positive is not possible.

We can change the game about maximizing the difference. If the maximum difference player 0 can get is positive, then she can use that strategy and win. If the maximum difference is 0, then she better use that strategy and draw. If even the maximum difference is negative, the player will be forced to lose.

Recurrence

This allows us to describe a function: `f(b, d)` that will return the final difference `d_f` if both players play optimally assuming the number of candy in each box `i` is `b_i` and the current difference `c_0 - c_1` is `d`. Next player wants to maximize the result, the other player wants to minimize it. (The other player wants to maximize `c_1 - c_0 = - d_f`, maximizing `-d_f` is the same as minimizing `d_f`.

• Base case: All boxes are empty. Result is `d`.

• Else player 0 simulates what happens after taking the candy in each non-empty box `i`: Player 0 gains `b_i` candy, which means that the difference `d = c_0 - c_1` increases by `b_i`. The remaining turns will also modify the difference so we should simulate the next state. Note that the player numbers are swapped in this sub-state. `d` represents a `c_0 - c_1`, but we need `c_1 - c_0` when calling the next state. This is the same as multiplying by -1. So we call `f(“modified b”, -(d + b_i)`. The result will give the final difference between `c_1 - c_0` , we need the inverse, so we multiply by -1 again:

  `f(b, d) = max( -f(“take candy from box i”, -(d + b_i) ) , " for each valid i")`

Depending on how well we implement it, and if the language doesn’t have too much overhead. This is actually a good moment to implement the solution. In fact, we could have implemented it before, although the simplifications mentioned so far also simplify the code. We can just run this recurrence relation because with `n <= 10` there will not be too many recursion branches. Imagine the worst case: `n = 10`. At first , first player has 10 options for the box to take, then second player has 9 options, then first player has 8 and so and so. This means that there will be `10!` calls to the function in total. It is not too large, but the execution time will be tight unless we are careful with the implementation. This is basically an `O(n!)` backtracking solution. The following c++ version needs 0.5 seconds in topcoder’s servers in the worst case:

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
const int INF = 1000000000;

// The trick is to update boxes[] in-place instead of creating a new
// copy for each call to the function    
vector < int > boxes;

int f(int d) {
  int res = -INF;
  // for each non-empty box
  for (int i = 0; i < boxes.size(); i++) {
    if (boxes[i] != 0) {
      // update the boxes vector:
      if (i > 0) {
        boxes[i - 1] *= 2;
      }
      if (i + 1 < boxes.size()) {
        boxes[i + 1] *= 2;
      }
      int old = boxes[i];
      boxes[i] = 0;

      // try it if we take it, remember the maximum difference
      res = std::max(res, -f(-(d + old)));

      // important to *restore* the vector so that the next call to f
      // is correct.
      boxes[i] = old;
      if (i > 0) {
        boxes[i - 1] /= 2;
      }
      if (i + 1 < boxes.size()) {
        boxes[i + 1] /= 2;
      }
    }
  }
  if (res == -INF) {
    // base case, all boxes are empty
    res = d;
  }
  return res;
}

string getWinner(vector < int > sweets) {
  boxes = sweets;
  int d = f(0);
  if (d < 0) {
    return "Kris";
  } else if (d > 0) {
    return "Elly";
  } else {
    return "Draw";
  }
}

The current difference won’t affect the strategy.

What if we want faster solutions? There is just one more simplification: Remember that `f(b, d)` involves the first player choosing the turn that optimizes the final difference. However, picture yourself playing the game, does the fact that you know that the current difference between your number of candy and the other player’s really affect your strategy? If you want to maximize the number of candy, would knowing that you have `x` candy at the moment stop you from getting the most candy possible from the remaining boxes? The answer is just no.

So let’s modify the function to remember only the current state of the boxes: `f(b)`. Gets the difference between the players’s candy considering only the non-empty boxes (ignoring previously-emptied boxes).

• If all boxes are empty, the only possible difference is 0 (do nothing)

• Else we try for each non-empty box `i`. We know that the difference will increase by `b_i`. The difference for the remaining boxes will be `-f(b’)` (once again, we swap the player numbers, which means negating the difference). So the difference after picking box `i` will be: `b_i - f(b ')`. Grab the maximum of them all.

The cool thing about this is that the total number of possible values of `b` is not large at all. Note that each box can be multiplied by 2 at most twice and can also become 0. This roughly gives 4 options for each of the boxes `(0,b_i,2b_i,4b_i)`. So an upper bound for the number of `b` lists is `4^n` . Note that `4^n` is already smaller than `10!`.

However, a more precise upper bound is `2^n`. This is because the number of candy in each box can be determined by only the list of already-empty boxes. If in `b[]`, a box is empty (and the original `“sweets”[]` array didn’ contain an empty box here) it means its neighbors are doubled.

It is good to know the number of states is small. The game is also acyclic, each turn reduces the number of non-empty boxes. So we can use memoization to ensure that each state of the function is evaluated once. This makes the complexity `O(n 2^n)` , because each call to the function needs an `O(n)` loop.

Implementation

`2^10` is small enough that we can safely use `b[]` as a vectors/list/tuple key in an associative array to perform the memoization. The following python code needs 0.1 seconds in topcoder servers the worst case:

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
class EllysCandyGame:
  def getWinner(self, sweets):
  # convert tuple a in such a way that its i - th box is taken, so it becomes
# empty and the neighbors are doubled
def takeIth(a, i):
  def g(j):
  if j == i:
  return 0
elif abs(i - j) == 1:
  return 2 * a[j]
else:
  return a[j]

return tuple(g(j) for j in range(len(a)))

# we do memoziation through a useful decorator declared below
@MemoizedFunction
def f(rem):
  if not any(rem):
  return 0 #base
case, all boxes empty
else:
  valid = tuple(i
    for i in range(len(rem)) if rem[i] != 0)
return max(rem[i] - f(takeIth(rem, i)) for i in valid)

# If the best difference Elly can make is negative, Kris wins, etc, etc, etc
if f(sweets) < 0:
  return "Kris"
elif f(sweets) > 0:
  return "Elly"
else:
  return "Draw"

# decorator that adds memoization to a
function using a dictionary: )
def MemoizedFunction(f):
  mem = dict()
def g( * args):
  if args not in mem:
  mem[args] = f( * args)
return mem[args]
return g

In c++, we can reach 0.01 seconds:

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
const int INF = 1000000000;

map < vector < int > , int > mem;

// convert vector a in such a way that its i-th box is taken, so it becomes
// empty and the neighbors are doubled
vector < int > takeIth(vector < int > boxes, int i) {
  boxes[i] = 0;
  if (i > 0) {
    boxes[i - 1] *= 2;
  }
  if (i + 1 < boxes.size()) {
    boxes[i + 1] *= 2;
  }
  return boxes;
}

int f(vector < int > boxes) {
  if (mem.count(boxes) == 0) {
    int & res = mem[boxes];
    res = -INF;
    // for each non-empty box
    for (int i = 0; i < boxes.size(); i++) {
      if (boxes[i] != 0) {
        // try it if we take it, remember the maximum difference
        res = std::max(res, boxes[i] - f(takeIth(boxes, i)));
      }
    }
    if (res == -INF) {
      // base case, all boxes are empty
      res = 0;
    }
  }
  return mem[boxes];
}

string getWinner(vector < int > sweets) {
  if (f(sweets) < 0) {
    return "Kris";
  } else if (f(sweets) > 0) {
    return "Elly";
  } else {
    return "Draw";
  }
}

Since the state is determined by the set of empty boxes, we could use bit masks to simplify the implementation and reduce overhead.

EllysPairing

Used as: Division One - Level Two:

The memory and time limits

There are at most 50000000 names and this problem uses a special memory limit - 16 MB. We’ll need sub-linear memory usage. The time limit will also be an issue, even the problem statement suggests ways to avoid much overhead when calculating the names.

The memory limit means that we will not be able to save all the names in an array, we need to iterate through them as we generate them.

The following sections are said to be well known-facts when solving this minimum pairs of distinct elements problem and are only included for completeness.

The result is frequently n/2

In the best case scenario, we can make `|__n/2__|` good pairs (From now on, we will be using the notation for floor and ceil functions). If `n` is even, that means pairing everybody with someone. Else it means pairing everybody but one person with someone.

The key idea is to put focus on the most frequent name in the list. If all names were different, the maximum number of times a name appears in the list is 1 and it is easy to see we can reach the optimal `|__n/2__|` result. As we increase the maximum frequency of the name, it will be more difficult to make the optimal matching. After some inspection you shall reach that even if the maximum frequency is as large as `|<sub>n/2</sub>|`, it is perfectly possible to have `|__n/2__|` pairs: Just put each of the people with the most frequent name in a distinct pair, then match the the other people with them. Even if two names had `|__n/2__|`, frequency, this would still be possible: Match each person with name 0 with a person with name 1. We use `|<sub>n/2</sub>|` because if `n` is odd, we can also reach the goal when the maximum frequency is `|__n/2__| + 1`.

However, once the maximum frequency of names is larger than `|<sub>n/2</sub>|`, we are forced to make some awkward pairs.

Perhaps this problem is easier to understand when you picture it as two rows of cells. Each column represents a pair. We first try to fill the top row using the element that appears the most times. Once we run out of cells in the top row, we are forced to move to the second row.

For `n = 10`, if X is the majority element that appears 5 times:

1
2
3
x x x x x
  ?
  ? ? ? ?

No matter what the other elements are, we will match each X with a different number.

However, if X appeared more than 5 times, for example 7:

1
2
x x x x x
x x ? ? ?

We are forced to have 2 awkard pairs. This can be found as 10 - (7 - 5). So the formula for the number of good pairs is: `n/2 - (c - (n/2))` where `c` is the number of times the dominating, majority element appears. When `n` is odd, things vary a bit: Try `n = 11`, X appears 6 times (meaning `|<sub>n/2</sub>|`)

1
2
3
x x x x x x
  ?
  ? ? ? ?

The number of times X appears is low enough so the result is still `|__n/2__|`. Now try it with X appearing 8 times:

1
2
x x x x x x
x x ? ? ?

From this we can find that the formula for the number of good pairs becomes: `|__n/2__| - ( c - |<sub>n/2</sub>| )`

So all that we need to find is:

• The element that is most frequent in the list of names.

• The number of times that element appears, and if that is higher than `|<sub>n/2</sub>|`

Majority element and its frequency

Let’s find if the most frequent element is too frequent and and the number of times it appears in `O(n)` time and sublinear memory, e.g: `O(1)` memory.

The trick here is that we don’t really need to always find the most frequent element. We only need to find it when it appears more than `|<sub>n/2</sub>|` times. This kind of element is the majority element. It turns out that this is a known problem: A Linear Time Majority Vote Algorithm. If we can use that algorithm to find a candidate for the majority element in `O(1)` memory and `O(n)` time (iterating through all the names generated by the pseudo-random algorithm), we just need another `O(n)` loop (iterating again) to count the number of times it appears.

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
int getMax(int M, vector < int > count, vector < int > first, vector < int > mult, vector < int > add) {
  // Find candidate:
  int p = -1, q = 0;
  // Because we can't keep them in memory,
  // We need to iterate through the names as we generate them.
  for (int i = 0; i < count.size(); i++) {
    unsigned int x = first[i];
    for (int j = 0; j < count[i]; j++) {
      // process x:
      // this is the part where we do the majority algorithm:
      if (p != x) {
        if (q == 0) {
          // there is no current candidate, make the element one
          p = x;
          q = 1;
        } else {
          // cancel the current candidate with the new element
          q--;
        }
      } else {
        q++;
      }
      // continue generation
      x = (x * mult[i] + add[i]) & (M - 1);
    }
  }

  // p now holds the candidate
  // check if candidate is the majority:
  int n = 0, c = 0;
  // we need to generate the names, again:
  for (int i = 0; i < count.size(); i++) {
    unsigned int x = first[i];
    for (int j = 0; j < count[i]; j++) {
      // process x:
      // this is the part where we count the frequency of p:
      if (x == p) {
        c++;
      }
      n++;
      // continue generation
      x = (x * mult[i] + add[i]) & (M - 1);
    }
  }

  // if so...
  if (c > (n + 1) / 2) {
    if (n % 2 == 1) {
      return n / 2 - (c - n / 2 - 1);
    } else {
      return n / 2 - (c - n / 2);
    }
  } else {
    return n / 2;
  }
}

Having to generate the names all over again in a separate part of the algorithm is too repetitive. But we cannot just save the names in an array or list. We can, however, simplify the code through a number of ideas. For example, if we can use some functional programming capabilities like the following code that uses c++11 lambda expressions:

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
int getMax(int M, vector < int > count, vector < int > first, vector < int > mult, vector < int > add) {
  // Create a closure, forEachName, it takes a function g as an argument.
  // forEachName generates the names using the pseudo-random algorithm
  // and calls g(x) for each of them.
  auto forEachName = [ & ](std:: function < void(int) > g) {
    for (int i = 0; i < count.size(); i++) {
      unsigned int x = first[i];
      for (int j = 0; j < count[i]; j++) {
        g(x);
        x = (x * mult[i] + add[i]) & (M - 1);
      }
    }
  };

  // Find candidate: We create a function that processes each x found by forEachName.
  // Using the majority algorithm. Note how locals p and q are modified by the function.
  int p = -1, q = 0;
  forEachName([ & ](int x) {
    if (p != x) {
      if (q == 0) {
        p = x;
        q = 1;
      } else {
        q--;
      }
    } else {
      q++;
    }
  });

  // check if candidate is the majority: Same as before, we just count the frequency with a new function
  int n = 0, c = 0;
  forEachName([ & ](int x) {
    if (x == p) {
      c++;
    }
    n++;
  });

  // one liner for the formula:
  return n / 2 - ((c > n / 2) ? (c - n / 2 - n % 2) : 0);
}

Subcube

Used as: Division One - Level Three:

This problem just requires some little analysis and a clever idea to simplify the otherwise complicated implementation.

Two points

Imagine two points in the list of provided points. Any pairs of points can form an edge of infinitely many cubes, so any pair of points is a subcube.

Three points

If we go one up, we have three points. Not any triple can be a subcube. In fact, there are only three kinds of triples (ignoring rotations and inversions) that could be a subcube:

1. The three points are in the same face of the cube. Note that in this case, there are only two cubes that would contain these 3 points. Note the two bottom left images, the cube could be at either side of the plane that contains the 3 points.

2. Two points make an edge and the other is one of the vertices the completely opposite edge. In this case, there is only one cube that can contain the 3 points.

3. Three points equidistant to another vertex. Note the middle image in the right column. In this case, there are also two possible cubes. Just imagine that there are two possible points that are equidistant to the 3 points.

Preliminary, complicated idea

In conclusion, there are only `O(n^3)` cubes the `n` points could be subcubes of. Each triple of points generates at most two candidate cubes. This enables an approach idea: We could take each of the triples of points, generate the (at most two) cubes that could contain the 3 points as vertices and verify if any of the other points from the input are also vertices. This will effectively find all cubes that contain at least 3 points. For each of the cubes, we save the set of vertices in some list. We can later extract all subsets from the sets in this list and count them.

This approach is good in theory, for each `O(n^3)` cube we might find at most `2^8` subsets, so it will work in time. The problem with this approach is that it will be too complex too implement. There are many rotations and inversions possible for each of the two kinds of cube, and there might be too much geometr.

Distances

A better other idea is to take advantage of our knowledge that there are at most `O(n^3)` cubes. We can try to recursively generate them, starting with three points and adding new points making sure that their distances to the already-existent points are consistent.

This recursive algorithm was implemented by goie, you can read their implementation.