TC SRM443 D1 600 (BinaryFlips)

This problem can be accessed via:
http://www.topcoder.com/stat?c=problem_statement&pm=10387

A fairly standard problem with somewhat tricky implementation due to the problem constraints. The problem gives us "A" number of zeroes and "B" and number of ones and using a swap of exactly "K" digits in each turn, determine the minimum number of moves to get it into a state of all ones (and returning -1 if it's impossible to do so). Looking at the constraints of around 100,000 means we can't naively try all combinations. A simple approach to take is to Breadth-First searching the moves and making sure we don't re-visit already processed nodes with lower number of moves (as they will never be optimal).

We need to make several observations to help simplify the problem. As we can choose any K digits to swap over in a given turn, this means we can view the problem as a set of 0's followed by a set of 1's for simplicity. This helps us determine that the state required for the BFS is simply the number of zeroes (or ones) and not a string of disordered 0's and 1's. A further optimisation is to note that the number of zeroes can be derived from the number of ones as the total size of the string does not change. Hence the maximum state space is simply 200,000 so we are fine for memory usage. The only problem left is the transitions between states inside the inner cycle of the BFS. As the K is as large as 100,000 we will run into time limit issues if we aren't efficient in which states we check/traverse to.

This is perhaps the trickest part of the problem - the other parts are fairly standard and simple. Now we ask ourselves, "is there a way to make sure we only consider non-visited nodes?". Using a set data structure which keeps all its elements unique allows us to only traverse the unvisited states. To make another optimisation we need to ensure that we only visit the reachable unvisited states - we calculate the state range in which we can reach and do a subset traversal of the set (instead of going through the whole set and determining whether it's a valid move). To determine the range of states we need to see that if we can traverse to x-number of 1's and we can also traverse to y-number of 1's then we can also traverse to all number of 1's between x and y with the same parity. To see this, arrange a state in a sequence of 0's and 1's and take an arbitrary K (K = 4 in this case):

Move to 9 1's: 0[0000]11111 -> 0[1111]11111
Move to 7 1's: 00[0001]1111 -> 00[1110]1111
Move to 5 1's: 000[0011]111 -> 000[1100]111
Move to 3 1's: 0000[0111]11 -> 0000[1000]11
Move to 1 1's: 00000[1111]1 -> 00000[0000]1

As you can see, we can only move a specific parity (odd/even) between the minimum and maximum range. This can be seen above where we use a sliding "window" mechanism for the inversion. The parity is determined by a combination of the window size (i.e. K) and the parity of the state. To see this connection, we build an informal proof:

Let the K-sized window be denoted by W.
Let P be the parity of the state S, where S is a sequence of 0's followed by 1's.
Then we define x to be the number of 0's in S and y to be the number of 1's in S.

By definition, P = y (mod 2). Furthermore we need to define x' and y' to be the number of 0's and 1's in the window W respectively. We take x'' and y'' to be the number of 0's and 1's in the state S excluding the digits inside window W. Then it follows that:

x'' = x - x' (mod 2)
y'' = y - y' (mod 2)
x' + y' = K

Parity of the inversed window W = x' (mod 2) since it's the number of 0's in the window (as they turn into 1's after the transform which becomes the parity). We now calculate P', the parity of S after being transformed by an arbitrary K-sized window:

P' = x' (mod 2) + y'' (mod 2) (parity of the inversed window plus the region of S - W)
P' = K - y' (mod 2) + y'' (mod 2)
P' = K - y' + y'' (mod 2)
P' = K - y' + 2y' + y'' (mod 2) (add 2y' - this can be done since it doesn't alter the odd/even-ness of the equation)
P' = K + y' + y'' (mod 2)
P' = K + y (mod 2)

Therefore the next state's parity is P' = K + y (mod 2). So we only need to compute this to determine whether the parity of the next state is odd/even. So it suffices to just calculate the minimum and maximum number of 1's and then traverse based on the parity. Using all the concepts above gives us an implementation which runs at around 100ms worst case:

class BinaryFlips {
public:
 int minimalMoves(int, int, int);
};

int visited[200011];

int BinaryFlips::minimalMoves(int A, int B, int K) {
 if (A == 0) return 0;
 if (A + B < K) return -1;
 queue<int> q;
 int N = A + B;
 memset(visited,-1,sizeof(visited));
 set<int> evenVisit, oddVisit;
 for (int i = 0; i <= N; i++) {
  if (i & 1) oddVisit.insert(i);
  else evenVisit.insert(i);
 }
 if (B & 1) oddVisit.erase(oddVisit.find(B));
 else evenVisit.erase(evenVisit.erase(B));
 q.push(B);
 visited[B] = 0;
 while (!q.empty()) {
  int t = q.front(); q.pop();
  if (t == N) return visited[t];
  int numZeroes = N - t;
  int numOnes = t;
  int x = numOnes < K ? K - numOnes : numOnes - K;
  int y = numZeroes < K ? numOnes + numZeroes * 2 - K : numOnes + K;
  int s = min(x,y);
  int st = max(x,y);
  set<int>* visitSet = (t+K) & 1 ? &oddVisit : &evenVisit;
  if (visitSet->size() == 0) continue;
  set<int>::iterator it = visitSet->lower_bound(s);
  while (it != visitSet->end() && *it <= st) {
   if (visited[*it] < 0) {
    q.push(*it);
    visited[*it] = 1 + visited[t];
    set<int>::iterator itTemp = it; itTemp++;
    visitSet->erase(it);
    it = itTemp;
   } else {
    it++;
   }
  }
 }
 return -1;
}