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).

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:

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

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

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

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!

## No comments:

## Post a Comment