Paying by the tray

The packhouse pays by the tray, and a tray is worth the average of what sits on it. Where you put the dividers is the whole question.

The problem

Crates of strawberries come off the field on a belt and cannot be reordered. Each crate carries one sugar reading, taken by the refractometer at the picking shed. The buyer pays per tray, and a tray is worth the mean of the readings of the crates on it; the day's payment is the sum of the tray prices.

You have trays trays. Every crate must go on a tray, each tray must hold a contiguous run of crates in belt order, and no tray may be left empty. You may use fewer trays than you have. Choose the dividers so the payment is as large as possible.

Input. sugars — a list of integers, the reading on each crate in belt order. trays — an integer, how many trays the packhouse sent.

Output. The largest possible payment, as a number rounded to five decimal places.

Example.

sugars = [12, 4, 4, 4, 12], trays = 3   ->  28.0

Isolating the two strong crates gives [12] [4 4 4] [12], worth 12 + 4 + 12. Dividing anywhere else dilutes them: [12 4] [4] [4 12] is 8 + 4 + 8 = 20.

A second example, where the divider does not belong at the steepest drop:

sugars = [5, 1, 9, 2, 8], trays = 2   ->  12.25

The readings fall hardest between 9 and 2, and cutting there gives 5 + 5 = 10. The best single cut sits before the last crate: [5 1 9 2] averages 4.25, and the lone 8 is worth 8.

Constraints.

• 1 <= len(sugars) <= 100
• 0 <= sugars[i] <= 10^4
• 1 <= trays <= 200 — the packhouse may send more trays than there are crates
• An answer within 1e-6 of the true payment is accepted

Hints

Approach

Brute force

Try every set of dividers. With n crates there are n - 1 gaps and up to trays - 1 dividers to place in them, so the count is a sum of binomials that reaches 2^99 for a hundred crates — around 6 × 10^29 arrangements. Scoring each one costs another O(n).

The insight

Fix where the last tray starts and the crates before it become the same question with one tray fewer, because the price of that last tray does not depend on how the earlier crates were divided.

Trays hold contiguous runs and the belt order is fixed, so every arrangement of the first i crates into t trays is an arrangement of the first start crates into t - 1 trays followed by one tray holding crates start .. i-1. The two halves never interact — that independence is the optimal substructure a table needs. And a spare tray is never wasted: the mean of a merged tray is a weighted average of the two halves' means, so it is at most the larger of them, and with non-negative readings that is at most their sum. So "at most trays" is the same as "exactly min(trays, n)".

Algorithm

1. Build prefix sums so a tray's price is one subtraction and one division.
2. Clamp trays to min(trays, n).
3. Fill the one-tray row: row[i] is the mean of the first i crates.
4. For each further tray count t, set row[i] to the best of previous[start] + price(start, i) over all start from t - 1 to i - 1.
5. Answer: the last cell of the final row.

Complexity

Time O(k · n²) — one row per tray count, each of n cells scanning up to n divider positions; at n = k = 100 that is about a million additions. Space O(n), because only the previous row is ever read.

Solution

"""Paying by the tray — partition DP over a prefix of the belt and a tray count."""

NOT_FILLABLE = float("-inf")


def solve(sugars, trays):
    crates = len(sugars)
    if crates == 0:
        return 0.0
    # One crate per tray is the finest split there is; spare trays buy nothing,
    # and asking for more trays than crates would leave a tray empty.
    trays = min(trays, crates)

    running = [0.0] * (crates + 1)
    for i, reading in enumerate(sugars):
        running[i + 1] = running[i] + reading

    def price(start, stop):
        """What a tray holding crates start .. stop-1 is worth."""
        return (running[stop] - running[start]) / (stop - start)

    # row[i] = the best payout for the first i crates using exactly t trays.
    # Fewer than t crates cannot fill t non-empty trays, hence NOT_FILLABLE.
    row = [price(0, i) if i >= 1 else NOT_FILLABLE for i in range(crates + 1)]
    for t in range(2, trays + 1):
        nxt = [NOT_FILLABLE] * (crates + 1)
        # The last tray is a suffix start .. i-1; everything before it is the
        # same question one tray smaller, and the two parts never interact.
        for i in range(t, crates + 1):
            nxt[i] = max(row[start] + price(start, i) for start in range(t - 1, i))
        row = nxt
    return round(row[crates], 5)

TESTS = [
    (([12, 4, 4, 4, 12], 3), 28.0),
    (([5, 1, 9, 2, 8], 2), 12.25),
    (([12, 4, 4, 4, 12], 1), 7.2),
    (([3, 1, 4], 5), 8.0),            # more trays than crates: one crate each
    (([6], 1), 6.0),                  # a single crate on a single tray
    (([7, 7, 7, 7], 2), 14.0),        # every reading equal: any cut is optimal
    (([0, 0, 5], 2), 5.0),            # zero readings must not tempt a bad cut
]

Pitfalls

• Treating trays as an exact count. Five crates cannot fill 200 trays, so the table's final cell stays at negative infinity and the function returns nonsense. Clamp to min(trays, n) first.
• Integer division for the mean. total // count turns 7.2 into 7 and systematically favours long trays, which quietly changes the answer rather than crashing.
• Letting the divider sit at start == i. That is an empty tray and a division by zero; the earlier trays also need at least t - 1 crates between them, so start starts at t - 1, not at 0.
• Cutting greedily at the largest drop. The second example returns 10 that way instead of 12.25.

Variants

• The espalier weave — the same "best answer ending here" table, but the prefix is replaced by a branching tree.
• The pier ticker — a partition problem where the order is yours to choose, which costs you an exponential state.