SRM 600

Match Summary

Round Overview
Discuss this match

Would you believe it? It is SRM # 600. The nostalgic in this SRM writer has been mislead to believe that SRM 500 happened just recently, but apparently it has been 2.5 years. Time flies when you are writing editorials. This important milestone was celebrated in full. t-shirts were offered. Cash prizes were offered. Topcoders from all the world wanted a t-shirt and put their full effort.

TheShuttles

Used as: Division Two - Level One:

By the problem’s constraints, the maximum number of passengers for a location is 100. The shuttle size must be a integer and it wouldn’t be helpful for the shuttle size to be larger than the number of passengers in all locations. It follows that the shuttle size should be a number between 1 and 100, inclusive. We can just try each of these possible values and find the one that gives the best result.

The remaining issue is to, given a shuttle size `x` , and a number `c` of passengers for a location. Calculate the number of shuttles that are needed for this location. Usually you’d divide `c / x`. If the division is uneven, an extra shuttle is needed for the remainder passengers. In effect, we do `m = |<sub>c/x</sub>|`, or division rounding-up. The total number of shuttles `n` will be the sum of all `m` values we find for each location.

For each of the `m` shuttles, the cost increases by `“baseCost” + X * “seatCost”`. The total cost is therefore: `n times (“baseCost” + X * “seatCost”)` . We are ready to code:

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int getLeastCost(vector < int > cnt, int baseCost, int seatCost) {
  // initialize res with a big number. Since we know result fits a integer,
  // let's use the largest integer of them:
  int res = numeric_limits < int > ::max();
  // For each number of seats x:
  for (int x = 1; x <= 100; x++) {
    // calculate number of shuttles
    int n = 0;
    for (int c: cnt) {
      // (c + (x - 1)) / x gives the ceil(c/x), c/x rounded up. Try it.
      n += (c + (x - 1)) / x;
    }
    // and the cost
    int cost = n * baseCost + n * x * seatCost;
    // remember the minimum:
    res = std::min(res, cost);
  }
  return res;
}

python

1
2
3
4
5
6
7
8
9
10
11
class TheShuttles:
  def getLeastCost(self, cnt, baseCost, seatCost):
  # calculate cost given x:
  def cost(x):
  n = sum(m / x + (m % x != 0) for m in cnt) # ** see below
return n * (baseCost + x * seatCost)

# find the x that yields the minimum cost
return min(cost(x) for x in range(1, 101))

# ** (m % x != 0) is 1 whenever m is not a multiple of x

ORSolitaireDiv2

Used as: Division Two - Level Two:

At most 20 cards

This very important constraint means that there at most `2^20` subsets of cards, more than one million. The division 1 version will show the way to solve this problem in polynomial time. In this explanation though, we will simply use the following logic: Generate all sub-sets and for each subset, test if removing the cards in that subset will make it impossible to reach the goal. Pick the smallest set that makes the goal impossible to reach.

Given a set

Once the set of cards that will be removed is fixed, we need to know if it is possible or not to reach the goal after we remove those card.
It is useful to notice that some cards are never helpful. Consider goal = 11001 and a card = 10101:

1
2
goal = 11 ** 0 ** 01
card = 10 ** 1 ** 01

If we did X = X or 10101, and X became 00100, we would not be able to reach the goal anymore. There is a bit position in which the card has 1 and goal has 0. The OR bit operation can only add ‘1’ bits, never remove them. Whether a card is invalid to use or not depends solely on the goal and not the current value of X. This means that the card will never be valid, it also means that the cards that don’t have this issue will always be valid. Regardless of the current value of X.

The only valid cards are those that have ‘0’ bits in positions that have ‘0’ in goal. An OR operation can only add ‘1’ bits to X. So an optimal strategy is to always OR all valid cards together. The OR of all valid cards is equal to the goal if and only if the problem is solvable with the given set of available cards.

Solutions

• Generate all subsets of cards

• For each set, if after removing those cards, the OR of all the valid cards is < goal, the subset is a good one to remove.

• Return the size of the minimum good subset.

To search for all the subsets of cards you can use backtracking. It is common to use bitmasks because of the short, yet hard to understand code they result in. Another option would be to use the language’s libraries if available e.g., c++ has next_permutation and Python has itertools.combinations, which could be used if you first fix the number of elements of the set

C++ - backtracking

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
int getMinimum(vector < int > numbers, int goal) {
  int n = numbers.size();
  int res = n; // worst case: remove n cards

  // Decided to use a c++11 lambda to avoid using class attributes/globals,
  // sorry about that:
  function < void(int, int, int) > backtrack = [ & ](int p, int X, int removed) {
    // p: next card to remove or not
    // X: current OR value of remaining valid cards
    // removed: total number of removed cards.
    if (p == n) {
      res = std::min(res, removed);
    } else {
      if ((goal | numbers[p]) != goal) {
        // ignore:
        backtrack(p + 1, X, removed);
      } else {
        if (removed + 1 < res) {
          // remove:
          backtrack(p + 1, X, removed + 1);
        }
        // don't remove:
        if ((X | numbers[p]) != goal) {
          backtrack(p + 1, X | numbers[p], removed);
        }
      }

    }

  };
  backtrack(0, 0, 0);
  return res;
}

The good thing about backtracking is that it allows us to crop the search. This solution neeeds 8ms in the worst case.

Java - bitmasks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ORSolitaireDiv2 {
  public int getMinimum(int[] numbers, int goal) {
    int n = numbers.length;
    int res = n; //worst case scenario: remove all cards.

    // for each subset of removed cards:
    for (int mask = 0; mask < (1 << n); mask++) {
      // Get OR of valid , remaining cards:
      int X = 0;
      for (int i = 0; i < n; i++) {
        if (((mask & (1 << i)) == 0) && ((numbers[i] | goal) == goal)) {
          X |= numbers[i];
        }
      }
      // If it is impossible, remember the least number of removed cards:
      if (X != goal) {
        res = Math.min(res, Integer.bitCount(mask));
      }

    }
    return res;
  }
}

C++ - next_permutation

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
int getMinimum(vector < int > numbers, int goal) {
  int n = numbers.size();

  for (int r = 0; r < n; r++) {
    // to use next permutation, array initially must be:
    // (n - r) zeros followed by r ones:
    int remove[n];
    for (int i = 0; i < n; i++) {
      remove[i] = (n - i - 1 < r);
    }
    do {
      // get the OR of all valid, remaining cards:
      int X = 0;
      for (int i = 0; i < n; i++) {
        if ((!remove[i]) && ((numbers[i] | goal) == goal)) {
          X |= numbers[i];
        }
      }
      if (X != goal) {
        return r;
      }
    } while (next_permutation(remove, remove + n));
  }
  return n;
}

Python - itertools.combinations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class ORSolitaireDiv2:
  def getMinimum(self, numbers, goal):
  # define an OR
function:
def OR(a, b):
  return a | b

# Get rid of invalid cards:
  numbers = [y
    for y in numbers
    if (goal | y == goal)]

n = len(numbers)
#
for each i = number of removed cards:
  for i in range(n):
  #
try all the combinations of n - i remaining cards(after removing i cards)
for rem in itertools.combinations(numbers, n - i):
  # Get the OR of all valid remaining cards: reduce() helps apply OR
# to all cards.
if reduce(OR, rem) != goal:
  return i
return n

PalindromeMatrixDiv2

Used as: Division Two - Level Three:

Care only about the palindrome rows and columns

A key aspect of this problem is that it requires at least `r = “rowCount”` rows and `c = “columnCount”` columns to be palindrome. The at least part simplifies our search, because if doesn’t matter if the remaining rows/columns are palindrome or not - We can just pick the special `r` rows and `c` columns and the condition can ignore the rest of the cells.

There are `((n),®)` ways to pick the `r` rows and `((m),©)` ways to pick the `c` columns (Where `((n),(k))` is the binomial coefficient, `n` is the total number of rows and `m` the total number of columns). With `n,m <= 8`, the worst number `((m),©) = ((8),(4)) = 70`, so there are at worst 70 different ways to pick the palindrome rows. There are also at worst 70 different ways to pick the palindrome columns. A combined choice of palindrome rows and columns would have at worst 70*70 = 4900 options. Let’s iterate through all these options and find, for each of them, the minimum cost to make those columns and rows palindrome. Then just show the minimum result out of every possible pick.

To search for all the combinations of palindrome columns and rows you can use backtracking. You can also use bitmasks to iterate through all the subsets of columns/rows and caring only about the ones with exactly `r` and `c` columns. Another option would be to use the language’s libraries if available, c++ has next_permutation which could be used on a list of `r` elements equal to 1 and `n-r` elements equal to 0; Python has itertools.combinations.

Minimum cost for a specific case

After we decide the `r` rows and `c` columns to be palindrome, we need the minimum cost to do so.

In one dimension

Let’s first understand how the palindrome condition works in a single dimension. For example, what’s the minimum cost to turn “10010101” to palindrome? The resulting string needs the following conditions to be true:

• `B_0 = B_7`

• `B_1 = B_6`

• `B_2 = B_5`

• `B_3 = B_4`

For each of the pairs `(i, n-i-1)`, you find that `B_i = B_(n-i-1)`, which means that you need the minimum cost to turn `A_i` and `A_(n-i-1)` equal. In this specific case, the cost is 2, because `A_2 != A_5` and `A_3 != A_4`.

Two dimensions

In two dimensions, the logic ought to be more complicated. Let’s try an example:

1
2
3
4
1010
0101
0101
1010

Assume that we decided that column 2 and row 2 must be palindrome. The following conditions need to apply in the final matrix for row 2:

• `B_20 = B_23`

• `B_21 = B_22`

For column 2:

• `B_02 = B_32`

• `B_12 = B_22`

If `B_12 = B_22` and `B_21 = B_22` then we can conclude that also `B_12 = B_21`.

There are various groups of cells in which all cells in the group must be equal. We can find the maximal groups possible. First solve the cells involved in: `B_12 = B_22 = B_21`. The three cells must be equal. We currently have: `A_12 = 1, A_22=0, A_21=1`. The minimum cost to turn all these cells equal is 1 (Change 0 to 1). In general, the minimum cost will be equal to the minimum between the number of cells with 0 and the number of cells with 1 (So you change this minimum group to the other value).

For the remaining groups, we have simple conditions like: `B_20 = B_23`. Do the same, initially `A_20 = 0` and `A_23 = 1`, so the cost is 1. There are cells that don’t participate in any condition, but we can assume them to belong to groups of exactly one element. Like `A33` must be equal to itself. Currently `A_33= 0` so there are no '1’s in this group and the minimum cost is 0.

In general

In general, it is all about finding these groups of cell that must contain only equal numbers. The useful reduction is to consider the cells as vertices and the = relationship as edges in a graph. This way the groups of cells that must be equal are connected components. We find each connected component in the graph, we can use a Depth-first-search (DFS) to visit all the nodes connected to each node we find. Let’s define the edges:

• Cell `(i,j)` is connected to cell `(n-i-1, j)` if column `j` is palindrome (`B_ij = B_(n-i-1)j`).

• Cell `(i,j)` is connected to cell `(i, m-j-1)` if row `i` is palindrome.

The DFS needs `O(|V| + |E|)` time where `|V|` is the number of vertices and `|E|` the number of edges. In this case, there are `O(nm)` vertices and each of them has at most 2 edges, so the DFS will be `O(nm)`. We repeat this DFS at most 4900 times.

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
int minChange(vector < string > A, int rowCount, int columnCount) {
  int n = A.size(), m = A[0].size();
  int pcols[m];
  int prows[n];
  int res = n * m;
  // for use with next_permutation, pcols is initially: {0,0,...,0, 1,1,...1 }
  for (int i = 0; i < m; i++) {
    pcols[i] = (m - i - 1 < columnCount);
  }
  do {
    // for use with *nested* next_permutation,
    // prows is initially: {0,0,...,0, 1,1,...1 }
    for (int j = 0; j < n; j++) {
      prows[j] = (n - j - 1 < rowCount);
    }
    do {
      // did you know? Only 4900 ways to do this.
      int cost = 0;
      bool visited[8][8];
      memset(visited, false, sizeof(visited));
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          if (!visited[i][j]) {
            int o = 0, z = 0;
            // A iterative version of DFS:
            // count the number o of '1's and number z of '0's
            //  in the connected component that contains (i,j)
            stack < int > S;
            S.push(i);
            S.push(j);
            while (!S.empty()) {
              // (x,y) is connected to (i,j):
              int y = S.top();
              S.pop();
              int x = S.top();
              S.pop();
              if (!visited[x][y]) {
                // We didn't process it before:
                z += (A[x][y] == '0');
                o += (A[x][y] == '1');
                visited[x][y] = true;
                if (pcols[y]) {
                  // (n - x - 1, y) is connected to (x,y):
                  S.push(n - x - 1);
                  S.push(y);
                }
                if (prows[x]) {
                  // (x, y) is connected to (x,m - y -1):
                  S.push(x);
                  S.push(m - y - 1);
                }
              }
            }
            cost += min(o, z);
          }
        }
      }
      res = std::min(res, cost);
    } while (next_permutation(prows, prows + n));
  } while (next_permutation(pcols, pcols + m));
  return res;
}

At most 4 connected cells

Perhaps the DFS only complicates things. Something to notice about the graph is that a connected component has at most 4 cells. The cells are: `(i,j)`, `(n-i-1,j)`, `(n-i-1,m-j-1)` and `(i,m-j-1)`. For each cell `(i,j)` with `(i < n/2)` and `(j < m/2)` , we can calculate the minimum cost using the four cells that were mentioned and the knowledge of whether or not rows `i` and `n-i-1` are palindrome and columns `j` and `m-j-1` are palindrome. Depending on the palindrome decision, two cells in the same row or column have to be equal. If at most one of the rows/columns is not palindrome, all of the four cells have to be equal. Else there are 4 cases in which 3 cells are equal and the rest are cases in which you can treat the rows and columns individually. You can find example code for this idea in the explanation for the division 1 version of the problem.

ORSolitaire

Used as: Division One - Level One:

From the division 2 version explanation, we can learn that the optimal strategy once some cards are removed, is to OR all the valid cards that remain.

Let’s discard invalid cards and assume that all cards are valid. All the cards that are not removed will participate in the OR. The question is now to remove the minimum number of cards so that the OR result is not goal.

Since all cards are valid (Have 0 bits in all positions where goal has 0 bits). The only way to have a total OR different to goal is that at least one of the bit positions that have ‘1’ in goal have ‘0’ in the OR result.

In order for the total OR to have ‘0’ in a bit position, we need to remove all the cards that have ‘1’ in that position. If at least one card with ‘1’ remained, the OR would still have ‘1’.

Therefore, we should just find the bit position that is ‘1’ in goal and that has the minimum number of cards with ‘1’ in it. Remove all those cards, and that is the minimum number of cards we should remove.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int getMinimumPoly(vector < int > numbers, int goal) {
  int res = numbers.size();
  // For each bit position, numbers in input have at most 31 relevant bits: 
  for (int i = 0; i < 31; i++) {
    // If the goal has this bit position as 1.
    if (goal & (1 << i)) {
      // remove all valid numbers with this bit
      int c = 0; // count them
      for (int x: numbers) {
        if ((x & (1 << i)) && ((goal & x) == x)) {
          c++;
        }
      }
      res = std::min(res, c);
    }
  }
  return res;
}

Remember the backtracking solution shared for the division 2 version? It turns out that it passes the system tests with 0.5 seconds of worst-case time.

PalindromeMatrix

Used as: Division One - Level Two:

From division 2

This explanation is meant as a continuation to the explanation used for the division 2.

The larger constraints

With `n,m <= 14`, the simple solution to just decide the palindrome rows/columns and then finding the minimum cost is not going to work very well. However, the number of ways to decide the palindrome columns is still not very large. The worst `((m),©)` is equal to `((14),(7)) = 3432`. How about we try to find, for this selection of palindrome columns, the minimum cost to make `r` palindrome rows in addition of making those columns palindrome? Call the set of palindrome columns `P`.

Dynamic programming

Similar to palindrome problems that use one dimension. When deciding the contents of the rows, we can use the following order:

• First decide row 0 and row `n-1`.

• Decide row 1 and row `n-2`.

• …

• Decide row `n/2-1` and row `n/2`. (Note that `n` is guaranteed to be even).

If we decide the rows in this order and make sure that for each palindrome column `j: j in P` : cell `(i,j)` is equal to cell `(n-i-1, j)` for all the rows `i`, `n-i-1` that were already filled.

Let’s make a function `f(i, r)` which finds the minimum cost to fill the rows other than the first `i` rows and the last `i` rows. Such that `r` rows of the not-filled ones must be palindrome and for each column `j in P`, the final column is palindrome.

The trick in this case is to consider that for `f(i,r)`, there are 3 things we can do with the two rows: `i` and `n-i-1`:

• Do not bother about the rows, they can be palindrome or not, `r` does not change.

• Worry about one of the rows, one of them must be palindrome. `r` is decreased by 1.

• Worry about both rows, make both palindrome. `r` is decreased by 2.

Let’s assume we can find the cost: `“cost”(i,k)` to fill the rows `i` and `n-i-1` in such a way that at least `k` of the rows are palindrome. Then the dynamic programming part is easy to solve:

• Base case: `f(i = n/2, r)`, this means that all the row were already filled. Since we cannot fill more rows, `r` must be 0, in that case, there is nothing more to do, the whole matrix is correct and the minimum cost is 0. In the unfortunate case `r != 0`, there is nothing we can do to fix the matrix, let’s make the minimum cost in this case `oo`, infinite so that the case is marked as invalid.

• Else we decide how to fill rows `i` and `n-i-1`, if `k` of them are palindrome, the minimum cost is: `“cost”(i,k) + f(i+1, r-k)`. We just need to find the minimum of those costs for the valid values of `k` (`r - k >= 0)`.

Simply use dynamic programming, there are `O(nr)` states for `f(i,r)`. We can solve this recurrence in `O(nr)` time.

Minimum cost to fill two rows

The final challenge is to find the `“cost”(i,k)"` function. Find the minimum cost to fill rows `i` and `n-i-1` in such a way that `k` of them are palindrome. In addition, remember there is a set `P` of palindrome columns, so for each `(j in P)`, we need cell `(i,j)` to be equal to `(n-i-1,j)`.

There are four possibilities:

• Neither rows `i` and `n-i-1` have to be palindrome.

• Only row `i` has to be palindrome.

• Only row `n-i-1` has to be palindrome.

• Both rows `i` and `n-i-1` have to be palindrome.

We can just find the minimum cost for each of these 4 cases. This yields the following sub-problem: We have a matrix consisting of two rows. A set of rows that must be palindrome and a set of columns that must be palindrome. Find the minimum cost. So now we have a small instance of the same sub-problem that we solved in the division-2 version. This time with at most `2 time m` cells.

Complexity analysis and code

The total complexity will be: `O( ((m),©) times ( nr + nm) )`. For each of the `O( ((m),©) )` ways to pick the palindrome columns, we need a `O(nr)` dynamic programming and to calculate the cost function. The cost function needs to be calculated `O(n)` times calculating each cost function needs `O(m)`, because the new matrix has `2xm` elements, and we repeat the calculation 4 times.

This time we’ll use bitmasks to generate the set of palindrome columns and we’ll use the case by case basis to find the minimum cost to solve the `2 times m` special matrix.

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
131
132
133
int subProblem2x2(bool p0, bool p1, bool q0, bool q1) {
  // minimum cost to change a[][] such that:
  // All in row 0 is equal <==> p0
  // All in row 1 is equal <==> p1
  // All in col 0 is equal <==> q0
  // All in col 1 is equal <==> q1
  int o = 0;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      o += (a[i][j] == '0');
    }
  }

  if (p0 + p1 + q0 + q1 >= 3) {
    // If at most one of the rows/columns is not palindrome, then all the
    // cells must be equal.
    // Try it: a = b, c = d, Adding (b = d) or (a = d) will make all the variables equal
    return min(o, 4 - o);
  }
  // In the following cases, we have a row and a column that must be palindrome
  // Make the pattern:
  // ##   a = b, b = c -> a = b = c
  // .#
  //
  if (p0 && q0) {
    o -= (a[1][1] == '0');
    return min(o, 3 - o);
  }
  if (p0 && q1) {
    o -= (a[1][0] == '0');
    return min(o, 3 - o);
  }
  if (p1 && q0) {
    o -= (a[0][1] == '0');
    return min(o, 3 - o);
  }
  if (p1 && q1) {
    o -= (a[0][0] == '0');
    return min(o, 3 - o);
  }
  // The rows and columns don't intersect, so if a row/column must be
  // palindrome, only the two cells in it matter.
  int res = 0;
  if (p0) {
    res += (a[0][0] != a[0][1]);
  }
  if (p1) {
    res += (a[1][0] != a[1][1]);
  }
  if (q0) {
    res += (a[0][0] != a[1][0]);
  }
  if (q1) {
    res += (a[0][1] != a[1][1]);
  }
  return res;
}
// Note that we could still use the same DFS as in division 2 to solve this problem.

const int INF = 14 * 14;

int withPalindromeColumns(const vector < string > & A, int rowCount, int mask, int m, int n) {
  int minCost[n / 2][3];
  for (int i = 0; i < n / 2; i++) {
    // find the minimum cost to have:
    // B[i][j] = B[h - i - 1][j] , for each j in mask.
    // and
    // a) No extra condition                                     -or-
    // b) At least 1 of B[i] or  B[n - i - 1] is palindrome      -or-
    // c) B[i] and B[n - i - 1] are palindromes
    for (int j = 0; j < 3; j++) {
      minCost[i][j] = 2 * m;
    }

    for (int p1 = 0; p1 < 2; p1++) {
      for (int p2 = 0; p2 < 2; p2++) {
        int res = 0;
        for (int j = 0; j < m / 2; j++) {
          bool q1 = (mask & (1 << j));
          bool q2 = (mask & (1 << (m - j - 1)));
          a[0][0] = A[i][j];
          a[0][1] = A[i][m - j - 1];
          a[1][0] = A[n - i - 1][j];
          a[1][1] = A[n - i - 1][m - j - 1];
          res += subProblem2x2(p1, p2, q1, q2);
        }
        int s = p1 + p2;
        minCost[i][s] = std::min(minCost[i][s], res);
      }
    }
  }

  int dp[n / 2 + 1][rowCount + 1];

  // dp[i][r] : Minimum cost to solve if:
  // * Columns in set "mask" must be palindrome.
  // * the i first rows and the i last rows were already modified and they
  //   have appropriate values to ensure the columns in that set are palindrome.
  // * At least r of the rows not filled yet must be palindrome.

  // Base case, when i = n/2 :        
  for (int r = 1; r <= rowCount; r++) {
    // we cannot fill any more rows, and not enough of them were palindrome
    dp[n / 2][r] = INF;
  }
  dp[n / 2][0] = 0;
  for (int i = n / 2 - 1; i >= 0; i--) {
    for (int r = 0; r <= rowCount; r++) {
      dp[i][r] = INF;
      // fill the i-th first row and the i-th last row. 
      //   p = number of rows out of those two that will be palindrome.
      for (int p = 0; p < 3 && r - p >= 0; p++) {
        int x = minCost[i][p] + dp[i + 1][r - p];
        dp[i][r] = std::min(dp[i][r], x);
      }
    }
  }
  return dp[0][rowCount];
}

int minChange(vector < string > A, int rowCount, int columnCount) {
  int m = A[0].size(), n = A.size();
  int res = INF;
  // pick a set of columns         
  for (int mask = 0; mask < (1 << m); mask++) {
    // care only about sets that have columnCount columns:
    if (__builtin_popcount(mask) == columnCount) {
      res = std::min(res, withPalindromeColumns(A, rowCount, mask, m, n));
    }
  }

  return res;
}

LotsOfLines

Used as: Division One - Level Three:

Areas and intersections

A key step is to notice the following: Assume there are already some lines dividing the plane and that we add a new line. After adding this new line, the number of areas will increase.

The number of new areas is always exactly to [1 + number of unique intersections with previous lines]. Note that some of the previous lines may be parallel to the new line and have no intersection with it. Also, multiple lines may intersect with the new line in the same point. We only count this point once.

The solution will be to start with one area and then add the lines one by one in row-major order of `(a,b)` pairs. Each time we add a new line, count the number of points in which the previous lines intersect with it and increase the number of areas by 1 + number of intersections.

All those equation systems

Let’s now count the number of intersections after adding line represented by pair `(a,b)`. This means the equation is: `y = ax + b`. Note that because they have the same slope, there cannot be intersections between line `(a,b)` and any other line with smaller value of `b`. Therefore, we need to worry only about lines represented by pair `(alpha,beta)` where `(alpha < a)` and `(beta < B)`. Let’S solve the system of equations:

`y = a x + b`
`y = alpha x + beta`
`->`
`x = (beta - b) / (a - alpha)`

We can say the value of `x` is a number `p / q`. `(p = beta - b)` where `0 <= beta < B`. Which means `(-b <= p < B - b)`. A similar analysis yields: `(1 <= q <= a)`. Each unique value of `x` equal to `p / q` where `p` and `q` are valid represents a unique intersection `(x, ax+b)`, so we just need to count the number of unique values in this set.

Unique values

Count the number of unique values `p/q` where `(-b <= p < B - b)` and `(1 <= q <= a)`. Since `(q > 0)`, the sign of `p/q` depends on `p` , which can vary. Let us solve positive, negative and zero values separately.

Zero

When `p = 0`, the value of `q` does not matter, the result will always be `p / q = 0`. We should need to know if `p = 0` is included in the set of allowed values. We need condition: `(-b <= 0 < B - b)` to be true:

`(-b <= 0) -> (b >= 0)`
`(B - b > 0) -> (b < B)`

Which means `0` is a valid `p` if and only if `(B > 0)`, which appears to be all the time. Note also that at least a value of `q` must exist: `(1 <= q <= a)` means that whenever `(a = 0)`, this intersection is not possible (or any other)`.

Positive p

When `(0 < p < B - b)`, we have a positive value for `p / q`. We’d like to count the unique values. What makes some values repeated? Consider two pairs `(p_1, q_1)`, `(p_2, q_2)` Assume `p_1 / q_1 = p_2 / q_2`, this can actually only happen if there is a `k` such that: `p_1 = kp_2`, `q_1 = kq_2` (or vice versa). When counting the unique `p/q`, we should consider only the pairs `(p,q)` when `p` and `q` are coprime / have a gcd equal to 1.

The problem can be rephrased to: Count the number of pairs `(p,q)` where: `gcd(p,q) = 1` , `(0 < p < B - b)` and `(0 < q <= a)`.

Negative p

When `(-b <= p < 0)`, `p` is a negative number. The issue is otherwise the same. `-2/4 = -1/2`. So we can multiply `p` by -1, and now we have fractions `(p’)/q` where `(0 < p <= b)`. The problem is rephrased to: Number of pairs `(p,q)` where: `gcd(p,q) = 1` , `(0 < p < b + 1)` and `(0 < q <= a)`.

Counting co-prime pairs

Both cases lead us to the same sub-problem in which we count pairs `(p,q)` that are pair-wise coprime and the values of both `p` and `q` have upperbounds.

The solution to this sub-problem is to imagine a table of `A times B` dimensions where each cell `(x,y)` has `1` if `(gcd(x,y)=1)` or `0` otherwise. It is simple to fill this table in `O(AB log(max(A,B)))` time using the Euclidean algorithm. After filling this table, it is also simple to make a table of accumulated sums that we can query in `O(1)` to find the total number of `1` in a sub-square of the table.

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
int sum[1200][1200];

int gcd(int a, int b) {
  while (a != 0) {
    int c = a;
    a = b % a;
    b = c;
  }
  return b;
}

long countDivisions(int A, int B) {
  // Precalculate sum[x][y], sum of coprime pairs:
  //  (p,q) (1 <= p <= x), (1 <= q <= y)   
  for (int i = 1; i < A; i++) {
    for (int j = 1; j < B; j++) {
      int x = ((gcd(i, j) == 1) ? 1 : 0);
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + x;
    }
  }
  long ans = 1;
  for (int a = 0; a < A; a++) {
    for (int b = 0; b < B; b++) {
      // Always at least one new area
      ans++;
      if (a != 0) {
        // 1 : Intersection p/q = 0
        // sum[a][b] : Intersections x = p/q with negative p
        // sum[a][B-1-b] : Intersections x = p/q with positive p
        ans += 1 + sum[a][b] + sum[a][B - 1 - b];
      }
    }
  }

  return ans;
}