Maximize the minimum asset value within an upgrade budget

Clarify first. Asset i starts at values[i]. One upgrade costs costs[i] and adds values[i] again, so after k upgrades the asset is worth values[i] * (1 + k). Upgrades are whole steps, any asset can be upgraded any number of times, and the total spent must not exceed budget. Return the largest possible value of min(final values). Confirm: all inputs are positive integers, the budget may be 0, and unused budget is fine.

Brute force. Try every way to split the budget into upgrade counts. That is exponential in n and only useful as a test oracle.

Greedy is a trap. "Always upgrade the current minimum" fails: upgrading the smallest asset may be very expensive, and a single upgrade may not even raise the floor if a second asset is tied for the minimum. Mention it, then move on.

Key idea: binary search on the answer. Fix a target floor T. Each asset independently needs the fewest upgrades k with values[i] * (1 + k) >= T, which is max(0, ceil(T / values[i]) - 1). The cheapest way to reach floor T is to buy exactly those upgrades, so

cost(T) = sum(costs[i] * max(0, ceil(T / values[i]) - 1)).

cost(T) never decreases as T grows. So the affordable targets form a prefix [min(values), answer], and we binary-search its right end.

Bounds. lo = min(values) costs nothing. For the upper bound, even if the whole budget went to asset i, it could reach at most values[i] * (1 + budget // costs[i]). The floor cannot exceed the smallest of these caps, so that is hi. Using a tight hi keeps the search short and the numbers small.

Invariants.

• lo is always affordable; everything above hi is not.
• The feasibility check stops as soon as the running cost passes the budget. This keeps it fast and, in fixed-width languages, avoids overflow.

Reconstructing the plan. Once the floor F is known, the upgrade counts are max(0, ceil(F / values[i]) - 1). Leftover budget can go anywhere; it cannot raise the floor any further.

from __future__ import annotations


def upgrades_needed(value: int, target: int) -> int:
    """Fewest upgrades so that value * (1 + k) >= target."""
    if value >= target:
        return 0
    return (target + value - 1) // value - 1  # ceil(target / value) - 1


def cost_to_reach(values: list[int], costs: list[int], target: int, budget: int) -> int:
    """Cost to lift every asset to at least `target`; stops early past `budget`."""
    spent = 0
    for v, c in zip(values, costs):
        spent += upgrades_needed(v, target) * c
        if spent > budget:
            return spent  # already too expensive; no need to finish the sum
    return spent


def max_floor_value(values: list[int], costs: list[int], budget: int) -> int:
    """Largest achievable minimum value across all assets.

    Upgrading asset i once costs costs[i] and adds values[i] to its value,
    so after k upgrades it is worth values[i] * (1 + k).
    """
    if not values:
        raise ValueError("portfolio must not be empty")
    if len(values) != len(costs):
        raise ValueError("values and costs must have the same length")
    if budget < 0 or any(v <= 0 for v in values) or any(c <= 0 for c in costs):
        raise ValueError("values and costs must be positive, budget >= 0")

    # Spending nothing gives min(values). Spending the whole budget on a
    # single asset caps what that asset can reach, so the floor can never
    # exceed the smallest of those caps.
    lo = min(values)
    hi = min(v * (1 + budget // c) for v, c in zip(values, costs))

    # Feasibility is monotone in the target: if T is affordable, so is
    # every T' < T. Find the last affordable target.
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if cost_to_reach(values, costs, mid, budget) <= budget:
            lo = mid
        else:
            hi = mid - 1
    return lo


def upgrade_plan(values: list[int], costs: list[int], budget: int) -> list[int]:
    """Number of upgrades per asset that achieves the optimal floor."""
    floor = max_floor_value(values, costs, budget)
    return [upgrades_needed(v, floor) for v in values]

• upgrades_needed: O(1).
• cost_to_reach: O(n) time, O(1) space.
• max_floor_value: O(n log H) time, where H = min_i values[i] * (1 + budget // costs[i]). log H is at most about 64 for 64-bit inputs. O(1) extra space.
• upgrade_plan: the same as max_floor_value, plus O(n) space for the result.

• values=[3, 5, 2], costs=[2, 1, 3], budget=7 → 4. Upgrade asset 0 once (cost 2) and asset 2 once (cost 3): values [6, 5, 4]. Reaching 5 would need asset 2 at 6, which is two upgrades (cost 6), plus 2 for asset 0: total 8, over budget. Plan: [1, 0, 1].
• values=[2, 3], costs=[1, 2], budget=5 → 6. Asset 0 twice (cost 2), asset 1 once (cost 2). Target 7 costs 3 + 4 = 7.
• values=[4, 6, 3], costs=[3, 2, 1], budget=9 → 8. Target 9 would cost 6 + 2 + 2 = 10.
• values=[4, 4], costs=[1, 1], budget=0 → 4 (no budget; the floor is the current minimum).
• values=[7], costs=[3], budget=10 → 28 (a single asset: three upgrades, one unit of budget left over).
• values=[1, 1, 1], costs=[1, 1, 1], budget=5 → 2; with budget=6 → 3. A tie at the minimum means one upgrade alone does not move the floor.
• values=[10, 1], costs=[1, 100], budget=99 → 1; with budget=100 → 2. The cheap asset is not the bottleneck; the expensive one is.
• Empty portfolio, mismatched lengths, or non-positive values/costs → ValueError.

1. Each upgrade adds a fixed +1 (or +d[i]) instead of values[i]. The check becomes max(0, ceil((T - values[i]) / d[i])) upgrades. Binary search is unchanged. With +1 and equal costs, you can also sort and use prefix sums to "water-fill" the lowest assets in O(n log n) without a search.
2. Many budget queries. Precompute nothing per query; just run the binary search per query in O(n log H). If n is large and queries are many, sort assets by value and note that cost(T) only changes at the points values[i] * k; for the +1 variant, prefix sums make each check O(log n), so each query is O(log n log H).
3. Upgrade cost grows with each step (for example the k-th upgrade of asset i costs k * costs[i]). The cost to reach T is still monotone in T; replace the linear cost with the closed form costs[i] * k(k+1) / 2. Same search.
4. Return the plan, and spend leftovers well. Use upgrade_plan. If the follow-up asks to also maximize total value with the leftover budget, put it into the asset with the best values[i] / costs[i] ratio; this does not change the floor.
5. Very large numbers / other languages. In Java or C++, values[i] * (1 + k) and the running cost can overflow 64 bits. Stop the sum early when it exceeds the budget, and compute the cap with a saturating multiply.

Mid-level (L4)

• Clarifies the upgrade rule and turns it into values[i] * (1 + k).
• Sees that a fixed target makes each asset independent, and recognizes binary search on the answer.
• Writes a correct ceil and an off-by-one-free binary search, and tests ties and a zero budget.

Senior (L5)

• States why feasibility is monotone and why greedy "upgrade the minimum" fails, with a small counterexample.
• Chooses tight bounds, adds the early exit in the cost check, and states O(n log H).
• Returns the upgrade plan, not only the number, and handles invalid input.

Staff (L6+)

• Generalizes cleanly to other cost and gain models (additive steps, growing step costs) and says which still allow the search.
• Discusses overflow and saturating arithmetic, and how to serve many budget queries efficiently.
• Connects the problem to real capacity planning (raising the slowest stage of a pipeline) and explains which assumptions would break in practice.