SRM 580

Match Summary

Round Overview
Discuss this match

Over 2000 coders participated in SRM 580. As we approach larger numbers like SRM 600 and SRM 1000. The ever popular Saturday schedule brought plenty of coders to play and practice for the incoming important tournament matches both inside and outside TopCoder. Problem setter snuke had prepared a interesting problem set that seems to follow an “Intervals” theme. The competition was also tougher than usual in division 1, with seven of the greatest coders successfully completing the hard problem. This time, however, more than that was needed. The top 3 coders were the only ones who solve the three available problems. Congratulations to azneye (division 2 win), K.A.D.R (Fastest 250), RAVEman(Third place), Egor (Second place) and specially tourist(fastest submission in the 600 and 1000 points problems, an impressive 1st place).

ShoutterDiv2

Used as: Division Two - Level One:

The problem asks us to count the total number of pairs of rabbits that become friends. Since there are up to 50 Rabbits, we can try iterate through all the possible pairs of rabbits and just count the ones that became friends.

Two Rabbits became friends if there is an instant of time at which they were both in the club. In other words, the intervals of time of the two Rabbits must overlap, even if the overlap is just a single point.

How to find if two intervals overlap

This is actually a classic problem. In short, there are four cases to consider:

A condition that covers all four cases is: (s[j] <= t[i] && s[i] <= t[j]).

1
2
3
4
5
6
7
8
9
10
11
12
13
int count(vector < int > s, vector < int > t) {
  int c = 0;
  // For each pair (i,j) of Rabbits:
  for (int i = 1; i < s.size(); i++) {
    for (int j = 0; j < i; j++) {
      if (s[j] <= t[i] && s[i] <= t[j]) {
        // If the intervals overlap, increase the count:
        c++;
      }
    }
  }
  return c;
}

EelAndRabbit

Used as: Division Two - Level Two:

Used as: Division One - Level One:

All eels have the same speed

Each eel can be abstractly represented as an interval. Since the eels move at the same speed, we can picture that the relative positions of the intervals will not change over time. In fact, we can make the problem about picking the time point in a set of intervals of times. Each eel will be catch-able only between two periods of time. For example, an eel of length L whose tail reaches the rabbit’s position at time T, will be catch-able only between times T and T+L, inclusive.

Two points of time

For each eel i, consider its respective interval [t[i], t[i] + l[i] ]. If the rabbit decides to catch eels at time x, then he will catch all eels that have an interval that contains x. However, there are two different times where the Rabbit can catch eels and the rabbit can’t catch the same eel twice. The objective is therefore to find the two points of time x and y such that the maximum number of different eel intervals contain x or y - If the same interval contains both x and y, it will only be counted once.

We can ignore most points

The times x and y can be non-integer and the range of time to choose from can be very large. However, in reality, we only need to consider some few important times. Of course, during all the time before the smallest possible t[i] there will be no eels to catch. This smallest t[i] is therefore the first relevant point:

Interestingly, if we move the time slightly to the right, the set of eel intervals that contain the time does not change:

In fact, we can see that the only point at which it will change will be the next value to coincide with a t[i] or t[i]+l[i]. Thanks to this we will only need to care about integer coordinates, and only up to 100 (When n=50) coordinates (all those equal to t[i] or t[i]+l[i]):

Even better, we do not even need those points equal to a (t[i]+l[i]) that are not equal to a (t[j]), the reason is that if we checked a previous t[j], and the next immediate point is only equal to (t[i]+l[i]), this new point is the end of at least one interval. The number of intervals can only be smaller than when we checked t[i]. Thanks to this, we only need to check points equal to a t[j]. Note that it is also valid to only check points equal to a t[i]+l[i] - We only need to check the rightmost or leftmost ends of all intervals instead of both.

We have found out that we only need to try values for x and y are equal to a t[i]. We can therefore just use a simple O(n²) loop to iterate through all the relevant pairs (x, y). For each pair, we need a O(n) loop to count the number of intervals that include the points (eels that can be caught by the Rabbit at those times).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int getmax(vector < int > l, vector < int > t) {
  int res = 0;
  // Iterate for all the important values of (x,y):
  for (int i = 0; i < t.size(); i++) {
    for (int j = i; j < t.size(); j++) {
      int x = t[i], y = t[j];
      // Count the number of intervals:
      int c = 0;
      for (int k = 0; k < l.size(); k++) {
        bool containsX = (t[k] <= x && x <= t[k] + l[k]);
        bool containsY = (t[k] <= y && y <= t[k] + l[k]);
        if (containsX || containsY) {
          c++;
        }
      }
      // Remember the best result
      res = std::max(res, c);
    }
  }
  return res;
}

WallGameDiv2

Used as: Division Two - Level Three:

Eel’s control of the game

Let us play from Eel’s perspective. Rabbit starts at top left cell and may be able to move to many cells in the top row until a blocked cell or the border of the board:

In an example with three reachable cells in the top row, the Rabbit can move to any of them and them move to the cell below it. Ad Eel we can place walls to vertically separate cells from each other. With the help of walls we can actually force the Rabbit to move to a specific one of them:

With the help of walls we can assume that the Rabbit will have to move the token to the position in the second row that we wanted. There are once again three locations in the lower row that are reachable. One of the other location is blocked with an ‘x’. The remaining locations (in red) are not valid, because if we made the Rabbit move there, the Rabbit would be unable to reach the bottom row (The paths from each of the squares in that area to the bottom row are blocked). Although we have many valid locations where we can force the Rabbit to move, we should place walls in a way that maximize the cost. We must leave at least one of them open for the Rabbit, though:

Then we face other three choices where to put the wall gap. The image to the right shows the whole path the Rabbit took to reach the bottom row.

The path the Rabbit takes at the end is a simple path, the Rabbit never visits the same square twice. There is no reason to, because the Rabbit already knows the positions of all the walls and can take a direct route. The simple path will finish at any of the cells in the bottom row.

Although the previous logic to consider sub-problems with the starting cell in each row in mind allows a dynamic programming solution. If you instead notice that Eel can force Rabbit to take any simple path to the bottom row that Eel prefers we can have a simpler one. For example, consider the following simple path:

It is possible to decide walls that force Rabbit to take any valid simple path we want. Eel wants Rabbit to spend the maximum cost possible. The path Eel forces Rabbit to take should be the one that has the largest possible sum of cell values, the worst simple path (It must be valid though, it must finish at one of the cells in the bottom row.).

Worst valid path from (0,0) to the bottom

A path is a sequence of cells. A simple path is a sequence of cells that does not visit the same cell twice. We can try a backtracking logic: The fist cell in the path is (0,0). When the current cell is (x,y), there are up to three choices for the next cell in the path:

• (x,y+1) : Move down

• (x - 1,y) : Move left.

• (x + 1,y) : Move right.

In many cases some of these moves are invalid. The new cell could have a ‘x’ and be blocked. It is also possible that no valid path is possible if you move to that cell. Or maybe the cell does not exist (you are at one of the borders and can only move in one horizontal direction). Or maybe the cell was already visited by the path, which would not be good because the path must be simple. Because we can’t move up, the only way to visit a cell that was already visited is to move backwards - Move left after a move to the right or vice versa. Thanks to this we only need to remember three variables: (x,y) the current cell and d, the previous direction. For example d is 1 if the previous move was to the left, 2 if the previous move was right and 0 otherwise. The result is a recurrence relation f(x,y,d) that returns the worst path starting at (x, y) such that the new direction is consistent with d:

• f(x,h - 1,d) = (cost(x, h-1)) (If h is the height of the board, then all cells at row (h - 1) are in the bottom. The path has finished.

• f(x, y, d) = -INF (A very small negative number) in case there are no valid paths starting at (x,y) such that the next direction is consistent with d. If ( x, y) is “x” assume also that the result is -INF. We use -INF to mark this state as invalid, because the latter steps maximize the result, so any valid result will be greater than the invalid result.

• f(x, y, 0) = cost(x, y) + (The worst path out of f( x, y+1, 0), f(x-1, y, 1), f(x+1, y, 2) ). (E.g: If we decide to move right, the new value of d is 2, and the next starting cell is (x+1, y).

• f(x, y, 1) = cost(x, y) + (The worst path out of f( x, y+1, 0) or f(x-1, y, 1) ). (The previous move was to the left, it is not valid to move right).

• f(x, y, 2) = cost(x, y) + (The worst path out of f( x, y+1, 0) or f(x+1, y, 2) ). (The previous move was to the right, it is not valid to move left).

This recurrence relation is acyclic and has a limit number of state combinations O(w*h) (There are at most three values of d for each cell). We can use memoization to implement it in polynomial time.

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
vector < string > costs;
int w, h;
int dp[50][50][3];
int worstPath(int y, int x, int d) {
  const int INF = 1000000000;
  int res = dp[y][x][d];
  if (res == -1) {
    int c = costs[y][x] - '0';
    if (costs[y][x] == 'x') {
      // Invalid
      res = -INF;
    } else if (y == h - 1) {
      // Base case, the bottom is the end of the road:
      res = c;
    } else {
      // Move down:
      res = c + worstPath(y + 1, x, 0);

      // Move left (as long as the previous move was not right)
      if ((d != 2) && (x > 0)) {
        res = std::max(res, c + worstPath(y, x - 1, 1));
      }
      // Move right (as long as the previous move was not left)
      if ((d != 1) && (x < w - 1)) {
        res = std::max(res, c + worstPath(y, x + 1, 2));
      }
    }
    // memoize the result:
    dp[y][x][d] = res;
  }
  return res;
}
int play(vector < string > costs) {
  //Save some variables for use by the worstPath function:
  this - > costs = costs;
  w = costs[0].size();
  h = costs.size();
  // initialize the whole dp[][][] array with -1:
  memset(dp, -1, sizeof(dp));
  // Solution: x=0, y=0, d=0
  return worstPath(0, 0, 0);
}

ShoutterDiv1

Used as: Division One - Level Two:

Disregard the general problem

It is usual in a problem like this to reduce it to a graph problem. Make a network in which each Rabbit is a vertex and the friendship relationships are edges. Turns out that this problem is too difficult, even when ignoring the possibility that there can be up to 2500 rabbits.

That is a general problem that ignores how the friendship relationship depends on intervals of time.

Merging intervals

Let us focus on the intervals. Each Rabbit is associated with an interval of time. There can be up to 2500 rabbits. Let us try solving the sub-problem for the message that a single Rabbit sent.

Imagine the green interval represents the Rabbit whose message we want to get read by all of the other Rabbits. When this rabbit transmitted his introduction, the rabbits with the teal intervals read it (Since these intervals overlap with the first one, they are friends). Each of these rabbits can retransmit the message. Imagine if two rabbits retransmitted the message:

These two retransmissions have made the remaining two rabbits receive the message. The advantage of this perspective is that we can see a retransmission as an extension of the first interval.

We can then interpret the objective as extending the original interval. It is not necessary to extend it to cover all of the other intervals. It is only necessary to make it overlap with all of the other intervals. In practice, this means that the minimum interval that it needs to cover is between the left-most t[i] and the right-most s[i], these two would be the extreme intervals.

Given the minimum t[i] and the maximum s[i], we need to extend the original interval such that it contains them. In order to extend the interval, we can take any interval it currently overlaps with, and then extend it to include this interval in its entirety, merging intervals is the equivalent of having a Rabbit retransmit the message. So we want to minimize the number of merges.

Covering the requirements

The previous perspective is enough to allow a solution, albeit one that has its complications. There is a way to simplify the logic. Consider the following initial setting:

And a possible final setting:

The original interval and the 3 intervals that were merged to it are painted orange. From this perspective we can see an alternative interpretation. We need a set of intervals such that their total merge connects the leftmost t[i] and the maximum s[i]. The set of intervals should contain the initial Rabbit and should otherwise have the minimum possible size. The set of intervals has to be connected. Each interval has to overlap with the next one. The minimum number of retransmissions is equal to the number of picked intervals minus one (one of the intervals is the original one).

In order to find the minimum size of this set. We should use the following approach based on a sorted list of intervals in non-decreasing order of s[i]. Begin with the minimum t[i], we need to connect t[i] with the right-most interval. We should find an interval that contains this point. Since we want to minimize the number of picked intervals, we should pick the interval j that has the maximum possible t[j]. This creates a new instance of the problem, but this time we need to connect t[j] with the right-most extreme. We can repeat the logic. There is only one exception: We must always pick the original interval, so if at one point it is possible to pick it, it should be picked (with no cost). In a sorted list of intervals, this algorithm can be implemented in O(n). Just note that after finding the best new interval to connect to an end point t, we no longer need to use any of the intervals that were verified to contain t.

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
// Assume arrays s[] and t[] were parsed from the original 
// combined string  input.
int count(vector < int > & s, vector < int > & t) {
  int n = t.size();
  // Sort in non-decreasing order of s[i], 
  int lleft = t[0]; //we need the left-most t[i] as a starting point.
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if ((s[j] < s[i]) || ((s[j] == s[i]) && (t[j] > t[i]))) {
        swap(s[i], s[j]);
        swap(t[i], t[j]);
      }
    }

    lleft = std::min(lleft, t[i]);
  }
  int cost = 0;
  // For each rabbit i:
  for (int i = 0; i < n; i++) {
    int left = lleft;
    int j = 0;
    // We need to repeat until even the right-most s[j] was checked:
    while (j < n) {
      //  If we can use Rabbit i, use it for free:
      if (s[i] <= left) {
        left = std::max(left, t[i]);
      }
      // Find the best new rabbit (interval) to add to the set)
      int best = -1;
      while ((j < n) && (s[j] <= left)) {
        if ((best == -1) || (t[best] < t[j])) {
          best = j;
        }
        j++;
      }
      if (best == -1) {
        return -1;
      }
      // The new rabbit is the left-most extreme, we can break:
      if (j == n) {
        break;
      }
      // Increase the cost, update the left variable
      cost++;
      left = t[best];
    }
  }
  return cost;

}

WallGameDiv1

Used as: Division One - Level Three:

From Eel’s perspective

Let us see the game from Eel’s perspective. Eel must decide both the time and location to place the walls.

Not giving away too much information

Consider an extreme case, Eel decides to place all the walls that it can just before the first turn. This sub-problem is basically the same as the division 2 version. After Eel places all the walls in this manner, there will still be a path that Rabbit can take. Since Rabbit already knows all the positions of the walls, Rabbit can take the direct, simplest path possible.

What happens is that when Eel places more walls than it needs to place in a step, it gives Rabbit more information than necessary. At any time, Eel should place only enough walls to force Rabbit into the worst path possible, but not more walls than that.

To place or not a wall directly below the Rabbit

Assume there is already a wall below the Token, Eel does not need to place any additional wall until the Rabbit moves the Token to a cell that has no walls below it. If Eel placed any wall before the Rabbit moves to one of those cells, Eel would be handling Rabbit information for free. Consider the following example, which is an extreme case:

If Eel places the remaining wall of the row too soon, Rabbit would know which side of the row is better to move to and will move directly to it. It is better for Eel to wait until the Rabbit takes the token to either extreme, making the Rabbit revisit many cells:

Eel should always wait until the token is placed on a cell that does not have a wall directly below it. Then Eel should decide between placing the wall in that location or not. In case all of the other cells in the row already have walls, Eel is unable to place a wall in that location (Because Eel cannot make the game completely impossible). The decision that Eel makes (place or not a wall below the current cell) will be the one that will require the largest cost.

From Rabbit’s perspective

Rabbit wants to minimize the cost. Assume Rabbit placed the Token above a cell that does not have a wall directly below to it. There are two possibilities: a) Eel will place a wall below that cell or b) Eel will not place a wall below the cell.

In case the Eel didn’t place the wall. The rabbit has the option to move to the row below it. This decision seems like a very good choice - The lower we move the closer we are to the bottom-most row. It is actually possible to show that this is always the optimal move.

Proof: The current cell position is (x, y). After the Rabbit placed the token on this cell, Eel didn’t put a wall below it, allowing Rabbit to move to cell (x, y+1). By contradiction: Assume there is a cell (x2, y+1) better than (x, y+1) as a starting point in row y+1. If there is no wall above ( x2, y+1), then the Rabbit might try to move to (x2, y). Eel will now have a choice to place a wall below (x2, y+1), because we know that the wall space between ( x,y) and (x,y+1) is empty, thus it will be a valid move to place a wall between (x2, y) and (x2, y+1). If Eel places this wall, then Rabbit will be forced to move back to (x,y), this time forced to move to (x,y+1), the path cost starting at (x,y+1) is still the same, but Rabbit spent cost units by unnecessarily attempting to move to (x2,y).

Whenever the path to the cell below the token is empty, Rabbit must always move down.

The other case is when the Token is already above a wall. Eel will wait until the Rabbit moves above an empty wall space. It makes sense to make the Rabbit take the straight path, either to the left space or the right space. Rabbit must pick the choice that minimizes the overall result (including the cost to move to the empty space).

Dynamic programming

Once the token is in row y, we can ignore any walls in previous rows. The only walls that matter are those that were placed between row y and y+1.

When the token enters the row for the first time, the walls between y and y+1 form an empty set. If Eel decides to place a wall below (x, y) the set of walls will contain only x. Rabbit can choose to move to x+1 or x-1, where Eel will once again have the choice to add a new wall. The new set of walls will be {x-1,x} or {x,x+1}. Let us assume Rabbit move to x-1, Rabbit once again has the choice to move to another cell that is not above a wall. The choices are x-2 or x+1. Note how the set of walls is always an interval of positions.. This is great because there are only O(w*w) possible intervals which we can represent by two variables, x0,x1 such that the interval is [x0,x1). There are only four choices for x, because x will either be outside the interval and be equal to x0-1 or x1 or it can also be at either of the extremes of the interval (equal to x0 or x1-1). The values for y are O(h). All in all, the state of the game can be described by tuple (y, x, x0,x1) and there are O(h*w*w) such tuples.

Define two functions: playEel(y, x, x0,x1) and playRabbit( y, x, x0,x1), that represent the decisions taken by each animal. playEel() returns the maximum possible cost Eel can accomplish after Rabbit moved the Token to a cell that does not have a wall directly below it. playRabbit() finds the minimum possible cost assuming that Eel has already decided whether or not to place a wall below (x,y).

• playEel(h-1, x, empty interval) is a base case, the Rabbit has managed to move the token to the last row. The Eel knows that the remaining cost is 0.

• playEel(y, x, x0,x1), as a precondition we know that (x,y) is not above a wall. The interval of walls [x0,x1) is either to the left or right of (x). Eel must decide between placing a wall or not. If Eel does not place a wall, it is Rabbit’s turn without a wall below the token: ( playRabbit(y, x, x0,x1) ). If Eel places a wall, the interval [x0,x1) must be extended to include x, the result is equal to playRabbit(y,x, extended interval). If all the cells of the row (other than x) already contain walls, it is not possible for Eel to place a wall.

• playRabbit(y, x, interval that does not contain x), is the case where Eel decided not to place a wall below (y,x), Rabbit must move to the below row. After this move, Eel has a chance to decide for the new position. The result is: cost(y+1, x) + playEel( y+1,x, empty interval).

• playRabbit(y, x, interval that contains x), gives the rabbit two choices: Move to the empty cell to the right or left of the interval. This move involves visiting (and paying costs) for a wide number of cells. For example, if Rabbit moves the token to x0-1 , the total cost is: (Cost to move from (x,y) to (x0-1,y) ) + playEel(y,x, x0-1,x1).

These mutually recursive recurrence relations are still acyclic and we should be able to implement them with dynamic programming or memoization.

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
int w, h;
vector < string > costs;
int dpRabbit[50][50][51][51];
int dpEel[50][50][51][51];

// Sum of costs between (y,x0) and (y,x1-1):
int sum(int y, int x0, int x1) {
  int s = 0;
  for (int i = x0; i < x1; i++) {
    s += costs[y][i] - '0';
  }
  return s;
}

int playRabbit(int y, int x, int x0, int x1) {
  // Token is currently at point (x,y). There are walls between each
  // (y, i) and (y+1,i) for each x0 <= i < x1 :
  // What should Rabbit do?

  int res = dpRabbit[y][x][x0][x1]; //O(n^3) states because x = x0-1, x0, x1-1 or x1
  if (res == -1) {
    if (!(x0 <= x && x < x1)) {
      // no wall below the Token. Best to move below:
      // It is convenient to use [x,x) as the empty interval. This way the
      // Eel function can easily extend it to include x:
      res = (costs[y + 1][x] - '0') + playEel(y + 1, x, x, x);
    } else {

      res = INF;
      // Rabbit decides to move to x0 - 1
      if (x0 > 0) {
        // sum(y,x0-1,x) = Cost to move from (x,y) to (x0-1,y).
        // playEel(y,x0-1, x0,x1) = Cost after Eel decides to place
        //                            a wall or not.
        //
        res = sum(y, x0 - 1, x) + playEel(y, x0 - 1, x0, x1);
      }

      // Rabbit decides to move to x1:
      if (x1 < w) {
        // sum(y, x+1, x1+1) = Cost to move from (x,y) to (x1,y).
        // playEel(y,x1, x0,x1 ) = Cost after Eel decides to place
        //                         a wall or not.
        //
        int tem = sum(y, x + 1, x1 + 1) + playEel(y, x1, x0, x1);

        // Rabbit wants the smaller cost:
        res = std::min(res, tem);
      }
    }
    dpRabbit[y][x][x0][x1] = res; // memoize the case.
  }
  return res;
}

int playEel(int y, int x, int x0, int x1) {
  // Token is currently at point (x,y). There are walls between each
  // (y, i) and (y+1,i) for each x0 <= i < x1 :
  // What should Eel do?

  int res = dpEel[y][x][x0][x1]; //Also O(n^3) because x = x0-1 or x1
  if (res == -1) {
    if (y == h - 1) {
      //The token is in the last row. Eel cannot do much about it.
      res = 0;
    } else {
      //What if Eel decides not to place a wall?
      res = playRabbit(y, x, x0, x1); //let the Rabbit do its move

      //What if Eel decides to place a wall?
      if (x1 - x0 < w - 1) { //Cannot fill the whole row with walls
        int tem = playRabbit(y, x, std::min(x0, x), std::max(x1, x + 1));
        // extend the interval that contains the wall

        // Eel wants the maximum cost:
        res = std::max(res, tem);
      }
    }
    dpEel[y][x][x0][x1] = res; // memoize the case.
  }
  return res;
}

int play(vector < string > costs) {
  // Save some variables for use by the functions:
  this - > costs = costs;
  h = costs.size(), w = costs[0].size();
  // Initialize dpRabbit and dpEel with -1s.
  memset(dpRabbit, -1, sizeof(dpRabbit));
  memset(dpEel, -1, sizeof(dpEel));

  // Rabbit picks a starting cell in the top row:
  int best = INF;
  for (int i = 0; i < w; i++) {
    // Rabbit wants the choice that costs the least:
    best = std::min(best, (costs[0][i] - '0') + playEel(0, i, i, i));
  }
  return best;

}