Optimize invites under capacity constraints

You have n donors (n up to 100,000). For each donor i you know: p_online[i] (probability of donating if emailed), a_online[i] (expected donation conditional on donating), p_gala[i], a_gala[i]. Costs: c_online per person emailed, c_gala per gala attendee, plus gala fixed cost F_gala. You may email everyone, but you can invite at most K=100 donors to the gala; a donor cannot both be emailed and invited to the gala. Choose a set G (|G| ≤ K) to maximize expected total net revenue: sum_{i∈G}(p_gala[i]*a_gala[i] - c_gala) + sum_{i∉G}(p_online[i]*a_online[i] - c_online) - F_gala. Tasks:

1. Describe an O(n log n) algorithm to choose G. Provide correctness intuition and complexity. (Hint: rank donors by Δi = (p_galaa_gala - c_gala) - (p_onlinea_online - c_online) and take the top K with positive Δi.)
2. Extend your approach if some donors belong to households that must be invited as a group (all-or-nothing) with varying group sizes; state how this becomes a 0/1 knapsack variant and propose an algorithm or approximation suitable for n=1e5.
3. Explain how you'd incorporate uncertainty in p and a (e.g., prediction intervals) to produce a risk-aware selection.

Optimize Gala Invites Under Capacity Constraints

A nonprofit can reach each of n donors either by email (online) or by inviting them to a gala, but not both. For each donor i you are given four parallel arrays: p_online[i] (probability of donating if emailed), a_online[i] (expected gift amount conditional on donating online), p_gala[i], and a_gala[i] (the gala analogues). There are per-person costs c_online (per emailed donor) and c_gala (per gala attendee), plus a one-time gala fixed cost F_gala. You may email everyone, but the gala venue holds at most K donors, so you may invite at most K donors to the gala.

Let the gala be held regardless (so F_gala is always paid). Choose a set G with |G| <= K to maximize the expected total net revenue:

sum_{i in G} (p_gala[i]*a_gala[i] - c_gala)

• sum_{i not in G} (p_online[i]*a_online[i] - c_online)

• F_gala

Return the maximum achievable expected total net revenue, rounded to 6 decimal places.

Approach (O(n log n)): Start from the baseline where every donor is emailed: base = sum_i (p_online[i]*a_online[i] - c_online) - F_gala. Moving donor i from email to the gala changes the objective by delta_i = (p_gala[i]*a_gala[i] - c_gala) - (p_online[i]*a_online[i] - c_online). Because the only constraint is the count |G| <= K, the moves are independent: greedily apply the moves with the largest positive delta_i, up to K of them, stopping once delta_i <= 0. Sorting the deltas dominates at O(n log n).

Constraints

• 0 <= n <= 100000
• All four probability/amount arrays have the same length n
• 0 <= p_online[i], p_gala[i] <= 1
• a_online[i], a_gala[i] >= 0
• 0 <= K (gala capacity); typically K = 100
• c_online, c_gala, F_gala >= 0
• The gala fixed cost F_gala is always paid (the gala is held regardless of |G|)

Examples

Example 1

Input: ([0.5], [100], [0.8], [1000], 1.0, 100.0, 20000.0, 100)
Output: -19300.0

Explanation: One donor. Online value = 0.5100 - 1 = 49. Gala value = 0.81000 - 100 = 700, so delta = 651 > 0 and the donor is moved to the gala. base = 49 - 20000 = -19951; total = -19951 + 651 = -19300. The large fixed cost dominates.

Example 2

Input: ([0.1, 0.1, 0.1], [10, 10, 10], [0.9, 0.9, 0.9], [1000, 1000, 1000], 1.0, 100.0, 0.0, 2)
Output: 1600.0

Explanation: Each online value = 0.110 - 1 = 0; each gala value = 0.91000 - 100 = 800, so delta = 800. K = 2 caps the gala at two donors. base = 0; total = 0 + 800 + 800 = 1600. The third donor stays online despite a positive delta because of the capacity limit.

Hints

1. Rank donors by Delta_i = (p_gala[i]*a_gala[i] - c_gala) - (p_online[i]*a_online[i] - c_online): this is the marginal gain of moving donor i from email to the gala.
2. Since the only constraint is the count |G| <= K, the moves are independent — there is no interaction between donors — so a greedy pick of the top-K positive deltas is optimal.
3. Compute the all-online baseline first (sum of online values minus F_gala), then add only the positive deltas among the top K. Never take a delta <= 0.
4. Sorting the deltas is the O(n log n) bottleneck; you could also use a partial selection (e.g. a size-K heap) for O(n log K).