Overview

Given a row of flower beds, the problem asks to optimally choose the interval \(K\) of a sprinkler that waters every \(K\)-th bed starting from the first, in order to maximize the number of flowers watered.

Analysis

Problem Setup

The sprinkler waters positions \(1, 1+K, 1+2K, \ldots\). Thinking in 0-indexed terms, the beds at positions \(0, K, 2K, 3K, \ldots\) are watered.

For example, with \(N = 10\) and \(S = \) o.oo.o.oo.: - \(K = 1\): positions \(0,1,2,3,4,5,6,7,8,9\) → all beds are checked, so the total number of flowers \(= 5\) - \(K = 3\): positions \(0,3,6,9\) → o, o, ., . → \(2\) flowers - \(K = 2\): positions \(0,2,4,6,8\) → o, o, ., ., o → \(3\) flowers

Since the number of flowers watered changes for each value of \(K\), we try all values of \(K\) and find the maximum.

Complexity of the Naive Approach

For \(K = 1\), we check \(N\) beds; for \(K = 2\), we check \(N/2\) beds; for \(K = 3\), we check \(N/3\) beds; and so on. The total computation is:

\[\sum_{K=1}^{N} \frac{N}{K} = N \sum_{K=1}^{N} \frac{1}{K} \approx N \ln N\]

This is known as the harmonic series and is \(O(N \log N)\). When \(N = 2 \times 10^5\), this amounts to roughly \(2 \times 10^6\) operations, which runs sufficiently fast.

Why Brute Force Works

At first glance, there are \(N\) possible values of \(K\), and for each \(K\) we check up to \(N\) beds, making it appear to be \(O(N^2)\). However, since larger values of \(K\) result in fewer beds to check, the total sum is bounded by \(O(N \log N)\).

Algorithm

1. For each \(K = 1, 2, \ldots, N\), do the following:
   • Check positions \(0, K, 2K, 3K, \ldots\) (within the range less than \(N\)) in order
   • If the character at that position is o, increment the count by \(1\)
2. Output the maximum count across all values of \(K\)

Complexity

• Time complexity: \(O(N \log N)\)
  • From the harmonic series \(\sum_{K=1}^{N} \lfloor N/K \rfloor = O(N \log N)\)
• Space complexity: \(O(N)\)
  • Only for storing the string \(S\)

Implementation Notes

• The problem statement uses 1-indexed positions (\(1, 1+K, 1+2K, \ldots\)), but in the program, using 0-indexed with range(0, N, K) handles this naturally.

• Python’s range(0, N, K) enumerates values \(0, K, 2K, \ldots\) in steps of \(K\) up to less than \(N\), making the inner loop concise to write.

• The implementation is straightforward: for each \(K\), compute count and update the running maximum best by comparison.

  Source Code

import sys

def solve():
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().strip()
    
    best = 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 > best:
            best = count
    
    print(best)

solve()

---

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