#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/aliens-trick-wqs-binary-search/gosha-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/aliens-trick-wqs-binary-search/gosha-implementation

Repovive

Gosha - Implementation - Aliens Trick (WQS Binary Search) | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Gosha - Implementation

The code structure

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)$ .