Overview

Choose a sprinkler interval \(K\) from \(1 \le K \le N\) such that the number of flowers o at positions \(1, 1+K, 1+2K, \ldots\) is maximized.

Analysis

The sprinkler waters only every \(K\)-th section starting from the first. In other words (1-indexed), $\(1,\ 1+K,\ 1+2K,\ \ldots \le N\)\( by counting the number of `o`s at these positions, we can determine the number of flowers that can be watered for that \)K$.

A naive approach of “for each \(K\), checking every position to determine whether it is a watered position” would take \(O(N)\) per \(K\), resulting in \(O(N^2)\) overall, which is too slow for \(N = 2 \times 10^5\).

The key observation is that “we only need to directly traverse the watered positions.” When \(K\) is fixed, the positions to check are only \(1, 1+K, 1+2K, \ldots\), and there are approximately \(N/K\) of them. Therefore, we can count in \(O(N/K)\) for each \(K\).

For example, if \(N=10, K=3\), we only need to check the 4 positions \(1, 4, 7, 10\) (since no other positions will ever be watered).

Algorithm

1. Convert the string \(S\) into an array \(a\) (mapping o to 1 and . to 0).
2. Iterate over all values of \(K\) from \(1\) to \(N\).
3. For each \(K\), traverse \(i = 0, K, 2K, \ldots\) (0-indexed) and sum up \(a[i]\).
   • This sum is “the number of flowers that can be watered with that \(K\).”
4. Output the maximum value as the answer.

In the code, range(0, N, k) is used to efficiently enumerate “only the watered positions.”

Complexity

• Time complexity: \(\displaystyle \sum_{K=1}^{N} O\!\left(\frac{N}{K}\right) = O(N \log N)\) (using the harmonic series \(1+\frac{1}{2}+\cdots+\frac{1}{N} = O(\log N)\))
• Space complexity: \(O(N)\) (for storing the array mapping o/. to ¹⁄₀)

Implementation Notes

• Positions are 1-indexed in the problem statement, but Python arrays are 0-indexed. By treating the first position (position 1) as index 0, checking 0, k, 2k, ... gives the correct correspondence.

• Instead of referencing S each time, converting it to an array a[i] of 0/1 values makes summation straightforward.

• Since the input can be large, using sys.stdin.readline is recommended for safety.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    S = input().strip()
    a = [1 if c == 'o' else 0 for c in S]

    ans = 0
    for k in range(1, N + 1):
        s = 0
        for i in range(0, N, k):
            s += a[i]
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.