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

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

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

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

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

Repovive

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

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

IOI Aliens - Implementation

High-level structure

function solve(points, k)
    preprocess points (sort, remove dominated)
    binary search on lambda
    for each lambda, compute dp with CHT
    count photos used
    adjust search range
    return optimal cost - k * lambda

function dpWithCHT(lambda)
    hull := empty convex hull structure
    for i from 1 to n
        dp[i] := query hull at position x[i] + lambda
        add line for point i to hull
    return (dp[n], count)

The CHT handles the quadratic cost function. Combined with Aliens Trick. Time: $O(n \log n \log C)$ , Space: $O(n)$ .

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

Space complexity: $O(n)$ .