Overview

Given a weather record of length \(N\), we examine all intervals of \(M\) consecutive days and count the number of “bad weather periods” where the number of sunny days is less than \(K\). We solve this efficiently using the sliding window technique.

Analysis

Naive Approach and Its Problems

The simplest method is to count the number of sunny days over \(M\) days for each of the \(N - M + 1\) intervals. In this case, the time complexity is \(O(N \times M)\).

Since \(N\) can be up to \(10^6\) and \(M\) can also be up to \(10^6\), the worst case requires \(10^{12}\) operations, which results in TLE (Time Limit Exceeded).

Key Observation

When comparing two adjacent intervals, we notice that most of their elements overlap.

For example, with \(S = \) 110100 and \(M = 3\): - Interval 1: 110 (day 1 to day 3) → 2 sunny days - Interval 2: 101 (day 2 to day 4) → 2 sunny days - Interval 3: 010 (day 3 to day 5) → 1 sunny day - Interval 4: 100 (day 4 to day 6) → 1 sunny day

When moving from interval 1 → interval 2, only day 1 on the left is removed and day 4 on the right is added. In other words, there is no need to recount all \(M\) days each time — it is sufficient to update only the difference (one element removed and one element added).

Algorithm

We use the sliding window technique.

1. Compute the initial window: Count the number of sunny days count from day 1 to day \(M\).
2. Check: If count \(< K\), increment the result by 1.
3. Slide the window: For \(i = 1, 2, \ldots, N - M\), repeat the following:
   • Remove the left end: If \(S[i-1]\) is 1, decrement count by 1.
   • Add the right end: If \(S[i+M-1]\) is 1, increment count by 1.
   • Check: If count \(< K\), increment the result by 1.
4. Output the final result.

Verifying with the example above (\(S = \) 110100, \(M = 3\), \(K = 2\)): - Initial: 110 → count=2, \(2 < 2\) is false - Slide 1: Remove 1, add 1 → remove 1 makes count=1, add 1 makes count=2 → 101 count=2, false - Slide 2: Remove 1 makes count=1, add 0 makes count=1 → 010 count=1, \(1 < 2\) is true → result=1 - Slide 3: Remove 0 makes count=1, add 0 makes count=1 → 100 count=1, \(1 < 2\) is true → result=2

The answer is 2.

Complexity

• Time complexity: \(O(N)\) — \(O(M)\) for computing the initial window, \(O(N - M)\) for sliding, totaling \(O(N)\)
• Space complexity: \(O(N)\) — required for storing the string \(S\)

Implementation Notes

• We use sys.stdin.buffer.read() to read input quickly. Since \(N\) can be as large as \(10^6\), fast input handling is important in Python.

• The number of sunny days in the window is managed with a single variable count, and only the difference is updated with each slide, so no additional arrays are needed.

• This can also be solved in \(O(N)\) using prefix sums, but the sliding window approach is more memory-efficient and simpler to implement.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    S = input_data[3].decode()
    
    # Calculate sum of first window
    count = 0
    for i in range(M):
        if S[i] == '1':
            count += 1
    
    result = 0
    if count < K:
        result += 1
    
    for i in range(1, N - M + 1):
        # Remove element going out of window
        if S[i - 1] == '1':
            count -= 1
        # Add element coming into window
        if S[i + M - 1] == '1':
            count += 1
        if count < K:
            result += 1
    
    print(result)

main()

---

This editorial was generated by claude4.6opus-thinking.