SRM 676

Match Summary

Round Overview
Discuss this match

FarmvilleDiv2

If it wasn’t for the ability to reduce growth duration by spending money, the total time required to harvest all types of plants would be equal to the sum of all times. The cost part changes the problem in a simple way, any time you spend cost[i] money on plant i, it reduces the time for the plant by 1. This also means it reduces the total time by 1. So it doesn’t matter which plant you pick, the total cost will be reduced by 1. There are only two important things to know:

• After reducing the cost of some plants, a few might have a new harvest time equal to 0. Then you can no longer pick those plants.

• We cannot pick plants whose costs are larger than the budget.

• We want to make the total time, the sum of the individual times as small as possible. So we want to maximize the number of occasions in which we reduce the time by 1. This will happen only if we make sure to always pick the valid plant with the smallest cost. That way, the budget will last for as many time reductions as possible.

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
int minTime(vector < int > time, vector < int > cost, int budget) {
  int n = time.size();
  // while we can reduce the time:
  while (true) {
    // pick a plant to reduce
    int pick = -1;
    for (int i = 0; i < n; i++) {
      // time of the plant must be larger than 0, we need enough money:
      if ((time[i] > 0) && (cost[i] <= budget)) {
        // make sure to pick the plant with the smallest cost:
        if ((pick == -1) || (cost[pick] > cost[i])) {
          pick = i;
        }
      }
    }
    if (pick != -1) {
      // spend cost[pick] coins to reduce time by 1
      budget -= cost[pick];
      time[pick]--;
    } else {
      break;
    }
  }

  // sum of all times:
  return accumulate(time.begin(), time.end(), 0);
}

BoardEscapeDiv2

Let’s think recursively. We want to find if the when the token has k written on it and is at position (i,j) will the next player to move win or lose? We can define this as a boolean win[i][j][k]. All positions in which the player cannot move are losing positions. So if (i,j) contains an exit or if k = 0, then win[i][j][k] is false. Otherwise, it is possible to make a move. There are up to 4 other cells (n_x, n_y) that the player can move to. Also note that after making the move, k will decrease. Now since the player wants to win, they should pick a position that makes the other player lose. This means win[nx][ny][k-1] should be false. If any of the moves leads to that, then win[nx][ny][k-1] is true because our player can win. However, if all of the positions would make the other player win, then our current player will lose. This approach requires us to repeat this process for up to O(rcK) states, one for each possible combination of (i,j,k). We can calculate this iteratively (starting with small k = 0) or recursively using memoization:

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
int r, c;
vector < string > s;

int mem[50][50][101];

int win_position(int i, int j, int k) {
  int res = mem[i][j][k];
  if (res == -1) {
    // result for i,j,k not memoized yet, do it. 
    if ((k == 0) || ((s[i][j] == 'E'))) {
      // player cannot move
      res = 0;
    } else {
      static
      const int dx[4] = {
        0,
        0,
        -1,
        1
      };
      static
      const int dy[4] = {
        -1,
        1,
        0,
        0
      };
      res = 0;
      // try all 4 directions , if it is an allowed move and the other
      // player would lose then res = 1.
      for (int d = 0; d < 4; d++) {
        int nx = i + dx[d], ny = j + dy[d];
        if ((0 <= nx && nx < r) && (0 <= ny && ny < c) && (s[nx][ny] != '#')) {
          if (win_position(nx, ny, k - 1) == 0) {
            res = 1;
          }
        }
      }
    }
    mem[i][j][k] = res;
  }
  return res;
}

string findWinner(vector < string > s, int k) {
  r = s.size(), c = s[0].size();
  this - > s = s;

  // put a -1 in all values of the mem table:
  memset(mem, -1, sizeof(mem));

  // find the token's position:
  int tx = -1, ty = -1;
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      if (s[i][j] == 'T') {
        tx = i;
        ty = j;
      }
    }
  }

  // will next player win?
  return win_position(tx, ty, k) ? "Alice" : "Bob";
}

RailroadSwitchOperator

The trains enter the root each at a different time. Every second, any tree that’s not in the leaves moves deeper. This means that any level of depth of the tree may only contain at most one train. There will never be two trees at the same node. So the problem is that at some given times, some nodes need to point to the left child or the right child. The rest of the problem is to decide when to do something and how many switches to flip in that one action. It would be a bit confusing to deal with both issues at once. How about if we first simulate the tree movement to get a list of times, nodes and needed directions of those nodes for all the trees. So we will be able to know that at a time t, node p must be connected to direction left or right.

The simulation

In order to identify the nodes, we should index them somehow. Leaves are indexed from 1 to N but there are 2N - 1 in total: The root level contains 1 node, the next level 2 nodes, then 4 and so and so until N nodes (and N is a power of 2) so we have the sum 1 + 2 + 4 + … + 2^(logN) = 2^(logN + 1) = 2N. When thinking of indexes for the tree, it will be useful to think about Binary Indexed Trees (BIT), and just assign 0 to the root and say that for each node i, its left child will be : 2i + 1 and its right child will be: 2i+2. This will create a unique index for each of the nodes. And it helps us traverse the tree without having to build the data structure.

We can do the simulation separately for each tree. We know the time it enters the root, that means that initially we have p = 0 and time is t’ = t[i], the needed direction depends on x. With N leaves, the first N/2 leaves will be in the left subtree and the next N/2 in the right subtree. Depending of the index we find left or right. The direction helps us determine the next value for p: Either 2p + 1 or 2p + 2. The time t’ increases by 1. We can repeat this logic (every time the number of nodes in the subtree is halved) until we reach the leaf, making sure to save p, t and the direction in some list.

The optimization problem

Now we have a list of times, nodes and directions. For each item in the list, we know of a time at which a node needs to point to one direction. We can pick any time to run an action, an action flips one or more nodes’ directions.

Let’s sort the list in increasing order of t. All nodes initially point left, so let’s think of the earliest time t at which a node needs to point right. That is a moment at which we need to change the direction of a node. Since a single action can flip multiple nodes, we are able to change the direction of other nodes. The intuitive solution is to iterate the list for any later times in which a node needs to be flipped, so we can also flip that node. There is a limitation, however, once we flipped a node in the current action, we cannot flip it again (it would nullify its effect). This approach is correct, the problem is that with N <= 2^17, the number of items in the list might be way too large (The limit might even get close to 2^17 * 16).

So we need to implement that approach but without running a nested loop for all the future items in the list. After using an action, many of the next node flips will be free. Just we cannot flip the same node twice using the same action. So imagine we have a variable that tells us that an action was executed at a certain time. Then switch flips that come after that action are free and don’t need a new action. However, we need to avoid doing a switch action twice. For that matter, for each switch, we can store the last time it was used, if that time is higher than the action time, then we cannot flip it again. In addition, if after an action, we used a switch without flipping it, it cannot be flipped for free.

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
int minEnergy(int N, vector < int > x, vector < int > t) {
  vector < tuple < int, int, int >> events;

  for (int i = 0; i < x.size(); i++) {
    int p = 0;
    int a = 0, b = N;
    x[i]--;
    int ct = t[i];
    while (a + 1 < b) {
      int c = (a + b) / 2;
      if (x[i] < c) {
        // go left
        events.push_back(make_tuple(ct, p, -1));
        b = c;
        p = 2 * p + 1;
      } else {
        // go right
        events.push_back(make_tuple(ct, p, 1));
        a = c;
        p = 2 * p + 2;
      }
      ct++;
    }
  }

  sort(events.begin(), events.end());

  vector < int > switch_dir(N * 2 - 1, -1);
  vector < int > last_use(N * 2 - 1, 0);
  int last_action = -1;
  int actions = 0;

  for (auto ev: events) {
    int t, p, dir;
    tie(t, p, dir) = ev;
    if (last_use[p] < last_action) {
      // free
      last_use[p] = t;
      switch_dir[p] = dir;
    } else {
      // not free, we might need to change.
      if (switch_dir[p] != dir) {
        actions++;
        last_action = t;
        switch_dir[p] = dir;
      }
      last_use[p] = t;

    }
  }
  return actions;
}

WaterTank

We are looking for the minimum non-negative real value R such that if the tank loses R liters per second , the total amount of water won’t ever become greater than C. There’s some intervals in which more water is added incrementally.

The larger R is, the faster the tank loses water and the less likely the tank will overflow. In other words, if we had two values R_1, R_2 and R_2 > R_1, we can be certain that if R_1 is a correct value so will R_2. And if R_2 is incorrect, R_1 will be even less correct. This makes the problem suitable for a Binary Search solution.

In order for the Binary Search to work, we need to think of how to answer the following question: “Given R, is it large enough to prevent the tank from overflowing?”. This is a simple simulation. We start with 0 liters of water and each of the intervals will change the quantity of water. If it ever exceeds C, then R is too small. Sometimes R might be so large that the value is reduced, in some occasions it might empty the tank completely so if we estimate a negative amount of water, that means the tank emptied before the interval ended so we should reset the value to 0:

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
double binary_search(double lo, double hi, std:: function < bool(double) > f) {
  for (int i = 0; i < 100; i++) {
    double ha = (lo + hi) / 2;
    if (f(ha)) {
      hi = ha;
    } else {
      lo = ha;
    }
  }
  return hi;
}

double minOutputRate(vector < int > t, vector < int > x, int C) {
  double lo = 0.0; // a value so small that we are sure it won't be enough
  double hi = 50e13; // a value so large that we know it will be enough
  // The maximum amount of water that will be filled
  // to the tank is, per the constraints 50e12. So 50e13
  // should be more than enough.

  for (int i = 0; i < 100; i++) {
    // each iteration halves the error (distance) between lo and hi, 
    // with 100 iterations it should make them indistingishable and
    // thus both will converge to the minimum valid R.

    double R = (lo + hi) / 2;
    // simulate it
    bool good = true;
    double v = 0;
    for (int i = 0; i < t.size(); i++) {
      // currently v of water in tank
      // speed is (x[i] - R) per second
      double add = t[i] * (double)(x[i] - R);
      if (v + add > C) {
        good = false;
      }
      v = std::max(v + add, 0.0);
    }
    if (good) {
      // we found a smaller correct value
      hi = R;
    } else {
      // we found a larger correct value
      lo = R;
    }
  }
  return hi;
}

BoardEscape

Tokens are independent

Tokens can share cells and you can only move a single token in each turn. The movement of some tokens doesn’t affect the mobility of any unique token. So each token is really a separate game. Each of these separate games finishes once the token cannot be moved (its number becomes 0 or it reaches the exit or it’s locked). Players alternate between playing the tokens they choose until all of the token’s games end.

This is where game theory comes handy. The game is a typical turn-based game in which the player that becomes unable to make a move loses the game. It’s similar to Nim. The similarities don’t end there: The game is impartial. Which means that the game behaves the same way for both players , all that matters is the current state of the game and some states are winning state and some are losing states.

So we know the game is similar to nim and is composed of many sub-games (each token). This is where Nimbers (Grundy Numbers) can help us. Theory says that each state of this game (and its sub-games) can be represented by a Nimber - a special number that means that the game is equivalent to Nim with a certain amount of stones. This is useful when the game is a combination because of Nimber addition. Each of the tokens represents a game that will have a Nimber and the xor of all those Nimbers will give us the Nimber for the combined game and tell us if the initial state is a losing or winning state. So all that we need to do is calculate the Nimber for each separate token.

Each token’s Nimber

The initial position of a token and the number written on it make a game state and we should find its Nimber. There are up to 4 moves available. All moves reduce the written number by 1, so the states are acyclic. Let’s name nimber[k][i][j] to the nimber given to a token that is in cell (i,j) and has k written on it.

• When k = 0, the token cannot move , this means that nimber[0][i][j] is always 0.

• If the token reaches an exit, you can also see as it still being on the exit but unable to move, so nimber[k][i][j] will always be 0 when (i,j) is an exit.

• Otherwise, there are some moves available, each will take us to a new nimber: nimber[k-1][i’][j’] , it’s a new cell position (i,j) but this time the written number is lower. These are the options we have. According to Nimber theory, the nimber of the original state will be equal to the minimum excluded ordinal out of all the nimbers that are reachable. That is, we pick the minimum non-negative integer that is not equal to any of the nimber[k-1][i’][j’] options.

This would solve the problem if not for how enormous k can be

Cycles

k can be up to 10^9 which makes the previous table-based iterative calculation inviable. But we can use all that logic to try and find patterns that help us solve the problem. Let’s simulate calculating the nimbers for all cells first for k = 0, then k = 1 and so and so. We will use the following board:

…##…
.#.#…E…E…
…#…E.E…E.E…
…E…
…E.E…

Any of the non-wall cells may contain a token at some time so we need the nimbers for all of them. For k = 0, this is easy, all nimbers are 0 because we cannot move nimbers when their written number is 0.

00–00000000000000000
0-0-00000000000000000
00-000000000000000000
000000000000000000000
000000000000000000000

When k = 1, things change. All of the exit cells will have 0 as nimber. The remaining cells’s nimber is calculated based on the (up to 4) adjacent cell’s nimbers in the previous step. Most of those cells have adjacent cells with nimber = 0. One cell, however, has no adjacent cells whatsoever, so it will remain with 0 as a nimber, as 0 is not excluded.

11–11111111111111111
1-0-11011110111111111
11-111111101011101011
111111111110111111111
111111111111111101011

For k = 2, things become more interesting. Most cells have only 1 as adjacent nimbers, so their new nimber is 0. There are some cells that are adjacent to 1s AND 0s, their new nimber will be 2. There is even a cell that is adjacent to only 0s, so its nimber will remain 1:

00–00200002000000000
0-0-02020020200000000
00-000200201020002000
000000000020200020200
000000000002000002000

For k = 3, most of the cells are not adjacent to 1 and are adjacent to 0 so their nimbers will be 1. There is a very interesting exception, a cell that has become adjacent to 4 twos and thus will have a new nimber equal to 0. This is one of those special cases that may mislead you into a wrong if missed, because without it, it would appear that after k = 0, the whole process is cyclic depending on the parity of k. Note how similar the new table is to the one with k = 1:

11–11111111111111111
1-0-11011110111111111
11-111111101011101011
111111111110111110111
111111111111111101011

However, it will still be cyclic. If you try k = 4 and then k = 5 you will see how it comes back to this state.

After trying many cases in paper it will become clear that they are all cyclic and the cycle tends to be of size 2 (in fact, it is always cyclic in length 2 or 1). What varies is the number of steps before the patterns become cyclic. That case with a cell that has exit doors adjacent diagonally seems to be the exception rather than the rule.

It is not trivial to prove that the patterns will always be cyclic after k = 4. That the patterns for k = 3, k = 5, k = 7, … k = 999999999 are all equal and therefore the patterns for k = 4, k = 6, … k = 1000000000 are also the same. But it is valid to guess that the patterns will always become cyclic and take few steps to become so. So a solution that simulates for k = 1, 2, … until it detects a cycle should be viable. What follows is a proof sketch for how it will always be cyclic after k = 4:

• Cells that are already locked by walls or are Exit cells will always have a nimber equal to 0.

• Cells that only have exit cells as neighbors will have nimber 0 for all k

• Cells that are neighbors to exit cells AND non-exit cells will always be adjacent to a cell with nimber 0. So after k = 0, their nimbers will never be 0. In fact they seem to alternate between 1 and 2.

• Cells that are surrounded by cells that are neighbors to exit cells will remain as 0 starting with k = 3, because they are first surrounded by 1s, then by 2s, then 1s and so and so.

• Other cells will alternate between 0 and 1 because they are surrounded by either other cells that alternate between 0 and 1 or cells that alternate between 2 and 1. In both cases, the result is 0 or 1 depending on the parity of k.

Code

So there we have it, for k <= 4 we just calculate the nimber tables for each value of k. When k > 4, we just convert it to 3 or 4 and do the same.

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
string findWinner(vector < string > s, int k) {
  const int MAX = 4;
  if (k > MAX) {
    k = MAX - k % 2;
  }

  int nimber[MAX + 1][50][50];

  // initially, all zero
  memset(nimber, 0, sizeof(nimber));
  int r = s.size(), c = s[0].size();

  for (int K = 1; K <= k; K++) { // for each K, use the previous K to calculate new nimbers:
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        if (s[i][j] == 'E') {
          nimber[K][i][j] = 0; // always 0
        } else if (s[i][j] != '#') {
          int dx = 0, dy = 1;
          // find the set of nimbers used by adjacent cells:
          set < int > adj;
          for (int d = 0; d < 4; d++) {
            int nx = i + dx, ny = j + dy;
            if ((0 <= nx && nx < r) && (0 <= ny && ny < c) && (s[nx][ny] != '#')) {
              adj.insert(nimber[K - 1][nx][ny]);
            }
            tie(dx, dy) = make_tuple(dy, -dx);
          }
          // minimum excluded ordinal:
          nimber[K][i][j] = 0;
          while (adj.count(nimber[K][i][j]) == 1) {
            nimber[K][i][j]++;
          }
        }
      }
    }
  }
  // calculate the nimsum of all tokens:
  int nimsum = 0;
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      if (s[i][j] == 'T') {
        nimsum ^= nimber[k][i][j];
      }
    }
  }

  return (nimsum == 0) ? "Bob" : "Alice";
}