P14979 [USACO26JAN1] Sliding Window Summation S

Bessie has a hidden binary string $b_1b_2\dots b_N$ ($1\le N\le 2\cdot 10^5$). The only information about $b$ you are given is a binary string $r_1r_2\dots r_{N-K+1}$ ($1 \le K \le N$), where $r_i$ is the remainder when the number of ones in the length-$K$ window of $b$ with leftmost index $i$ is divided by two. Output the minimum and maximum possible numbers of ones in Bessie's hidden binary string.

There are $T$ ($1\le T\le 10^3$) independent test cases to be solved. Each test is specified by the following: The first line contains $N$ and $K$. The second line contains the binary string $r_1\dots r_{N-K+1}$, where $r_i=\sum_{j=i}^{j+K-1}b_j\pmod{2}$. It is guaranteed that the sum of $N$ over all tests does not exceed $10^6$.

For each test case, output the minimum and maximum possible numbers of ones in Bessie's hidden binary string, separated by a single space.

For the first test case, $K=1$ means that $r=b$, and the number of ones in $r$ is $3$. For the second test case, there are two possibilities for $b$: 10001 and 01110, having $2$ and $3$ ones, respectively. --- - Input 2: $N\le 8$ - Inputs 3-4: $K\le 8$ and the sum of $N$ over all tests does not exceed $10^4$. - Inputs 5-11: No additional constraints.