Overview

This is a problem where you sink a tree into the ground to harvest as many apples as possible just by reaching up. We need to find the optimal sinking depth and count the number of harvestable apples.

Analysis

Key Observations

1. Sinking deeper is always better

   • If you sink the tree by depth \(D\), all apples’ heights decrease by \(D\)
   • Lower apple heights make them easier to reach
   • Therefore, sinking as deep as possible is optimal

2. Limitation on sinking depth

   • There is a constraint: “the height of the lowest apple must not become less than \(1\) centimeter”
   • If the lowest apple’s height is \(H_{\min}\), then \(H_{\min} - D \geq 1\) must hold
   • Therefore, \(D \leq H_{\min} - 1\), meaning we can sink at most \(H_{\min} - 1\)

3. Condition for harvesting

   • The maximum reachable height is \(T + K\) centimeters
   • After sinking by depth \(D\), an apple’s height becomes \(H_i - D\)
   • Harvesting condition: \(H_i - D \leq T + K\), i.e., \(H_i \leq T + K + D\)

Concrete Example

For example, if \(T = 150\), \(K = 30\) (reachable height is \(180\) cm), and apple heights are \([100, 150, 200, 250]\): - \(H_{\min} = 100\), so we can sink at most \(D = 99\) - Harvesting condition: \(H_i \leq 180 + 99 = 279\) - All apples with height \(250\) or less can be harvested → 4 apples

Algorithm

1. Sort the apple heights \(H\) in ascending order
2. Obtain the minimum height \(H_{\min}\) (the first element after sorting)
3. Calculate the maximum sinking depth \(D = \max(0, H_{\min} - 1)\)
4. Calculate the reachable height threshold \(\text{threshold} = T + K + D\)
5. Use binary search on the sorted array to count the number of apples satisfying \(H_i \leq \text{threshold}\)

Using Binary Search

Naively checking every apple one by one takes \(O(N)\), but with a sorted array, we can efficiently count using bisect_right. bisect_right(H, threshold) returns the number of elements less than or equal to threshold.

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(\log N)\) for binary search
• Space complexity: \(O(N)\)
  • Array to store apple heights

Implementation Notes

1. Handling the case where \(D\) becomes negative

   • When \(H_{\min} = 1\), \(H_{\min} - 1 = 0\), so we cannot sink at all
   • \(H_{\min} < 1\) should not occur given the constraints, but using max(0, max_D) as a safeguard is recommended

2. Watch out for overflow

   • \(T\), \(K\), and \(H_i\) can be up to \(10^9\), so threshold = T + K + D can be approximately \(3 \times 10^9\)
   • In Python, there is no need to worry about integer overflow, but in other languages, use 64-bit integers

3. Minimum value of the sorted array

   • After sorting, the first element H[0] is the minimum, so there is no need to use the min() function separately

     Source Code

import bisect

def solve():
    N, T, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    # ソートする
    H.sort()
    
    # 木を沈める深さDを考える
    # すべてのりんごについて H_i - D >= 1 を満たす必要がある
    # つまり D <= H_i - 1 for all i
    # よって D <= min(H) - 1
    
    min_H = H[0]  # ソート済みなので最小値は先頭
    max_D = min_H - 1  # 沈められる最大深さ
    
    # 手が届く高さは T + K
    reach = T + K
    
    # 深さDで沈めると、りんごの高さは H_i - D になる
    # H_i - D <= reach となるりんごを収穫できる
    # つまり H_i <= reach + D
    
    # Dは 0 から max_D まで選べる
    # D = max_D のとき、H_i <= reach + max_D を満たすりんごの数が最大になる
    # （Dを大きくするほど、より多くのりんごに手が届く可能性がある）
    
    # 最適な D は max_D（可能な限り深く沈める）
    # ただし max_D < 0 の場合は D = 0
    D = max(0, max_D)
    
    # H_i <= reach + D を満たすりんごの個数を数える
    threshold = reach + D
    
    # ソート済み配列で二分探索
    count = bisect.bisect_right(H, threshold)
    
    print(count)

solve()

This editorial was generated by claude4.5opus.