Overview

This problem asks us to count the number of intervals where the sum of \(K\) consecutive elements is less than or equal to \(0\). It can be solved efficiently using the sliding window technique.

Analysis

Problems with the Naive Approach

The simplest method is to calculate the sum of \(K\) elements for each starting position \(i\).

for i in range(N - K + 1):
    window_sum = sum(A[i:i+K])  # Add K elements each time
    if window_sum <= 0:
        count += 1

This method has \(O(N)\) intervals, and for each interval, we perform \(O(K)\) additions, resulting in a total time complexity of \(O(NK)\). When \(N = 2 \times 10^5\), this requires up to approximately \(4 \times 10^{10}\) calculations in the worst case, leading to TLE (Time Limit Exceeded).

Key Insight

Let’s consider two consecutive intervals.

• Interval 1: \(A_1, A_2, A_3, A_4\) (when \(K=4\))
• Interval 2: \(A_2, A_3, A_4, A_5\)

These two intervals have an overlapping portion: \(A_2, A_3, A_4\). This means we can calculate the sum of Interval 2 from the sum of Interval 1 as follows:

\[\text{Sum of Interval 2} = \text{Sum of Interval 1} - A_1 + A_5\]

This requires only 2 operations.

Algorithm

We use the sliding window technique (two-pointer method).

1. First, calculate the sum of the first \(K\) elements
2. Slide the window one position to the right at a time:
   • Subtract the leftmost element
   • Add the new rightmost element
3. At each step, check if the sum is less than or equal to \(0\) and update the count

Concrete example (\(N=6, K=3, A=[2, -3, 1, -2, 4, -1]\)):

Position \(i\)	Interval	Calculation	Sum	Anomaly?
1	\([2, -3, 1]\)	Initial calculation	\(0\)	✓
2	\([-3, 1, -2]\)	\(0 - 2 + (-2) = -4\)	\(-4\)	✓
3	\([1, -2, 4]\)	\(-4 - (-3) + 4 = 3\)	\(3\)	×
4	\([-2, 4, -1]\)	\(3 - 1 + (-1) = 1\)	\(1\)	×

Answer: \(2\) intervals

Complexity

• Time Complexity: \(O(N)\)

  • Initial sum of \(K\) elements: \(O(K)\)
  • Sliding window movement: \(O(N - K)\) times, each taking \(O(1)\)
  • Total: \(O(K + (N - K)) = O(N)\)

• Space Complexity: \(O(N)\)

  • \(O(N)\) for storing input array \(A\)
  • \(O(1)\) for other variables

Implementation Notes

1. Beware of overflow: Since the absolute value of \(A_i\) can be up to \(10^9\) and \(K\) can be up to \(2 \times 10^5\), the sum can reach approximately \(2 \times 10^{14}\). In Python, you don’t need to worry about integer overflow, but in C++ and similar languages, you need to use long long.

2. Index management: When sliding the window to the right, the element to remove is A[i-1] and the element to add is A[i+K-1]. Be careful about index offsets.

3. Boundary conditions: When \(K = N\), there is only one interval. Verify that your code handles this case correctly (the loop executes 0 times, so there’s no problem).

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Calculate the sum of the first K elements
    window_sum = sum(A[:K])
    
    count = 0
    if window_sum <= 0:
        count += 1
    
    # Check remaining intervals using sliding window
    for i in range(1, N - K + 1):
        # Add new element and remove old element
        window_sum = window_sum - A[i - 1] + A[i + K - 1]
        if window_sum <= 0:
            count += 1
    
    print(count)

solve()

---

This editorial was generated by claude4.5opus.