Overview

A problem where \(K\) bags of fertilizer are distributed among \(N\) fruit trees to maximize the product of growth values. To maximize the product under a fixed total sum, we use the property that values should be as equal as possible, and find the optimal distribution using binary search.

Analysis

Key Insight: Maximizing the Product Means “Equalization”

From the AM-GM inequality (Arithmetic Mean - Geometric Mean inequality), when the sum is fixed, the product is maximized when all values are as equal as possible.

For example, when \(A = [1, 5]\), \(K = 2\): - \((1+2) \times 5 = 15\) (give all to the smaller one) - \((1+1) \times (5+1) = 12\) (distribute evenly) - \(1 \times (5+2) = 7\) (give all to the larger one)

The distribution that makes values closest to each other gives the maximum product. In other words, it is always optimal to give fertilizer to the tree with the smallest value.

Problem with the Naive Approach

Since \(K\) can be as large as \(10^{18}\), simulating the distribution one bag at a time is impossible.

Solution: Determine the “Water Level” Using Binary Search

Think of it as raising all trees up to a “water level \(V\)”. Trees with \(A_i < V\) are raised to \(V\), while trees with \(A_i \geq V\) remain unchanged. We use binary search to find the maximum \(V\) such that the raising cost is at most \(K\).

Algorithm

1. Sort the array: Sort \(A\) in ascending order.

2. Determine the water level \(V\) using binary search:

   • Cost to raise to water level \(V\): \(\text{cost}(V) = \sum_{A_i < V} (V - A_i)\)
   • Find the maximum \(V\) such that \(\text{cost}(V) \leq K\).
   • Using the sorted array and prefix sums, the cost can be computed in \(O(\log N)\).

3. Distribute the remainder:

   • Compute \(\text{remaining} = K - \text{cost}(V)\).
   • All trees that had \(A_i \leq V\) now have value \(V\) (\(\text{idx\_v}\) trees).
   • Distribute the remaining \(\text{remaining}\) bags of fertilizer one bag each to these trees (\(\text{remaining}\) trees become \(V+1\)).

4. Compute the product (mod \(10^9+7\)):

   • \(\text{remaining}\) trees with value \(V+1\) → \((V+1)^{\text{remaining}} \mod p\)
   • \((\text{idx\_v} - \text{remaining})\) trees with value \(V\) → \(V^{(\text{idx\_v} - \text{remaining})} \mod p\)
   • Trees with values greater than \(V\) keep their original values \(A_i\) and are multiplied in directly.

Complexity

• Time complexity: \(O(N \log N + N \log(\max(A) + K))\)
  • \(O(N \log N)\) for sorting, \(O(\log(\max(A)+K))\) for binary search (with \(O(\log N)\) binary search at each step), and \(O(N)\) for the final computation.
• Space complexity: \(O(N)\) (prefix sum array)

Implementation Notes

• Upper bound for binary search: The upper bound for \(V\) is \(A[0] + K\) (the case where everything is given to one tree when \(N=1\)), but since \(K\) can be as large as \(10^{18}\), be careful with the range of lo, hi.

• Efficient cost computation: Use bisect_left on the sorted array to find the number of elements less than \(V\) and their prefix sum, computing the cost in \(O(\log N)\).

• Guarantee that remaining ≤ idx_v: Since \(\text{cost}(V+1) > K\), the remainder is always at most the number of trees at water level \(V\) (otherwise, all of them could have been raised to \(V+1\)).

• Modular arithmetic: Use fast exponentiation (pow(base, exp, MOD)) to efficiently compute large powers.

  Source Code

import sys
import heapq

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i+2]) for i in range(N)]
    
    MOD = 10**9 + 7
    
    # Key insight: To maximize the product, we should always add fertilizer to the tree
    # with the smallest current growth value. This is because for fixed sum, the product
    # is maximized when values are as equal as possible.
    
    # Optimal strategy: sort A, then distribute K fertilizer bags to make values as equal as possible.
    # After optimal distribution, all values will be either floor(target) or ceil(target) for some target,
    # or more precisely, we level up from the smallest.
    
    A.sort()
    
    # We want to find the final value V such that all trees have value >= V,
    # and some might have V+1.
    # 
    # Strategy: binary search on the final "base level" V.
    # If all trees are raised to at least V, the cost is sum(max(0, V - A[i]) for all i).
    # If cost <= K, then we have leftover = K - cost, and we distribute leftover among N trees
    # (each getting +1), so `leftover` trees get V+1 and (N - leftover) trees get V.
    # But some trees might already be above V, those stay as they are.
    
    # More carefully: after raising all trees below V to V, trees already >= V stay unchanged.
    # Wait, no. We can only ADD fertilizer, not remove. So trees with A[i] > V stay at A[i].
    
    # Let's think again. We raise trees with A[i] < V to V. Trees with A[i] >= V stay at A[i].
    # Cost = sum(max(0, V - A[i])).
    # Then leftover K - cost is distributed one per tree to maximize product.
    # Best to add to trees with smallest values first, but all trees at level V are equal,
    # so we add 1 to any of them. Actually trees with A[i] > V also exist.
    # Hmm, but since we want max product, we should add +1 to trees with smallest current value.
    # After leveling to V, the smallest values are V (for those that were raised), 
    # and some A[i] >= V. So we add +1 to trees at value V first.
    
    # Binary search: find largest V such that cost(V) <= K
    # cost(V) = sum(max(0, V - A[i]) for i in range(N))
    
    # prefix sums for sorted A
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]
    
    def cost_to_level(V):
        # Number of trees below V: binary search
        import bisect
        idx = bisect.bisect_left(A, V)
        # cost = V * idx - prefix[idx]
        return V * idx - prefix[idx]
    
    import bisect
    
    # Binary search for V
    lo, hi = A[0], A[0] + K  # V can be at most A[0] + K (if N=1, but generally)
    # Actually hi can be very large. Let's think: max V is when all K go to raise minimum.
    # V can be at most A[0] + K but also limited by distribution among multiple trees.
    # Safe upper bound: A[-1] + K (more than enough)
    # But K can be 1e18, so hi can be ~2e18. That's fine for binary search.
    
    hi = A[0] + K  # if N=1
    if N > 1:
        hi = A[-1] + K  # safe upper bound
    
    while lo < hi:
        mid = (lo + hi + 1) // 2
        c = cost_to_level(mid)
        if c <= K:
            lo = mid
        else:
            hi = mid - 1
    
    V = lo
    remaining = K - cost_to_level(V)
    
    # Now: trees with A[i] < V are raised to V. Trees with A[i] >= V stay at A[i].
    # remaining fertilizer bags are distributed as +1 each.
    # To maximize product, +1 should go to trees with smallest value, i.e., those at V.
    # Count trees at value V (after leveling): all trees with original A[i] <= V become V.
    
    idx_v = bisect.bisect_right(A, V)  # trees with A[i] <= V: indices 0..idx_v-1, all at V
    # Trees at value V: idx_v of them
    # remaining <= idx_v (since cost(V+1) > K)
    # `remaining` of them become V+1, rest stay at V
    
    # Compute product mod MOD
    result = 1
    at_v = idx_v  # number of trees at level V
    plus_one = remaining  # how many get V+1
    stay = at_v - plus_one  # how many stay at V
    
    result = pow(V + 1, plus_one, MOD) * pow(V, stay, MOD) % MOD
    for i in range(idx_v, N):
        result = result * (A[i] % MOD) % MOD
    
    print(result % MOD)

solve()

This editorial was generated by claude4.6opus-thinking.