Rakhsh's Revival
Contest: Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
Difficulty rating: 1000
Tags: data structures, greedy, implementation, two pointers

Rostam's loyal horse, Rakhsh, has seen better days. Once powerful and fast, Rakhsh has grown weaker over time, struggling to even move. Rostam worries that if too many parts of Rakhsh's body lose strength at once, Rakhsh might stop entirely. To keep his companion going, Rostam decides to strengthen Rakhsh, bit by bit, so no part of his body is too frail for too long.

Imagine Rakhsh's body as a line of spots represented by a binary string $$$s$$$ of length $$$n$$$, where each $$$0$$$ means a weak spot and each $$$1$$$ means a strong one. Rostam's goal is to make sure that no interval of $$$m$$$ consecutive spots is entirely weak (all $$$0$$$s).

Luckily, Rostam has a special ability called Timar, inherited from his mother Rudabeh at birth. With Timar, he can select any segment of length $$$k$$$ and instantly strengthen all of it (changing every character in that segment to $$$1$$$). The challenge is to figure out the minimum number of times Rostam needs to use Timar to keep Rakhsh moving, ensuring there are no consecutive entirely weak spots of length $$$m$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of test cases.

The first line of each test case contains three numbers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le m, k \le n \le 2 \cdot 10^5$$$). The second line of each test case contains a binary string $$$s$$$ of $$$n$$$ characters $$$s_1s_2 \ldots s_n$$$. ($$$s_i \in \{$$$0,1$$$\}$$$ for $$$1 \le i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the minimum number of times Rostam needs to use Timar to keep Rakhsh moving, ensuring there are no consecutive entirely weak spots of length $$$m$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we should apply an operation on each 0.

In the second test case, $$$s$$$ is already ok.

In the third test case, we can perform an operation on interval $$$[3,4]$$$ to get 001100.

Example input:
3
5 1 1
10101
5 2 1
10101
6 3 2
000000

Example output:
2
0
1

Editorial:
We will solve the problem using the following approach:
• Start from the leftmost spot and move rightwards.
• Whenever a consecutive segment of $$$m$$$ weak spots (i.e., $$$0$$$'s) is found, apply Timar to a segment of length $$$k$$$ starting from the last index of weak segment.
• Repeat this process until no segment of $$$m$$$ consecutive weak spots remains.
The idea behind this solution is that whenever we encounter a block of $$$m$$$ consecutive $$$0$$$'s, we need to strengthen it. Since we can apply Timar to a segment of length $$$k$$$, the optimal strategy is to always apply Timar starting at the last index of block of $$$m$$$ $$$0$$$'s.
Correctness Proof:
• For any block of $$$m$$$ consecutive $$$0$$$'s, we must apply Timar to at least one index in this block. Therefore, there must be an overlap between the block of weak spots and the segment of length $$$k$$$ that we strengthen.
• Suppose there exists an optimal solution where Timar is applied to a leftward segment. If we instead shifted this segment one step to the right, it would not affect the correctness of the solution, and it would still remain optimal.
Hence, this greedy strategy ensures that the minimum number of applications of Timar is used.