Overview

This problem asks us to maximize the number of trees contained within an interval of length at most \(K\), given \(N\) trees arranged in a straight line. We solve it efficiently by combining sorting and binary search.

Analysis

Key Observations

1. Align interval endpoints with tree positions: The optimal interval will always have one of its left (or right) endpoints at a tree’s position. This is because shifting an interval to a position that contains no additional trees serves no purpose.

2. Effectiveness of sorting: When we sort the tree coordinates, trees contained in the interval \([X_i, X_i + K]\) form a contiguous range of indices. This transforms the problem into: “For each \(i\), find the maximum \(j\) such that \(X_j \leq X_i + K\).”

Issues with the Naive Approach

Checking whether \(X_j - X_i \leq K\) for all pairs of trees \((i, j)\) requires \(O(N^2)\) time, which results in TLE (Time Limit Exceeded) under the constraint \(N = 2 \times 10^5\).

Solution

By using binary search on the sorted array, we can find the rightmost index for each tree in \(O(\log N)\) time.

Algorithm

1. Sort the coordinates: Sort the tree coordinates \(X\) in ascending order.

2. Search using each tree as the left endpoint: For \(i = 0, 1, \ldots, N-1\), do the following:

   • Set the left endpoint of the interval to \(X_i\) and the right endpoint to \(X_i + K\)
   • Use binary search (bisect_right) to find the index \(j\), which is one past the rightmost tree with coordinate at most \(X_i + K\)
   • The number of trees in the interval is \(j - i\)

3. Update the maximum: Find the maximum number of trees across all \(i\).

Concrete Example

For \(N = 5\), \(K = 4\), \(X = [1, 3, 5, 8, 10]\) (already sorted):

Left \(X_i\)	Right \(X_i + K\)	Trees in range	Count
1	5	1, 3, 5	3
3	7	3, 5	2
5	9	5, 8	2
8	12	8, 10	2
10	14	10	1

Therefore, the answer is 3.

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(N \log N)\) for performing binary search for each tree
• Space complexity: \(O(N)\)
  • Size of the array storing coordinates

Implementation Notes

• bisect_right(X, right) returns “the position of the first element greater than right”. In other words, all elements at most right exist at indices \(j - 1\) or less, so \(j - i\) gives the number of trees in the interval.
• You can either fix the left endpoint and search for the right endpoint, or fix the right endpoint and search for the left endpoint—both methods yield the same result.
• This can also be solved in \(O(N)\) using the two-pointer technique, but binary search is sufficiently fast.

Source Code

import bisect

def solve():
    N, K = map(int, input().split())
    X = list(map(int, input().split()))
    
    # Sort the coordinates
    X.sort()
    
    max_count = 0
    
    # For each tree as the left endpoint, count how many trees are in the interval [X[i], X[i] + K]
    for i in range(N):
        left = X[i]
        right = left + K
        
        # Use binary search to find the maximum index where value <= X[i] + K
        # bisect_right returns the first position greater than right, so everything before that is in range
        j = bisect.bisect_right(X, right)
        
        count = j - i
        max_count = max(max_count, count)
    
    print(max_count)

solve()

---

This editorial was generated by claude4.5opus.