Overview

Given the state of each section of a flower bed, the problem asks to find the maximum number of flowers that can be watered when watering every K-th section starting from the first one.

Analysis

If we straightforwardly implement the problem’s conditions, for each K (from 1 to N), we examine sections at every K-th interval. For each K, the number of sections to examine is approximately N/K, so the overall computational complexity is N * (1 + ¹⁄₂ + ¹⁄₃ + … + 1/N) ≈ O(N log N). Since the maximum value of N is 2×10^5, this is sufficiently feasible.

Algorithm

1. Read the number of sections N and the state string S as input
2. Vary K from 1 to N, and for each K, examine the sections to be watered
3. For each K, count the sections at positions 0, K, 2K, … that contain a flower (‘o’)
4. Output the maximum count among all values of K

Complexity

• Time complexity: \(O(N \log N)\)
  • The number of sections examined for each K is approximately \(N/K\), and the sum from K=1 to N forms a harmonic series, resulting in \(O(N \log N)\)
• Space complexity: \(O(N)\)
  • Only memory for storing the input string is used

Implementation Notes

• Use a while loop to efficiently compute positions at every K-th interval

• Note that indices start from 0 (the problem uses 1-based positions, but the program processes them as 0-indexed)

• Compare the count for each K and maintain the maximum value

  Source Code

import sys

def main():
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    s = data[1]
    
    max_count = 0
    for k in range(1, n + 1):
        count = 0
        i = 0
        while i < n:
            if s[i] == 'o':
                count += 1
            i += k
        if count > max_count:
            max_count = count
            
    print(max_count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.