Overview

This is a problem where flower beds are arranged in a row, and you need to find the maximum number of flowers that can be watered by sprinkling water at equal intervals.

Analysis

In this problem, the natural approach is to try all possible sprinkler intervals \(K\) from \(1\) to \(N\), and count the number of flowers that receive water for each case.

For example, consider \(S = "o.o.o"\), where flowers are at positions 1, 3, and 5.

• When \(K=1\), water reaches all positions \(1, 2, 3, 4, 5\), and 3 flowers receive water.
• When \(K=2\), water reaches positions \(1, 3, 5\), and 3 flowers receive water.
• When \(K=3\), water reaches positions \(1, 4\), and 1 flower receives water.

In this way, by exhaustively searching over all \(K\), we can find the maximum value.

With a naive brute-force approach, for the constraint \(N \leq 2 \times 10^5\), each \(K\) requires up to \(N\) checks, leading to a total of up to \(N^2 = 4 \times 10^{10}\) operations, which would exceed the time limit (typically around 1 second).

However, in practice, as \(K\) increases, the number of positions to check (\(N/K\)) decreases, so the total computation is bounded by \(O(N \log N)\), which is sufficiently fast.

Algorithm

1. For each \(K = 1, 2, ..., N\), do the following:
   • Water the positions \(0, K, 2K, 3K, ...\) (using 0-based indexing in Python), and count the number of positions that contain a flower (o).
2. Keep track of the maximum count.
3. Output the final maximum value obtained.

Complexity

• Time complexity: \(O(N \log N)\)
  　→ For each \(K\), there are \(N/K\) elements to check, and the total is \(\sum_{K=1}^{N} \frac{N}{K} \approx N \log N\)
• Space complexity: \(O(1)\)
  　→ Only a constant number of variables are used aside from the input

Implementation Notes

• String indices are 0-based, but the “positions” in the problem statement are 1-based, so be careful (however, there is no issue if you consistently use 0-based indexing in your code)

• Use sys.stdin.read for fast input reading

• For each \(K\), using range(0, N, K) to obtain equally-spaced positions makes the code simple to write

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    S = data[1]
    
    max_watered = 0
    
    for K in range(1, N + 1):
        count = 0
        for i in range(0, N, K):
            if S[i] == 'o':
                count += 1
        if count > max_watered:
            max_watered = count
            
    print(max_watered)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.