SRM 610

Match Summary

Round Overview
Discuss this match

Thank brunoja for contributing this problem set. Also congratulations to the division 1 winners: SkidanovAlex (1st), AstroConjecture (2nd), scott_wu (3rd), ir5 (4th) and pparys (5th). They all solved the 3 problems, including the surprisingly geometric hard problem. Also congratulations to division 2 winner: Hasan0540

DivideByZero

Used as: Division Two - Level One:

This is a simulation problem. Notice that only the numbers from 1 to 100 are allowed as input. Whenever you take the integer part of division `a/b` where `a > b`, the integer part will be greater than `0` and not larger than `a`. It follows that in the worst case, the largest list of numbers we can reach is the one containing all 100 numbers from 1 to 100. So the list will never contain more than 100 numbers. This means that we can just use the straightforward simulation.

More formally: We will add at most `98` new numbers and for each of them, we need an `O(n^2)` search to browse through each of the pairs of those numbers. We also need an `O(n)` search to verify that `a/b` does not exist. This means that in an exaggerated worst case, we need `O(N^4)` steps, where `N` is the maximum number in the sequence. Even that slow solution should run within the time limit for `N <= 100` in TC’s server. Like in the following python code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class DivideByZero:
  def CountNumbers(self, numbers):
  s = list(numbers)
old = 0
# repeat as long as there are new numbers in the list:
  while len(s) > old:
  old = len(s) # save current amount of numbers in the paper.
# find a good pair(a, b)
for a in s:
  for b in s:
  if a > b and a / b not in s:
  # A new number, append it.
s.append(a / b)
return len(s)

Note that problem called DivideByZero, but the division of the two numbers cannot be 0 because `a > b`, so a division by zero will simply not happen.

There are many ways to simplify the code and also make the algorithm faster. In the following c++ solution, we use a set data structure from its library to keep track of the numbers in the list. This makes searching for the number in the paper and adding a new number to the paper `O(log(n))`, thus simplifying complexity to `O(N^3 log(N))`:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int CountNumbers(vector < int > numbers) {
  int old = 0;
  set < int > paper(numbers.begin(), numbers.end());
  while (paper.size() > old) {
    old = paper.size();
    for (int a: paper) {
      for (int b: paper) {
        if ((a > b) && (paper.count(a / b) == 0)) {
          paper.insert(a / b);
        }
      }
    }
  }
  return paper.size();
}

Of course, the other languages have set structures too, like python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class DivideByZero:
  def CountNumbers(self, numbers):
  s = set(numbers)
old = 0
# repeat as long as there are new numbers in the list:
  while len(s) > old:
  old = len(s) # save current amount of numbers in the paper.
# find a good pair(a, b)
for a in list(s): #
for each a in a copy of the set:
  for b in list(s):
  if a > b and a / b not in s:
  # A new number, append it.
s.add(a / b)
return len(s)

A possible issue with any implementation is that we have to add elements to the paper set/list/vector while iterating through it. Depending on the language/data structure used that might not be possible. In the previous example, we make copies of the set to iterate it so we can modify it freely.

TheMatrix

Used as: Division Two - Level Two:

Used as: Division One - Level One:

Consider that even with `n <= 100` (Where `n` is the maximum dimension of the matrix), a complexity of `O(n^4)` shall work all right within the time limit for most of the supported languages. We’ll begin with a relatively simple `O(n^4)` approach that can also be turned into `O(n^3)` with a small change.

Fix the first and last column

The rectangle we have to search for can be described by two corners: `(x_0,y_0)`, `(x_1,y_1)`, what we can do is fix the start and final columns, the `x_0 = i` and `x_1 = j` coordinates. Then we are interested in finding the maximum height of a correct subrectangle inside the matrix composed of columns between `x_0 = i` and `x_1 = j`, inclusive. For each pair `(i,j)`, we can ignore the other columns.

Each of the sub-rows should be of the kind 010101… or 1010101… with an `O(n^2)` we can find whether each of these sub-rows belongs to either of those types. We can flag them as type ‘0’ for 010101… , type ‘1’ for 10101010… and we should also flag ‘x’ to the rows that don’t belong to any of those types.

After that we have the flags of each of the rows as a sequence like “010XX10101X11000X110101XXX”. We should just find the largest substring of this sequence that is made of alternating 1s and 0s. The size of this largest substring is equal to the largest height of a correct sub-rectangle within the two columns `i`, `j`. We can find that largest substring with an `O(n^2)` loop but `O(n)` is also easy.
In total the following code will need `O(n^4)` steps:

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
int MaxArea(vector < string > board) {
  int res = 0, w = board[0].size(), h = board.size();
  // fix columns i and j:
  for (int i = 0; i < w; i++) {
    for (int j = i; j < w; j++) {
      // the flags for each row:
      char row[h];

      // find the flags, 0 for rows 010101.., 1 for rows 101010... X for other.
      for (int k = 0; k < h; k++) {
        bool alt = true;
        for (int r = i + 1; r <= j; r++) {
          alt = alt && (board[k][r] != board[k][r - 1]);
        }
        row[k] = (alt ? board[k][i] : 'X');
      }

      // Find the largest substring of alternating 0s and 1s:
      int mh = 0, ch = 0;
      for (int k = 0; k < h; k++) {
        if (row[k] == 'X') {
          ch = 0;
        } else if ((ch > 0) && (row[k - 1] != row[k])) {
          ch++;
        } else {
          ch = 1;
        }
        mh = max(mh, ch);
      }
      // The largest height is mh, the width is j - i +1
      res = std::max(res, mh * (j - i + 1));
    }
  }
  return res;
}

Cubic complexity

The reason the previous code is `O(n^4)` is that we need an `O(n^2)` loop to flag the rows. We can optimize to `O(n^3)` by noticing that the flags for `j` can be found in `O(n)` if we reuse the knowledge of the flags for `j-1`. For each row `k`, if the flag for `j-1` was “X”, the flag will also be “X”, else if the bit at position `(k , j)` is different to the bit at position `(k, j-1)` the flag can stay the same (the first character of the sequence is the one at column `i`).

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
int MaxArea(vector < string > board) {
  int res = 0, w = board[0].size(), h = board.size();
  // fix columns i and j:
  for (int i = 0; i < w; i++) {
    // the flags for each row:
    char row[h];
    for (int j = i; j < w; j++) {

      if (j == i) { //initialize flags:
        for (int k = 0; k < h; k++) {
          row[k] = board[k][i];
        }
      } else {
        // update the flags, 0 for rows 010101.., 1 for rows 101010... X for other.
        for (int k = 0; k < h; k++) {
          if (board[k][j] == board[k][j - 1]) {
            row[k] = 'X';
          }
        }
      }

      // Find the largest substring of alternating 0s and 1s:
      int mh = 0, ch = 0;
      for (int k = 0; k < h; k++) {
        if (row[k] == 'X') {
          ch = 0;
        } else if ((ch > 0) && (row[k - 1] != row[k])) {
          ch++;
        } else {
          ch = 1;
        }
        mh = max(mh, ch);
      }
      // The largest height is mh, the width is j - i +1
      res = std::max(res, mh * (j - i + 1));
    }
  }
  return res;
}

MiningGoldEasy

Used as: Division Two - Level Three:

A recurrence

Let’s try to solve the problem using a recursive logic. First of all, since before the first step we can travel to any of the possible locations, we should find the top score you can earn if we move to location `(x,y)` before the first move. We should try each location `(x,y)` as a candidate.

After the first move, you earn some gold depending on the location of event 0. Then you can choose to move to a new point `(x’,y’)` which shares column or row `(x,y)`. After this move, we are in a similar sub-problem to the initial one, you are located at position `(x’,y’)` and want to know the maximum earnings you can make with the last `K-1` events. (Where `K` is the number of events).

The recurrence relation goes as follows: `f(x,y,i)` finds the maximum earnings if you are located at position `(x,y)` before event `i`.

• If `i = K`, all events have finished and you cannot earn any more gold. The result is 0. This is the base case.

• Else we earn some gold `m` equal to the Manhattan distance between `(x,y)` and the event’s location. Finally you can move to a new point `(x’,y’)` and then the remaining events will happen and you might move again later. We can try to iterate through all reachable points `(x’,y’)` that share the column or row with `(x,y)` and pick the maximum `f(x’,y’,i+1)`.

The complexity of this approach is large. Imagine `T` was the largest dimension. There are `O(T^2)` values for `(x,y)` , which means there are `O(KT^2)` possible states for the function. In each state, we need an `O(T)` loop to pick the new row or the new column. In total we have an `O(KT^3)` complexity. Note that `T` can be very large: `T '= 1000000`.

Relevant points

In order to make the solution more efficient, we just need to notice that it is never necessary to move to a point `(x,y)` such that `x` or `y` don’t match at least one of the events’ coordinates. This means that there are only `O(k)` options we need to try for `x` and `y` in each step and there are `O(k^2)` different values. This changes the complexity to `O(k^4)`.

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
int t, N, M;
int mem[50][50][51];
vector < int > event_i, event_j;

int f(int a, int b, int s) {
  int & res = mem[a][b][s];
  if (res == -1) {
    if (s == t) {
      res = 0;
    } else {
      int x = N + M -
        abs(event_i[a] - event_i[s]) -
        abs(event_j[b] - event_j[s]);
      res = 0;
      // change row:
      for (int na = 0; na < event_i.size(); na++) {
        res = std::max(res, x + f(na, b, s + 1));
      }
      // change column:
      for (int nb = 0; nb < event_j.size(); nb++) {
        res = std::max(res, x + f(a, nb, s + 1));
      }
    }
  }
  return res;
}

int GetMaximumGold(int N, int M, vector < int > event_i, vector < int > event_j) {
  this - > t = event_i.size();
  this - > N = N;
  this - > M = M;
  this - > event_i = event_i;
  this - > event_j = event_j;

  memset(mem, -1, sizeof(mem));
  int mx = 0;
  for (int a = 0; a < event_i.size(); a++) {
    for (int b = 0; b < event_j.size(); b++) {
      mx = std::max(mx, f(a, b, 0));
    }
  }
  return mx;
}

AlbertoTheAviator

Used as: Division One - Level Two:

The selection and the order

We are searching for the maximum-size set of missions that can be done. Let’s try a simpler problem first: Given a fixed set `S` of missions, can we do all the missions in that set?

We just need to find an optimal way to order the missions. This would mean that if the ordering doesn’t allow us to do all the missions we would be certain it is impossible to do it. There can be many orderings for missions and we will leave that analysis for later. For now, let’s assume that ordering exists.

Dynamic programming

Assuming that ordering exists, we cannot just iterate through all (at most `2^50`) subsets of missions and remember the largest set that can be completed. However, we can use dynamic programming.

The ordering must have established a mission such that, if it is in the set we picked, should be solved before all the other missions. Let’s call this mission, mission 0. Initially we have two options for the set: Either include mission 0 or not.

• If we decide not to include it, we can just focus on the remaining missions.

• If we decide to include it, we can assume it will be used first. This means that for the remaining missions we pick , the fuel value will be modified and we can proceed to decide the remaining missions…

The recurrence relation idea is as follows: `G( F, i )`, we have already processed the `i` missions that, according to the ordering, should be finished before the other missions. The current fuel amount is `F`. We need to decide what to do with the i-th mission (according to the ordering).

• If it is possible to do it (`F` is large enough), then the fuel amount will decrease and then possibly increase to a value `F’`. The result will be: `1 + G(F’, i+1)`.

• If we cannot or decide not to do the i-th mission, the result will be: `G(F, i+1)`.

• The maximum between `1 + G(F’, i+1)` and `G(F, i+1)`, is the result for `G(F, x)`.

The amount of fuel is at most 5000, each recursion step is `O(1)`. If we use memoization the complexity is: `O(F * k)`.

The best ordering

Let’s now talk about the best order to take the missions. There are many suspects: Sort by fuel mission cost? Fuel cost - refuel cost? Just refuel cost? There is no solution to this dilemma other than try them all until we can find one that we can prove to be optimal.

It turns out that the best ordering is to order the sequence by refuel in non-increasing order. How can we prove it? There are a couple of example proofs in the forums.

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
static
const int MAX = 52;
static
const int MM = 5002;

int n;
vector < int > ids, duration, refuel;
int mem[MAX][MM];

int recurse(int idx, int rem) {
  if (idx >= n) {
    return 0;
  }
  if (mem[idx][rem] == -1) {
    int ans = 0;
    // Don't take current mission
    ans = max(ans, recurse(idx + 1, rem));
    // Take current mission
    if (rem >= duration[ids[idx]]) {
      ans = max(ans, recurse(idx + 1, rem - duration[ids[idx]] + refuel[ids[idx]]) + 1);
    }
    mem[idx][rem] = ans;
  }
  return mem[idx][rem];
}

int MaximumFlights(int F, vector < int > _duration, vector < int > _refuel) {
  n = (int) _duration.size();
  ids.resize(n);
  duration = _duration;
  refuel = _refuel;

  for (int i = 0; i < n; i++) {
    ids[i] = i;
  }
  // sort non-decreasingly by fuel:
  sort(ids.begin(), ids.end(), [ & ](int i, int j) {
    return refuel[i] > refuel[j];
  });
  memset(mem, -1, sizeof(mem));
  return recurse(0, F);
}

MiningGoldHard

Used as: Division One - Level Three:

Independent axis

In each event, the amount of gold you make depends on the `x` and `y` coordinates of your current cell. The cost function is: `N + M - |e_i - x| - |e_j - y|`, where `(e_i, e_j)` are the event coordinates. Then the allowed movement is, you can move at most `d_i` units vertically and `d_j` units horizontally. It turns out that the solution is independent for each axis/direction. Just consider the values: `N - |e_i - x|` and `M - |e_j - y|` as independent parts of the total profit. Then we are allowed to make decisions in each axis without affecting the other.

Let’s then just solve for a single axis. There are points `x=0, 1, … N`. Before the first event, you can pick any of those points. After an event `i` with event position `e_i`, you earn `N - |e_i-x|` and you can increase or decrease `x` by at most `d_i` units. Without leaving interval `[0,N]`. If we can solve this sub-problem, we can use the same solution to solve the sub-problem for `y` and `M`.

Dynamic programming

There is a slow dynamic programming approach that can be used as a good starting point. Imagine we knew, for each `x`, the value `f(x,i)`, the maximum earnings you can make if you are located at point `x` starting at move `i`. The dynamic programming is simple:

• If `i = k` (Where `k` is the number of events), then there is nothing to do anymore and the maximum earning is 0 (base case).

• Else we earn `N - | e_i - x|` gold and then we need to decide where to move. We should pick a value `x’` such that `f(x’, i+1)` is as large as possible. Then the overall result is: `N - | e_i - x | + f(x’ , i+1)`. Note that `x’` follows is a integer that follows some constraints: `(0 <= x’ <= N), ( |x - x’| <= d_i)`.

This dynamic programming approach has a problem: The values of `x` are between 0 and `N`, inclusive, and `N` can be very large. In order to turn this knowledge into a solution, we needs a very good idea:

Function graphics

If you think about it, `f(x,i)` can be seen as describing a function dependent on `x`: `F_i(x)`. If we take this perspective, then we should try to analyze the graphics of each `F_i`.

We know that `F_k(x) = f(x,k) = 0`, the graphic will just be a straight horizontal line.
The graphic for `F_(k-1)(x)` shall be more interesting. `F_(k-1)(x) = |e_(k-1) - x| + 0 = |e_(k-1) - x|`. Graphics of functions with absolute values work as follows:

So we can predict function `F_(k-1)` will be simple. How about `F_(k-2)`? `F_(k-2)(x)` requires us to find the maximum `F_(k-1)(x’)` such that `|x’ - x| <= d`. Then we add `|e_(k-2) - x|`, we can do it in parts. How about we define `g(x) = max( F_(k-1)(x’) )` this new function will have a graphic that is based on the graphic of: `F_(k-1)(x)`.

To this function, we add `|e_(k-2) - x|`, which is another absolute value function. That function and the resulting addition will look like this:

The nice thing is that now, we can use that addition as the graphic for `F_(k-2)(x)`. We can repeat this process for smaller `k`. For example, with `d_(k-3) = 1`, the `max( F_(k-2)(x’) : |x - x’| <= d_(k-3))`, function can be found using a similar logic as before:

The idea of this problem is to repeat these processes until we find `F_0(x)` and then it would be easy to pick the `x` with the maximum `F_0(x)` so we can pick it as the starting location and solve the problem. How can we do it efficiently?

Expand

The first operation we’ll consider is the one in which we find the function `g(x) = max(F_i(x’) : |x’ - x| <= d)`. We had a simple example in the second image and a more complicated example in the fourth:

In both cases, the logic used is the same. We find the maximum point of the function and then we shift the left-side of the function left and the right side of the function right - we expand the function. There are many details in this one. First of all, is it always correct?

Always concave

This approach should be true whenever the left side of the function is ascending from left to right and decreasing from right to left. A interval in which all values of `f(x)` are equal to the maximum is also allowed. We are describing a concave function. Certainly, if the function is concave (Its negative is convex), this approach works. Can we prove that the functions will always be concave before we expand them?

Initially, the function is a straight line equal to `y = 0`. Then for each `i`, we repeat the two processes: Expand and add. The expand operation requires the function to be concave. If the function is concave, it will remain concave after the expand operation. Then we add some `|x - e|` to the function. All functions in the form of `|x-e|` are concave. The sum of two concave functions is also concave. This means that after every step, the function will remain concave.

Polyline

How can we implement the expansion? An easy way is to consider the function as a polyline. The significant vertices are those in which the direction changes. The maximum `y` will be in one of these vertices. After we find the maximum `y` we can offset the `x` values of the vertices to the left and to the right of this top vertex. We also need to create a new vertex to duplicate the top value. In total we need `O(t)` steps to do this, where `t` is the number of vertices in the initial polyline.

Cut

An issue is that the expansion will usually move vertices of the polyline outside the `(0 <= x <= N)` interval. Those values of `x` would be invalid. We need to discard those, but we need the `y` values for `x = 0` and `N=0`, we might need to do interpolation to find them.

Add

The addition process is also easy when we see the function as a polyline.

The `y` value in each segment in the polyline increases by some `|e - x|`. We might also need to add a new significant vertex to the polyline, the one where `x = e`. If `x = e` was not a significant vertex in this polyline before the addition, we need to find its `y` value using interpolation.

Complexity and code

Each of the operations is `O(t)` where `t` is the number of vertices currently in the polyline. Operations usually add new vertices. Each expansion and add operation will increase the number of significant vertices by at most 1. Initially, there are 2 vertices. It follows that the number of significant vertices is `O(k)`, because we repeat the two processes `k` times. The total complexity is `O(k^2)`, which is good enough for topcoder’s servers because `(k <= 1000)`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
int N;
vector < int > x, y;

// Get py for a point (px,py) in segment (x0,y0)-(x1,y1).
int interpolate(long x0, long y0, long x1, long y1, long px) {
  return (int)(y0 + (px - x0) * (y1 - y0) / (x1 - x0));
}

// The "expand" operation.
// We have a function of pairs (x, dp[i+1][x])
// We want to find a function (x, max( dp[i+1][x1] : abs(x - x1) <= d) )
// Which translates into finding the maximum dp[i+1][x] and "expanding"
// its value d units left and d units right.
void expand(int d) {
  // Find the index bi with maximum y[]. The set of x with maximum y[] will
  // be an interval.
  int bi = 0;
  for (int i = 0; i < x.size(); i++) {
    if (y[i] > y[bi]) {
      bi = i;
    }
  }
  vector < int > nx, ny;

  // Function point(px,py) describes what to do in case we find a point (px,py) :
  auto point = [ & ](int px, int py) {
    nx.push_back(px);
    ny.push_back(py);
  };
  // Move smaller points d units left
  for (int i = 0; i <= bi; i++) {
    point(x[i] - d, y[i]);
  }
  // *Copy* bi d units right..
  if (d != 0) { //a corner case, when d = 0, don't add a point.
    point(x[bi] + d, y[bi]);
  }
  // Move larger points d units left
  for (int i = bi + 1; i < x.size(); i++) {
    point(x[i] + d, y[i]);
  }
  x = nx;
  y = ny;
}

// After expand() operations, we might need to cut the values of the function
// for x < 0 or x > N.    
void cut() {
  vector < int > nx, ny;
  // function point(px,py) to add a point to the list whenever we find it:
  auto point = [ & ](int px, int py) {
    nx.push_back(px);
    ny.push_back(py);
  };

  for (int i = 0; i < x.size(); i++) {
    // x[i] within bounds, include this point.
    if (0 <= x[i] && x[i] <= N) {
      point(x[i], y[i]);
    }
    // If 0 was between x[i] and x[i+1], it means we need to cut the function
    // We interpolate to find the value of y for x=0.
    if ((i + 1 < x.size()) && (x[i] < 0 && 0 < x[i + 1])) {
      point(0, interpolate(x[i], y[i], x[i + 1], y[i + 1], 0));
    }
    // Same with x = N
    if ((i + 1 < x.size()) && (x[i] < N && N < x[i + 1])) {
      point(N, interpolate(x[i], y[i], x[i + 1], y[i + 1], N));
    }
  }
  x = nx;
  y = ny;
}

// The "add" operation.
// We want to create a function of pairs (x, dp[i][x])
// We already know the maximum (dp[i][x1] : abs(x1 - x) <= d) for each x.
// (The maximum score we can get *after* event i if we start event i at point x.
// To each of those maximums add N + abs(e - px). 
void add(int e) {
  vector < int > nx, ny;
  // function to add abs(e - px) to each point (px,py) we find in function:
  auto point = [ & ](int px, int py) {
    nx.push_back(px);
    ny.push_back(py + N - abs(e - px));
  };

  // We should add N + abs(e - px) to all points in the function.
  // Also need to include point x = e, if it doesn't already exist.
  for (int i = 0; i < x.size(); i++) {
    point(x[i], y[i]);
    // If x = e is not in the function, use interpolation to find its
    // y value and add it:
    if ((i + 1 < x.size()) && (x[i] < e && e < x[i + 1])) {
      point(e, interpolate(x[i], y[i], x[i + 1], y[i + 1], e));
    }
  }
  x = nx;
  y = ny;
}

// Solves for x:
int getMaximumGoldX(int N, vector < int > e, vector < int > d) {
  assert(e.size() < 100);
  this - > N = N;
  x = {
    0,
    N
  };
  y = {
    0,
    0
  };

  // The dynamic programming:
  for (int i = e.size() - 1; i >= 0; i--) {
    add(e[i]);
    if (i > 0) {
      expand(d[i - 1]);
      cut();
    }
    cout << i << endl;
  }
  return * max_element(y.begin(), y.end());
}

int GetMaximumGold(int N, int M, vector < int > event_i, vector < int > event_j, vector < int > event_di, vector < int > event_dj) {
  return getMaximumGoldX(N, event_i, event_di) +
    getMaximumGoldX(M, event_j, event_dj);
}