Sleeping Through Classes

The key thing: there is basically no choice here.

The statement says every important class must be attended. Once you attend an important class at position $i$, you are forced to stay awake for classes

$i+1, i+2, \ldots, i+k.$

So the schedule is fully determined by where the 1s are. This is not some spicy DP problem hiding in the bushes. It's just: mark which positions are forced awake, then count the rest.

What Makes A Class Sleepable?

Class $i$ is sleepable if both conditions hold:

1. $s_i = 0$, because important classes are mandatory.
2. There is no important class among the previous $k$ positions.

Why previous positions only? Because an important class affects the classes after it, not before it. A future 1 cannot ruin your current nap. Time does not run backwards, unfortunately or fortunately depending on the school day.

So for a zero at position $i$, it is forced awake if there exists some important class $j$ such that

$j < i \le j+k.$

That means $i$ lies within the cooldown zone after a 1.

Left-To-Right Scan

Maintain last, the index of the most recent important class seen so far.

When we are at position $i$:

• If s[i] == '1', this class is important, so update last = i.
• Otherwise, this is a 0. It is sleepable only if it is outside the forced-awake range from the latest 1:

$i > last + k.$

If that inequality holds, count it.

Why is the latest 1 enough? Because among all previous important classes, the most recent one has the farthest-right forced range endpoint. If even the most recent 1 does not force you awake, then older ones definitely do not either.

Example Walkthrough

Take:

$s = \texttt{01000101}, \quad k = 2$

Using 0-based indices:

• index $0$: 0, no previous 1, sleep.
• index $1$: 1, awake, set last = 1.
• indices $2,3$: forced awake because they are within $2$ classes after index $1$.
• index $4$: outside that range, sleep.
• index $5$: 1, awake, set last = 5.
• index $6$: forced awake.
• index $7$: 1, awake.

Answer: $2$.

Correctness Argument

For every position $i$, the algorithm tracks last, the nearest important class before or at $i$.

If $s_i = 1$, the class is important, so it cannot be slept through. The algorithm does not count it, which is correct.

If $s_i = 0$, then the only possible reason it cannot be slept through is that some previous important class forces wakefulness. The strongest such previous class is the most recent one, stored in last. If $i \le last + k$, then class $i$ is within the forced-awake range, so the algorithm correctly does not count it. If $i > last + k$, then no previous important class can force class $i$ awake, because every older important class has an even smaller forced range endpoint. So the algorithm correctly counts it as sleepable.

Thus every class is counted exactly when it can be slept through, so the answer is correct.

Complexity

Each test case is scanned once.

$O(n)$ time and $O(1)$ extra memory.

With $n \le 100$, this is extremely chill. The CPU is also sleeping through this one.