Gosha - Implementation

Here's the structure:

function solve(n, a, b, p[], u[])
    // Binary search on lambda1 for Poke Balls
    lo1 := -1, hi1 := 1
    while hi1 - lo1 > epsilon
        mid1 := (lo1 + hi1) / 2
        (exp, cnt1, cnt2) := bestWithPenalties(mid1, optimal_lambda2)
        if cnt1 > a then
            lo1 := mid1
        else
            hi1 := mid1
    return final answer adjusted by penalties
function bestWithPenalties(lambda1, lambda2)
    // Each Pokemon, pick best action
    total := 0, cnt1 := 0, cnt2 := 0
    for i from 1 to n
        options := compute all 4 options with penalties
        pick best, update totals
    return (total, cnt1, cnt2)

The inner binary search on $\lambda_2$ is nested inside.

Time: $O(n \log^2 C)$, Space: $O(n)$.

Time: $O(n \log C)$. Space: $O(n)$.