Rare
 0/12

LineContainer

Authors: Benjamin Qi, Andi Qu

Convex Containers

Half-Plane Intersection

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.
Example problem + implementation?
StatusSourceProblem NameDifficultyTagsSolutionURL
KattisNormalView Solution
JOIHardView Solution
Balkan OIVery Hard
Show Tags

Geometry, Binary Search

External Sol

LineContainer (aka O(NlogN)\mathcal{O}(N \log N) CHT)

StatusSourceProblem NameDifficultyTagsSolutionURL
YSNormalView Solution
Resources
KACTLsource of code that I (Ben) use
cp-algorelated topic (but not the same)

Example Problem

Focus Problem – read through this problem before continuing!

Analysis

Instead of focusing on the pillars that should be destroyed, let's instead focus on the pillars that remain.

The total cost consists of the cost due to height differences plus the cost of destroying unused pillars. The latter cost is equal to the cost to destroy all pillars minus the cost to destroy the remaining pillars.

Since the cost to destroy all pillars is constant, we can thus turn the problem into one about building pillars instead of destroying them!

From this, we get a basic DP recurrence. Let dp[i]dp[i] be the minimum cost to build the bridge so that the last build pillar is pillar ii.

dp[1]=w1dp[1] = -w_1 and the following recurrence holds:

dp[i]=minj<i(dp[j]+(hjhi)2wi)=minj<i(dp[j]+hj22hihj)+hi2wi\begin{aligned} dp[i] &= \min_{j < i}(dp[j] + (h_j - h_i)^2 - w_i)\\ &= \min_{j < i}(dp[j] + h_j^2 - 2h_ih_j) + h_i^2 - w_i \end{aligned}

Notice how

dp[j]+hj22hihjdp[j] + h_j^2 - 2h_ih_j

effectively describes a linear function y=mx+cy = mx + c, where m=2hjm = -2h_j, x=hix = h_i, and c=dp[j]+hj2c = dp[j] + h_j^2

This means that we can use CHT to compute dp[i]dp[i] efficiently!

However, since mm is not monotonic, we can't use linear CHT using a deque, so we must settle with O(NlogN)\mathcal{O}(N \log N).

Code

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
YSNormalView Solution
POINormal
Show Tags

DP, convex

View Solution
CEOIHard
Show Tags

DP, convex

External Sol
FHCHard
Show Tags

DP, convex

Check FHC
ACHardCheck AC
TLXHardCheck TLX
Old GoldHardExternal Sol

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on LineContainer!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.