Overview

Based on the stem lengths \(A_i\) of the flowers, we use binary search and a greedy method to find the minimum \(D\) such that all flowers can be assigned to \(K\) bouquets (each containing at most \(M\) flowers) where the “max − min” of each bouquet is at most \(D\).

Analysis

Key Insight 1: After sorting, flowers in the same bouquet can be a contiguous segment

The stem length condition depends only on “the difference between the maximum and minimum values.”
If we consider the sequence \(A\) sorted in ascending order, once the minimum and maximum values of flowers in a bouquet are determined, there is no reason to assign the flowers between them (in sorted order) to a different bouquet.
Therefore, if a solution exists, we can think of it as partitioning the sorted array into several contiguous segments, where each segment corresponds to a bouquet.

Key Insight 2: When \(D\) is fixed, a greedy approach can minimize the “number of bouquets needed”

When \(D\) is fixed, each bouquet must satisfy: - max − min within the segment \(\le D\) - length (number of flowers) of the segment \(\le M\)

In this case, scanning from left to right:

Starting from the leftmost unassigned flower, greedily pack as many flowers as possible (up to \(M\)) into the same bouquet while satisfying the conditions.

This greedy approach minimizes the number of bouquets used (reducing the number of flowers taken per bouquet only increases the number of bouquets needed later, so taking the maximum each time is optimal).

Therefore, if the number of bouquets used by this greedy approach is at most \(K\), it is feasible.
(There are exactly \(K\) bouquets available, but empty bouquets are allowed, so “required count \(\le K\)” is sufficient.)

Why the Naive Approach Fails

• “Searching through all assignments” or “counting partitions with DP” won’t work in time for \(N \le 2 \times 10^5\).
• Exhaustively trying all values of \(D\) is also impossible since \(A_i\) can be up to \(10^9\).

Therefore, we reduce the problem to: - Binary search on \(D\) - Feasibility check for a fixed \(D\) using \(O(N)\) greedy + two pointers

Algorithm

1. Binary Search Target

The answer \(D\) is a non-negative integer, and as \(D\) increases, the condition becomes more relaxed, so “feasible” is monotonically increasing.
Thus, we can binary search for the minimum \(D\).

The search range is: - Lower bound: \(-1\) (sentinel for infeasible) - Upper bound: \(A_{\max} - A_{\min}\) (with this value, the “difference condition” is always satisfied, so only capacity matters. Since the constraints guarantee \(K \times M \ge N\), it is always feasible)

2. Feasibility Check ok(D) (\(O(N)\))

Assuming \(A\) is sorted, we create bouquets from left to right.

• Pointer \(i\): the position of the leftmost flower to be assigned next
• Pointer \(r\): the maximum position satisfying \(A[r] - A[i] \le D\) (extended monotonically using two pointers)
• Since each bouquet can contain at most \(M\) flowers, the actual end of the segment for this bouquet is:
  \(end = \min(r,\ i + M - 1)\)
• Move to \(i = end + 1\) next
• If the number of bouquets groups created this way exceeds \(K\), it is infeasible; if we process everything, it is feasible

With two pointers, \(r\) increases at most \(N\) times in total, so the check is linear.

Small Example

For \(A = [1, 2, 3, 10, 11],\ M = 2,\ D = 1\): - \(i = 0\) (starting from 1): With \(D = 1\), \(r\) extends to 2 (value 3), but \(M = 2\) so \(end = 1\) → [1, 2] - Next \(i = 2\) (starting from 3): \(r = 2\) → [3] - Next \(i = 3\) (starting from 10): \(r = 4\), \(M = 2\) → [10, 11]
Total: 3 bouquets. Feasible if \(K \ge 3\).

Complexity

• Time complexity: Sorting \(O(N \log N)\) + binary search \(O(\log(A_{\max} - A_{\min}))\) iterations of \(O(N)\) checks
  Overall: \(O(N \log N + N \log(A_{\max} - A_{\min}))\)
• Space complexity: \(O(N)\) (for storing the array)

Implementation Notes

• ok(D) only needs to check “whether the number of required bouquets is at most \(K\)” (leftover bouquets can be left empty).

• The two pointers \(r\) should not be reset for each \(i\); instead, use something like if r < i: r = i to maintain monotonicity, achieving \(O(N)\).

• For the binary search, maintaining “infeasible lo” and “feasible hi” makes the implementation safe (in the code: lo = -1, hi = A[-1] - A[0]).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    def ok(D: int) -> bool:
        a = A
        n = N
        k = K
        m = M
        i = 0
        r = 0
        groups = 0
        while i < n:
            groups += 1
            if groups > k:
                return False
            if r < i:
                r = i
            ai = a[i]
            while r + 1 < n and a[r + 1] - ai <= D:
                r += 1
            end = r
            lim = i + m - 1
            if end > lim:
                end = lim
            i = end + 1
        return True

    lo = -1
    hi = A[-1] - A[0]  # always feasible
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid

    print(hi)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.