Overview

A problem where you harvest the maximum number of apple trees from trees lined up in a straight line, using an interval of length at most \(K\).

Analysis

In this problem, the length of the interval where the cart is parked must be at most \(K\), and we want to maximize the number of trees within that interval.

First, the coordinates of the trees are given, but they may not be sorted. However, since the interval selection covers a continuous range, by sorting the tree positions, we can efficiently determine “how many trees are contained within a given interval.”

A naive approach would be to try all pairs of intervals \([X_i, X_j]\) and check whether their length is at most \(K\). However, this has a time complexity of \(O(N^2)\), which is not practical since \(N\) can be up to \(2 \times 10^5\) (TLE).

Therefore, we use the following approach: - Consider each tree \(X_i\) as the left endpoint of the interval, and set the right endpoint as \(X_i + K\). - Efficiently count the number of trees contained in the interval \([X_i, X_i + K]\).

On a sorted array, the operation of finding “how far elements not exceeding a certain value extend” can be done in \(O(\log N)\) using binary search. In Python, this can be easily achieved using bisect.bisect_right.

Specifically, for each \(i\), we find the number of trees in the interval \([X_i, X_i + K]\) as follows: - Find the largest index not exceeding the right endpoint \(X_i + K\) using bisect.bisect_right(X, X[i] + K), and subtract \(i\) from it to get the count.

Even with this exhaustive search over all starting points, the overall complexity is \(O(N \log N)\), which is sufficiently fast.

Algorithm

1. Sort the coordinate list \(X\) of the trees.
2. For each \(i = 0, 1, ..., N-1\), do the following:
   • Set the right endpoint of the interval as \(R = X_i + K\).
   • Find the largest index in \(X\) not exceeding \(R\) using binary search: pos = bisect.bisect_right(X, R)
   • The number of trees in this interval is pos - i.
   • Update the maximum value.
3. Output the maximum count.

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting, and \(O(N \log N)\) for binary search on each element.
• Space complexity: \(O(1)\) (no additional memory beyond the input is used)

Implementation Notes

• The coordinate data must be sorted.

• Use bisect.bisect_right to quickly find “the largest position that is at most \(X_i + K\).”

• The key idea is to fix the starting point of the interval, extend the endpoint by \(K\), and count the number of elements within that range.

  Source Code

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    X = list(map(int, data[2:]))
    
    X.sort()
    
    max_count = 0
    for i in range(N):
        # 区間 [X[i], X[i] + K] に含まれる木の本数を数える
        right_end = X[i] + K
        pos = bisect.bisect_right(X, right_end)
        count = pos - i
        if count > max_count:
            max_count = count
            
    print(max_count)

if __name__ == "__main__":
    main()

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