Thought process on Codeforces 1353E

Link to problem

I remember seeing this problem almost a year ago during practice and getting stuck. Well, I finally solved it almost a year later!

Since the problem asks about equal spacing (of length K) between 1s in a binary string, I immediately  thought of numbers of 0s and 1s for each residue mod K. We have enough time to try each residue if the work for each residue is linearly proportional to the number of bits in each residue, i.e. K residues * (N / K) bits in each residue = O(N) total work. We know that while we are trying each residue, the bits at positions not congruent to K mod N have to be off, which is an easy precomputation done in O(N).

Our solution looks like this so far:

i64 solve(const i64 N, const i64 K, string_view S) {
  i64 total_on = 0;
  vec<i64> resid_on(K, 0);
  for (i64 i = 0; i < N; ++i) {
  	total_on += S[i] == '1';
    resid_on[i % K] += S[i] == '1';
  }

  i64 best = N;
  for (i64 resid = 0; resid < K; ++resid) {
    let i64 turn_non_resid_off = total_on - resid_on[resid];

    // gather the bits at resid (mod K) for convenience
    vec<bool> seq;
    for (i64 i = resid; i < N; i += K) {
      seq.push_back(S[i] == '1');
    }
    // TODO implement solve_resid
    let i64 subproblem_ans = solve_resid(seq);
    best = min(best, turn_non_resid_off + subproblem_ans);
  }
  return best;
}

Let's focus on bits at positions whose residues are resid (mod K). We know that they have to form the pattern 0*1*0*, i.e. 1111, 00111, 1000, 0000, 010, etc. So we have reduced the main problem to this problem. How do we solve it?

At first, my smooth brain thought this could be done with greedy. My approach was ignore leading 0s, ignore the 1s after the leading 0s. At the same time, ignore trailing 0s, and ignore the 1s before trailing 0s. Now we want to turn all the bits on in the middle subsegment. However, this fails on a case like:

10 2

0001000100

Because we can simply turn off one of the 1s rather turn on the 3 zeros in the middle.

At this point, my mind turned to dynamic programming. I started building my recurrences as follows:

1. Define f(pos) = minimum moves to make the suffix [pos, N) valid.
2. Define g(pos, state: {0, 1}) = minimum moves to make suffix [pos, N) valid such that bit at pos is state. This implies:
1. g(pos, 1) = (pos != 1) + (moves to make the suffix [pos + 1, N) have the pattern 1*0*)
2. g(pos, 0) = (pos != 0) + f(pos + 1)

and we want to solve for f(0), which is min(g(pos, *)). The wildcard used here and below represents all possible values for that argument, i.e. {0, 1} here.

This looks promising, but what is (moves to make the suffix [pos + 1, N) have the pattern 1*0*)?? It looked suspiciously "nice", i.e. something that I might be able to turn into a recurrence. OK, let's try that:

1. Define h(pos, state) = minimum moves to make the suffix [pos, N) have the pattern 1*0*. This implies:
1. h(pos, 1) = (pos != 1) + min(h(pos + 1, *))
2. h(pos, 0) = \sum_{i = pos}^N (i != 0)

Well that was nice indeed. Putting it together by plugging h into g, we have:

1. g(pos, 1) = (pos != 1) + min(h(pos + 1, *))
2. g(pos, 0) = (pos != 0) + f(pos + 1), as before

Implementation is straightforward:

i64 solve_resid(const vec<bool>& seq) {
  vec<vec<i64>> h(seq.size() + 1, vec<i64>(2));
  for (i64 i = seq.size() - 1; i >= 0; --i) {
    h[i][0] = seq[i] + h[i + 1][0];
    h[i][1] = !seq[i] + min(h[i + 1][0], h[i + 1][1]);
  }
  vec<vec<i64>> g(seq.size() + 1, vec<i64>(2));
  for (i64 i = seq.size() - 1; i >= 0; --i) {
  	g[i][0] =  seq[i] + min(g[i + 1][0], g[i + 1][1]);
    g[i][1] = !seq[i] + min(h[i + 1][0], h[i + 1][1]);
  }
  return min(g.front()[0], g.front()[1]);
}

Voila, Accepted!