SRM 589

Match Summary

Round Overview
Discuss this match

SRM 589 was the fifth problem set contribute by snuke. There was no shortage of interesting yet approachable problems in this match. The division 1 easy problem, was a greedy one that required a graph theory analysis to work. Less than a half of the coders solved this problem correctly. The second problem, required some creative simplifications to turn into a theory-reliant graph theory problem. Around a fifth of the coders could solve this one. Including Egor who got a very fast submission in 7.5 minutes. The hard problem was an easier than usual but still interesting one that required you to be creative and split it into two variations, each with its own specialized solution. Veteran topcoder bmerry got the fastest score in this hard problem with 18 minutes. That feat, in addition with great scores in the other problems and 150 challenge points gave bmerry a solid division win. The second place went to Petr and a very close third place to niyaznigmatul.

GooseTattarrattatDiv2

Used as: Division Two - Level One:

A string of a single letter

The objective is to make all letters equal. This means that the final string will have the same letter repeated n times.

Choosing the letter

We should pick one letter so that all the letters in the string become it. If we chose letter ch:

• For every letter q in the string that is not equal to ch, we need a step to convert all the letters equal to q into ch. This has a cost equal to the number of letters equal to q.

• The letters equal to ch do not need to be changed.

The best letter

Of all the options we have, we should pick the one that yields the smallest cost. From the previous analysis, note that each of the letters different to ch need to be modified and increase the cost. It is the ones that are equal to ch that don’t increase the cost. Therefore, we should pick the letter ch that appears the maximum number of times in S.

If the most frequent letter appears m times in S, all the (n - m) other letters need to be modified. This is the final result: n minus the number of times the most frequent letter appears.

c++ example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int getmin(string S) {
  int n = S.length(), m = 0;
  for (char ch: S) { // For each letter in S
    // Count the number of times it appears
    int c = 0;
    for (int i = 0; i < n; i++) {
      if (S[i] == ch) {
        c++;
      }
    }
    // remember the maximum
    m = std::max(m, c);
  }
  return n - m;
}

python example

1
2
3
4
5
class GooseTattarrattatDiv2:
  def getmin(self, S):
  return len(S) - max(S.count(ch) for ch in S)

#(find the letter that appears the maximum number of times in S # subtract that number from the length)

GearsDiv2

Used as: Division Two - Level Two:

The string and the conditions

We have a string like LRLLRLLRRRRL, we need to remove some of the gears. But removing the gears does not change the positions, so we are actually replacing the gears / characters with empty spaces. The final string should be one in which no two consecutive characters are equal, unless they are both empty spaces. The condition should also apply to the first and last characters in the string.

Cycles are annoying

We should try to get rid of the cycle logic in the problem. Consider the first and last character in the string. We can choose to remove or keep each of them. There are only 4 possibilities for this.

• Keep both characters: This is only possible if they are not equal. Then we are left with a string like LLRLLRLRLR since the first and last character are not equal, we do not need to worry about that condition, any further removal should consider only consecutive characters. This is a linear (non-circular) version of the problem.

• Remove one of the characters: E.g: From LLRLLRLRLR to -LRLLRLRLR. What is left of the string is another case of a string in which the extreme ends do not matter anymore: “LRLLRLRLR”, so we just need to literally remove the character.

• Remove both of the end characters. E.g: From LLRLLRLRLR to -LRLLRLRL-. The new string, the middle “LRLLRLRL” is another linear version of the problem. In reality, it can be shown that it is not necessary to try this case. Once we remove one of the end characters, if the linear problem requires us to remove the other one, our algorithm to solve the linear problem will decide to remove it.

We can just try the three options available: Remove one character or don’t remove any. For each of these options, solve the linear version of the problem. Return the best result out of the 3 options.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def getmin(Directions):
  n = len(Directions)
res = n - 1 # in the worst
case we 'd remove all but one gear

if (Directions[0] != Directions[n - 1]):
  res = getminLinear(Directions) #leave both extreme letters

#(getminLinear solves the linear version of the problem)

res = min(res, 1 + getminLinear(Directions[1: ])) # remove the first letter
res = min(res, 1 + getminLinear(Directions[: n - 1])) # remove the last letter
return res

class GearsDiv2:
  getmin = staticmethod(getmin)

Linear problem

So now we have a string of gears like LRLRLLLRLRL , we do not want to consecutive letters to be the same unless they are both -. What is the minimum number of times we need to replace a character with -?

If there were less than 2 characters in the string, then there is nothing we need to do. We can simply return 0 as no removals are needed.

In the other case, consider the first two characters. Two possibilities:

• They are equal. If the first two characters are equal, we need to remove at least one of them.

  • What happens if we remove the first one? This may not be the best strategy. Consider this string: “RRR”, if we remove the first R, the second R is still disrupting the third one. So it is better to remove the second R.

  • Thinking about it, it should always be better to remove the second letter. It will remove the first conflict and also remove the second conflict (if it exists) or at least leave things the same way. e.g: RRXXXXXXXX, if we remove the second R we are left with: R-XXXXXXXX, the R and XXXXXXXX are now independent. XXXXXXXX is now a smaller instance of the linear problem, and we can try to solve it using the same strategy. This move is always at least as good as removing the first letter: -RXXXXXXXX, in this case we do not know for sure if it will be necessary to remove R.

• They are different. We have two options:

  • Remove the first letter. But this is probably a bad idea. We have a string like LRXXXXXXXXX, if we remove the first letter, we will have: -RXXXXXXXXX. What does this accomplish? If we needed to remove R, it would be because of the XXXXXXXXX section, and removing the L didn’t affect it.

  • So we should just choose not to remove the first letter. From LRXXXXXXXXX, we know that we can just ignore the first letter. So now we just need to solve RXXXXXXXXX, a smaller instance of the problem.

Just like that, we have designed a recursive greedy approach to solve the linear problem. It looks like this:

1
2
3
4
5
6
7
8
9
10
11
    def getminLinear(Directions):
      n = len(Directions)
    if n <= 1:
      return 0 # nothing to do
          elif Directions[0] == Directions[1]:
          # they are equal.Remove the second one, solve the new independent
        case
        return 1 + getminLinear(Directions[2: ])
    else:
      # not equal, ignore the first letter:
      return getminLinear(Directions[1: ])

This is recursive, but it does at most one recursive call in each step, so we can estimate that the function is called a total of `O(n)` times. Removing the characters and may need `O(n)` time, so the total is `O(n^2)`.

Iterative version

Some coders may not like recursion, we can implement the same algorithm iteratively and with a `O(n)` complexity because we do not need to literally remove the characters from the string:

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 getmin(string Directions) {
      int n = Directions.size();
      int res = n - 1; //In the worst possible case, we need to remove all but one gear 

      for (int r1 = 0; r1 < 2; r1++) { //remove the first gear?
        for (int r2 = 0; r2 < 2; r2++) { //remove the second gear?
          if (r1 == 0 && r2 == 0 && Directions[0] == Directions[n - 1]) {
            // We cannot leave both extreme letters unremoved if they are equal
            continue;
          }

          int cost = r1 + r2;
          int i = r1; //start at the specified letter 
          while (i + 1 < n - r2) { //while there are 2 letters 
            if (Directions[i] == Directions[i + 1]) {
              cost++; // remove the second next letter 
              i += 2; //ignore the next two letters 
            } else {
              i++; //ignore the next letter.
            }
          }
          res = std::min(res, cost);
        }
      }
      return res;

    }

Alternative solutions and additional comments.

There is also a dynamic programming approach described in the forums.

FlippingBitsDiv2

Used as: Division Two - Level Three:

The k*M flip moves

The moves that involve flipping the first or last k*M bits are interesting. We will call them k*M flips.

There is no need to make a k*M flip move more than once for a same value of k and direction - It would cancel itself. We just need to choose the set of k*M flip moves to make. M effectively divides the sequence in `T = N / M` parts. After we perform a set of k*M flips, each of the bits in one of the parts will either be flipped or not. For example:
111010111010100, M = 3

The bit sequence is split in `T = N / M = 15 / 3 = 5` parts:
111 - 010 - 111 - 010 - 100

After we perform some k*M flips, some of these parts will be completely flipped and the others will be intact:
111 - 101 - 111 - 101 - 011

Flip a part or not

Assume that, given the sequence and its `T` parts of `M` bits, we knew in advance which of those parts we want to flip using k*M flips and which we prefer not to be flipped in that way. So we make a list of `T` elements. We use 1 to determine parts we want to flip and 0 for parts that we do not want to flip. So now we have a new binary sequence: 10101101010111, of T bits. We want to find the minimum number of k*M flips to do it.

We start with 00000000000000, meaning that all parts are unflipped. Each move flips the first k parts, toggling their bits from 0 to 1 and vice versa. What is the minimum number of moves we need? Begin with small examples:

• 00001111111 : This case is simple, start with 00000000000, pick the 7 last 0s and flip them. One step is needed.

• 1111000000 : Similarly, pick the 4 first 0s and flip them.

• 0000111000 : 0000000000 -> 1111111000 > 0000111000.

• 1100000001111 : 0000000000000 -> 1100000000000 -> 1100000001111.

• 0000000000: 0 steps are needed.

• 1111111111: 1 step is needed.

Let us try to generalize a strategy. Given a sequence of flipped/unflipped groups, like 10101110100000111011 . Consider any consecutive 0 or 1, there is no reason we wouldn’t flip both groups at the same time. The cost for 10101110100000111011 will the same as the cost of 10101010101. So assume that we compressed the initial setup so that there are no two consecutive 1s or 0s. What is the minimum cost? There are two possibilities:

• 1: All the groups have to be flipped (e.g: 11111…1). The cost is 1.

• A sequence that has at least one 0, so it is of the kind 10…1010 or 0…1010. The cost of the left side is 1 when the left side is 10 or 0 when it is 0. The right side has a length and begins with 1 and is of the kind: 101…10. Since it begins with 1, our first step has to be to toggle all the right side. Then we need to toggle again and so and so. For example, for 10101 as a right side::

  • 00000

  • 11111

  • 10000

  • 10111

  • 10100

  • 10101

The conclusion we need to take is that the minimum cost is equal to the number of times two consecutive positions have different values 0 or 1. Unless the sequences is 1111…1, in which case the cost is 1.

• 11010111001 has cost 6.

• 00101000110 also has cost 6.

• 00000 has cost 0 (no changes).

• 11111 has cost 1 (no changes but this is the exception).

Flip individual bits

Let us say we have decided what to do with the T parts. Some will be flipped and some will not after we use k*m flips. We also know the number of k*m flips necessary. We still need to convert all bits in the sequences to 1s, but this time we only need to use individual flips.

For the i-th group of M consecutive bits, find `c_0[i]` and `c_1[i]`, the number of 0 and 1 bits in the group. If the group was not flipped, then `c_0[i]` bits are not zero and must be flipped, else `c_1[i]` bits have become zeros and must be flipped. Therefore, depending on whether we flipped the group or not, `c_0[i]` or `c_1[i]` is added to the total cost.

Dynamic programming

We have found that all depends on the T groups of consecutive M bits and whether we decide to flip or not flip each group.

Let us work to assign the flipped or unflipped states to each of the groups. From a high index to a smaller one. Let us proceed in reverse order, from T-1 to 0.

Given a value of t, Assume we need to decide the values (flipped or not) for the first t groups and that have already decided what to do with the `(T-t)` last groups. Let p be 1 if group # `t` was flipped and 0 otherwise. We decide a value f which is 1 if we flip group `(t-1)` and 0 if we don’t.

• If `f != p` , then there was a change, the previous group was flipped and the new group isn’t or vice versa. This change forces us to increase the cost by 1. Note that if `t = T`, there is no previous group and this should be ignored.

• If f is 0, then we need to flip `c_0[t-1]` individual 0 bits into 1, which increases the cost by `c_0[t-1]`. Else we need to increase the cost by `c_1[t-1]`.

• We procceed to fill the remaining `(t-1)` groups. When deciding for `(t-2)` we will need the value of `f` that we just used.

This hints us that we might be able to solve the problem using a recurrence relation `g(t, p)`, where t indicates that we need to decide the first t groups, p means that group #t was flipped (1) or not (0) and g returns the additional cost needed for the first t groups.
There is an exception though. What if all the groups are flipped? This will find no change from p to f in any occasion, but we need to increase the cost by 1.

To detect this special case, we need to add an argument allflipped to the recurrence relation. Now we use `f(t, p, “allflipped”)`. allflipped is 1 if all the groups were flipped. The recurrence relation goes as follows:

• Base case: If `(t = 0)`, then we have no more groups to process. The additional cost is 0 unless `(“allflipped” = 1)`, this means that all the groups are flipped and that we need to add 1 cost unit. The result for `(t = 0)` is therefore equal to allflipped

• Else we try two values for `f` : 1 or 0. Which determine if group `(t-1)` is flipped or not.

• If `(p != f) and (t != T)`, increment cost by 1.

• If `(f = 0)`, increase cost by `c_0[t-1]` else by `c_1[t-1]`.

• Process the remaining groups, increase cost by `g(t-1, f, “allflipped”’ )`, because the value f for the current group will become the value p for the next group. `“allflipped”’` is equal to `(“allflipped” and f)`, in other words, if at any moment f was 0, allflipped will become 0.

And that is it. This recurrence relation has `O(N / M) -= O(N)` possible states. Most importantly, it is acyclic. We can use memoization or iterative dynamic programming to evaluate each state at most once. Which gives us a total `O(N)` complexity. A safe range for `(N <= 2500)`.

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
import string, sys

class FlippingBitsDiv2:
  def getmin(self, S, M):
  S = string.join(S, '') #concatenate all the sequence

# First a memoized
function g:
mem = dict() #we will save results in this associative array
def g(t, p, allflipped):
  if (t, p, allflipped) not in mem:
    #Result
for (t, p, allflipped) not yet saved in memory
if t == 0:
  res = allflipped #base
case
else:
  res = 10 ** 9 #initialize with a large value
for f in (0, 1): #
try values 0 or 1
for f:
  # calculate the cost
for this decision:
  cost = 0
if t != T and f != p:
  cost = 1
cost += (c1[t - 1]
  if f
  else c0[t - 1])
# recursive step:
  cost += g(t - 1, f, allflipped and f)
# remember the best:
  res = min(res, cost)
# save result in memory
mem[(t, p, allflipped)] = res
# load result from memory:
  return mem[(t, p, allflipped)]

N = len(S)
T = N / M
# fill arrays c1 and c0, the number of 1 and 0 bits in each group:
  c1 = [S[i * M: (i + 1) * M].count('1') for i in range(0, T)]
c0 = [M - x
  for x in c1]

#Set the recursion limit to a higher value, we estimate recursion depth to be O(T)
sys.setrecursionlimit(2 * T + 10)

# call the main
case
return g(T, 0, 1)

GooseTattarrattatDiv1

Used as: Division One - Level One:

Positions that must contain equal letters

In the final string, there may be groups of positions that must contain the same letter.

Palindrome rule

The palindrome rule states that the string must be equal to its reverse. Another way of seeing it is that for each position `i` : `(S[i] = S[n - i - 1] )`. This means that letters `S[i]` and `S[n - i - 1]` must be equal at the end.

This is a special relationship between two positions.

Same initial letter rule

The initial string may have the same letter in multiple positions. For example there might be a pair of positions `(i,j)` such that: `(S[i] = S[j])`. The only available move is to modify all letter positions equal to a value into a same other value. This means that all pairs `(i,j)` such that `(S[i] = S[j])` is initially true, should stay equal at the end. For each pair of positions `(i,j)`, if `(S[i] = S[j])` then the two positions are also part of the special relationship.

A implicit graph

Let us call the previously-mentioned special relationship an edge. Connecting vertices in a graph of positions. Each position in the string is a vertex, and two vertices are adjacent if the two positions must contain equal letters in the final string.

This relationship is transitive. If there were three positions `(i,j,k)` such that `S[i] = S[j]` and `S[j] = S[k]` in the final string then `S[i] = S[k]`. Two positions in the final string must be equal if there is a direct or indirect connection between them.

The good thing about using a graph is that we can easily partition the graph into connected components. If two vertices belong to the same connected component, then their positions must be equal. More importantly, all the vertices in the same connected component represent positions that must be equal to each other.

A letter for each component

All the positions in a given connected component must have the same letter in the final string. We can consider the positions in each connected component independently. If we do that, we are faced with a sub-problem for each connected component: To pick the best final letter for it. This sub-problem is identical to the division 2 easy problem: GooseTattarrattatDiv2

Summary

Determine which positions have to be equal to each other. Divide the graph in connected components of this relationship. (You can use a simple Depth-first search). Finally, for each component, find the letter that appears the maximum number of times, subtract that frequency from the number of letters in the component. The sum of the results for all components is the final answer.

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
// The solution to the division 2 problem:
int division2(string S) {
  // note how this is a shorter c++ version than that in the div2 explanation 
  int n = S.length(), m = 0;
  for (char ch: S) {
    m = std::max < int > (m, count(S.begin(), S.end(), ch));
  }
  return n - m;
}

bool visited[50];
string compo; //all the letters found in positions in the current component

int n;
string S;
// A Depth-first search finds all the positions in the connected component
// Saves all their relevant letters in the compo string.
void dfs(int i) {
  if (!visited[i]) {
    visited[i] = true;
    compo.push_back(S[i]);
    for (int j = 0; j < n; j++) {
      if (S[i] == S[j] || j == n - i - 1) {
        dfs(j);
      }
    }
  }
}

int getmin(string S) {
  // prepare the DFS:
  n = S.length();
  this - > S = S;
  fill(visited, visited + n, false);

  int res = 0;
  for (int i = 0; i < S.length(); i++) {
    if (!visited[i]) {
      // Get the letters for i's connected component: 
      compo = "";
      dfs(i);
      // Solve the sub-problem (Which we solved in division 2) 
      res += division2(compo);
    }
  }
  return res;
}

Alternative solutions and additional comments.

Many ways to simplify the code. For example, the DFS can just return the maximum number of times a letter appears in the connected component. Then we just subtract the result for each component.

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
def getmin(S):
  n = len(S)
visited = set()

# This DFS finds a list of all letters that are * connected * to letter ch:
  # Returns the maximum number of times one of the connected letters appears
def dfs(ch):
  res = 0
if ch not in visited:
  # add ch to the visited list
visited.add(ch)
# find the maximum number of positions
for a letter in the component
res = S.count(ch)
# Letter S[j] is connected to letter ch
if S[n - j - ] == ch
for i in range(0, n):
  if S[i] == ch:
  res = max(res, dfs(S[n - i - 1]))

return res

#
for each connected component, subtract the letter with the maximum number
# of positions: Call dfs
for each of the unique letters in S
return n - sum(dfs(ch) for ch in S)

class GooseTattarrattatDiv1
getmin = staticmethod(getmin)

During the match, there were solutions that used a union find data structure to quickly connect letters into a single component. You can read see this in niyaznigmatul’s solution, for example.

GearsDiv1

Used as: Division One - Level Two:

Graphs

The statement tells us to think of the gears as nodes in a graph and the mesh relationship between two gears as an edge between them.
Two meshing gears can’t have the same direction. Two adjacent nodes cannot have the same direction. After removing some of the gears, all the remaining gears of the same color must have the same direction.

How to assign directions

All the gears of a given color must move in the same direction. We have two available directions. From now on, we will call clockwise the positive (+) direction and counter-clockwise the negative (-) direction. It might initially appear that there are `2^3` ways to assign directions to the colors. In reality there are only 3 relevant ones.

If we assign the same direction to all the colors, we are only making things harder than they need to be. If all gears had the same direction, we would need to remove all connections between the gears. This worst-possible result is also an allowed result of the other cases in which we use two directions, so we can just ignore the case where all gears have the same direction.

Consider the following cases: `R<sup>+G</sup>+B^-` and `{:R^- :}{:G^- :}B^+` (* see below). In both cases, we need to cut all the connections between green and red gears, so the two cases are equivalent. At the end, there are only three important cases: `{:R^- :}{:G<sup>+:}{:B</sup>+:}`, `{:R<sup>+:}{:G</sup>- :}{:B^+:}` and `{:R<sup>+:}{:G</sup>+:}{:B^- :}`. So we just need to know which of the colors will get the direction that is different to the other two colors’ direction.

* (`R<sup>+G</sup>+B^-` means: red and green gears are positive, blue gears are negative)

Two positives, one negative

Let us simply try the three variations and repeat. In each case, two colors are positive and one is negative. After we decided which of the colors is negative, what is the minimum number of gears to remove in this specific case? Then we just need to pick the best result out of the three options.

Positive colors can’t have adjacent edges

Positive gears move in the same direction and there are two colors of of them. Gears of different positive colors can’t be adjacent, can’t share an edge, can’t mesh.

Negative color can be ignored

The gears of negative color do not really matter. Since they all have the same color, they can’t share edges. Any edge connecting a negative gear with the positive ones is perfectly valid and we do not need to remove the connection. Removing the connection does not help. We should just ignore all the negative gears and all their edges.

Disconnecting positive colors

What we have now is a set of gears. All the gears are moving in the same direction, so there should not be any connection between them. Thankfully, we know that each of the gears has one of two colors and that no two gears of the same color mesh.

What is the minimum number of gears we have to remove?

A set of vertices that share no edge is an independent set. The minimum number of vertices that we should remove in order to leave an independent set is the vertex cover. The condition that each vertex belongs to a color (class) and that initially there are no edges between vertices of the same color means that the graph is bipartite. It turns out that finding the minimum vertex cover in a bipartite graph is a known problem:

We should do a maximum bipartite matching between the gears of one color and the gears of the other color. We can implement this by using a maximum flow algorithm. Connect the source to the gears of the first color, each of those edges should have capacity 1. Then connect each pair of adjacent gears with a single edge. Finally, connect the gears of the second with the sink using edges of capacity 1.

Code

The following code assumes makes use of an external maximum flow library.

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
int getmin(string color, vector < string > graph) {
  int n = color.size();
  int res = n;
  const string RGB = "RGB";
  for (int ni = 0; ni < 3; ni++) { //the index of the "negative" color
    // If RGB[ni] is negative, then pick the other positive colors:
    char neg = RGB[ni], pos1 = RGB[(ni + 1) % 3], pos2 = RGB[(ni + 2) % 3];

    // remove connections between "positive" colors -> bipartite matching
    // (ignore negative gears )
    network * G = new MaxFlow::network(); // A network object used by the max flow solver
    for (int i = 0; i < n; i++) { //Add n vertices (one for each gear)
      G - > addVertex();
    }
    // add the source and sink:
    G - > source = G - > addVertex();
    G - > sink = G - > addVertex();
    for (int i = 0; i < n; i++) {
      if (color[i] == pos2) {
        // If the gear is of positive color 2, connect it to the sink
        G - > addEdge(i, G - > sink, 1);
      } else if (color[i] == pos1) {
        // Connect the source with the gears of positive color 1:
        G - > addEdge(G - > source, i, 1);
      }
    }
    // Create edges for each pair of adjacent positive gears: 
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if ((graph[i][j] == 'Y') && (color[i] == pos1) && (color[j] == pos2)) {
          G - > addEdge(i, j, 1);
        }
      }
    }
    // Calculate the maximum flow, which is equivalent to the maximum bipartite
    // matching, which is equivalent to the minimum vertex cover. Which is the
    // number of gears to remove to disconnect them:
    int mf = G - > maxFlow();
    // Remember the smallest result
    res = std::min(res, mf);

    // recycle the network object, non-C++ coders please ignore this.
    delete G;
  }
  return res;
}

FlippingBitsDiv1

Used as: Division One - Level Three:

Rotator sequence

The definition of a rotator sequence can also be interpreted as a sequence of bits that is has a cycle of length `M`: For example 11010111010111010111 is a rotator sequence for `M = 6` and `M = 12`. Note that `N` is not necessarily a multiple of `M`, but the last `N % M` bits still follow the cycle. It takes some prior knowledge of cyclic sequences or to try them on paper for a while to notice this fact. We can also just do an analisys of which bit positions must be equal to bit `(0 &lt;= i &lt; M)` , you will see that positions `(i, i+M, i+2*M, …)` all must be equal in order to follow the definition.

The k*M flip moves

This part of the problem analysis is similar to the division 2 version although with some small differences, so it might be useful to solve that problem first.

The moves that involve flipping the first k*M bits are interesting. We will call them k*M flips.
Something interesting is that if `N % M != 0`, it will be impossible to use the k*M flip moves to flip the last `N % M` bits. We will ignore them in this part of the analysis.

There is no need to make a k*M flip move more than once for a same value of k - It would cancel itself. We just need to choose the set of k*M flip moves to make. M effectively divides the sequence in `T = N / M` parts. After we perform a set of k*M flips, each of the bits in one of the parts will either be flipped or not. For example:

111010111010100, M = 3

The bit sequence is split in `T = N / M = 15 / 3 = 5` parts:

111 - 010 - 111 - 010 - 100

After we perform some k*M flips, some of these parts will be completely flipped and the others will be intact:
111 - 101 - 111 - 101 - 011

Flip a part or not

Assume that, given the sequence and its `T` parts of `M` bits, we knew in advance which of those parts we want to flip using k*M moves and which we prefer not to be flipped in that way. So we make a list of `T` elements. We use 1 to determine parts we want to flip and 0 for parts that we do not want to flip. So now we have a new binary sequence: 10101101010111, of T bits. We want to find the minimum number of k*M flips to do it.

We start with 00000000000000, meaning that all parts are unflipped. Each move flips the first k parts, toggling their bits from 0 to 1 and vice versa.

Using an analysis similar to the division 2 version, you will find that the minimum number of k*M flips is equal to the number of bit positions `i` such that: `s[i] != s[i+1]` plus `s[T-1]`. So we can generate 10101101010111 in 11 moves (There are 10 changes and the last bit is 1):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
00000000000000 - >
  **
  11111111111111 ** - >
  **
  00000000000 ** 111 - >
  **
  1111111111 ** 0111 - >
  **
  000000000 ** 10111 - >
  **
  11111111 ** 010111 - >
  **
  0000000 ** 1010111 - >
  **
  111111 ** 01010111 - >
  **
  0000 ** 1101010111 - >
  **
  111 ** 01101010111 - >
  **
  00 ** 101101010111 - >
  **
  1 ** 0101101010111

Small and large values of M

The key to solve this problem is to notice that the whole problem depends on the values of `M` and `T`. If the value of `M` is large, the value of `T` will be small and vice versa.

With `(N &lt;= 300)`, then `M` can be at most 300. However, if `M = 300`, then `T = 1`, which is very small. So let us find the maximum value for `min(M, T) = min(M, N/M)`, this is the square root. Therefore, at least one of the following conditions is true: `(M &lt;= 17)` or `(T &lt;= 17)`. 17 is a reasonable value that might allow even exponential complexity algorithms. Let us try it.

1
2
3
4
5
6
7
8
9
10
int getmin(vector < string > S, int M) {
  // concatenate S:
  string s = accumulate(S.begin(), S.end(), string(""));
  // Pick the best approach:
  if (M <= 17) {
    return smallM(s, M);
  } else {
    return smallT(s, M);
  }
}

Small M

Assume that `(M &lt;= 17)`. Remember that we defined a rotation sequence as one in which the same sequence of `M` bits is repeated over and over again. This means that there are only `M` values that determine the total result. There will be `(2 ^ M)` different results. M is small, so we can try them all.

If we know the original bit (e.g: 100010101) sequence and the target sequence (e.g: 110011001, note it is 1100 repeated) then we know exactly which bit positions we want to toggle. Any bit position in which original and target differ:

1
2
3
4
100010101
110011001
-- -- -- -- --
010001100

This is the same as performing a bit-wise xor between the original and the result. We intend the positions that are marked by 1, to be toggled, so we want them to become 0. In other words, we will like 010001100 to become 000000000. Or more formally, if Given, original and result we generate `a = “original” o+ “result”` (Where `o+` is the binary xor) and want to flip some of the positions of a using the allowed moves, so that a becomes 0. This becomes a problem similar to the division 2 version.

The last `N % M` bits cannot be flipped using k*M flips, so we will use the individual flips to solve them, every 1 becomes 0 with a cost. The remaining bits form groups of `M` consecutive bits each. There will be `T = N/M` such groups.

Consider the group of `M` bits: 1101011:

• If we decide not to flip this group, then we still need to zero each of its 1 bits: So the cost for this specific group will be equal to the number of 1 bits in it.

• If we decide to flip the group, it will become 0010100. We need to flip the new 1s which were formerly 0s, so the cost will be equal to the number of 0 bits in the sequence. This is in addition to whatever cost is needed to flip the group M.

Define for each group `i` of M bits: `c_0[i]`: the number of 0 bits in the group. And `c_1[i]`: The number of 1 bits in the group.

Now let us say that we have a sequence of `T` bits that determine whether the i-th group will be toggled or not. From previous analysis we can easily calculate the total cost to set all the bits to 0 if we decided to toggle those grups.

• For each unflipped group i, add `c_1[i]` to the cost.

• For each flipped group, add `c_0[i]`.

• For each group i, if group i is flipped and group i+1 is not flipped, add 1 to the cost.

• If the last group is flipped, add 1 to the cost.

This allows us to create a dynamic programming solution. Let us worry about filling the sequence of flipped/unflipped groups of `M` bits. The cost depends on whether or not the previous group that we zeroed was flipped or not. Let us use a function `g(t, p)` that returns the cost to zero the remaining bits when:

• `t` means that the first `t` groups of `M` bits were not zeroed yet. The `T-t` last groups were already processed and are already zero.

• `p` is 1 if, when we solved group `t`, we flipped that group or 0 otherwise. If `(t = T)`, it is convenient to make `p=0`, you will soon why.
  For a base case, `t = 0`, we have already zeroed all the bits. With nothing to do, the cost is 0.
  In other cases, we first decide whether or not to flip group `(t-1)`. We will use `f = 1` in case we want to flip it and `f = 0` otherwise.

• If `f != p` , then there is a change between the previous and current value. We need to increase the cost by 1. This is the reason why `p = 0` when `t = T`, this allows us to increase the cost by 1 if `f = 1` for the last group.

• If `(f = 1)`, add `c_0[t-1]` to the cost, else add `c_1[t-1]`.

• The cost to zero the `t-1` remaining groups is: `g(t-1, f)` , because when filling `(t-2)`, we will need the flip value at `(t-1)`, which is the current one.

The addition of the two costs is the result for the chosen value of `f`, try the two possibilities: 1 and 0 , and pick the one that yields the minimum total cost.

Small M - code

The following c++ program solves this special case:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int INF = (1 << 29);
int zeroIt(int T, int * c1, int * c0) {
  // Dynamic programming. Given T groups, group i has c1[i] 1 bits and
  // c0[i] 0 bits.

  int dp[T][2];
  dp[0][1] = dp[0][0] = 0; // Base case, t = 0

  for (int t = 1; t <= T; t++) {
    for (int p = 0; p < 2; p++) {
      dp[t][p] = INF;
      for (int f = 0; f < 2; f++) { //For each value of f:
        // Calculate the cost:
        int cost = 0;
        if (p != f) {
          cost++; // a change
        }
        cost += dp[t - 1][f];
        if (f) {
          cost += c0[t - 1];
        } else {
          cost += c1[t - 1];
        }
        // Recursive step, remember the smallest cost.
        dp[t][p] = std::min(dp[t][p], cost);
      }
    }
  }

  return dp[T][0];
}

// Assume s has the concatenation of the original vector of strings.
int smallM(string s, int M) { // M <= 17
  int N = s.length(), T = N / M, mask, ans = INF, i;
  int a[N]; //the bits

  // For each of the 2^M possible cyclic parts of the result:
  for (int mask = 0; mask < (1 << M); mask++) {
    // Generate a, binary array that has a 1 in positions that must
    // be flipped.
    for (int i = 0; i < N; i++) {
      a[i] = s[i] - '0'; // first the original bit.
      if (mask & (1 << (i % M))) { //If picked result requires a 1 in this position:
        a[i] ^= 1; // toggle this bit.
      }
    }
    int cost = 0;
    for (int i = T * M; i < N; i++) { //T*M = N - N % M
      if (a[i] == 1) { // we cannot use k*m flips to alter these last bits
        cost++; // toggle them manually.
      }
    }
    int c1[T], c0[T];
    for (int i = 0; i < T; i++) {
      c1[i] = count(a + i * M, a + (i + 1) * M, 1); //number of 1s in the i-th group
      c0[i] = M - c1[i]; // number of zeros.
    }
    cost += zeroIt(T, c1, c0);

    // Remember the best cost.
    ans = min(ans, cost);
  }

  return ans;
}

Since we only run this code when `M` is `O(sqrt(N))`, then we repeat the `O(N)` dynamic programming algorithm for each of the `O(2^sqrt(N))` ways to fill the result. The total complexity is: `O(N times 2^sqrt(N))` which is quite good.

Small T

In this case, M is so large that `(T &lt;= sqrt(N))`. This means that T is at most 17. This means that there are few groups of M consecutive bits. We can brute-force and find each of the `2^T` ways to decide if each of the groups is flipped or unflipped using k*M flips. For that decision, it is easy to find the minimum number of k*M flips needed.

After performing the k*M flips, the `N` bits of the sequence will have some values we would like to do individual flips so that this sequence becomes a rotator. Remember that for each `(i &lt; M)`, bits #: `(i, i+M, i+2M, …)` must all be equal. We can just decide between 1 or 0 for position i and just pick the option that requires the least number of individual toggles. For example, we count the number of positions `(i, i+M, i+2M, …)` that currently contain a 1 and the ones that contain a 0. From those numbers we can know the cost to turn all the 1s to 0s and all the 0s to 1s, and just pick the best one.

For each `O(2 ^ sqrt(N))` ways to decide the k*M flips, we need a simple `O(N)` algorithm to calculate the total cost to make the sequence a rotator. Consider this problem solved with a total `O(N times 2^sqrt(N))` time complexity.

Small T - 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
int smallT(string s, int M) { // T <= 17
  int N = s.length(), T = N / M, ans = INF;

  int a[N];

  // Try the ways to flip the T groups:
  for (int mask = 0; mask < (1 << T); mask++) {
    // initialize the bit sequence with the input:
    for (int i = 0; i < N; i++) {
      a[i] = s[i] - '0';
    }
    // flip the sequence's groups of M consecutive bits using the picked mask:
    int cost = 0;
    int p = 0;
    for (int i = T - 1; i >= 0; i--) {
      // if i is in the mask:
      int f = 0;
      if (mask & (1 << i)) {
        f = 1;
        //flip this group:
        for (int j = 0; j < M; j++) {
          a[i * M + j] ^= 1;
        }
      }
      if (f != p) {
        // a change between previous flip value and the current one:
        // Increment the cost:
        cost++;
      }
    }

    // For each i < M:
    for (int i = 0; i < M; i++) {
      // count the number of 0s and 1s in i, i+M, i+2M, ..., etc.
      int p = 0, q = 0;
      for (int j = i; j < N; j += M) {
        if (a[j] == 0) {
          p++;
        } else {
          q++;
        }
      }
      // Pick the best one, toggle them so that these positions are equal:
      cost += min(p, q);
    }

    ans = min(ans, cost);
  }

  return ans;
}