DP Optimization Black Magic

Convex hull trick and Li Chao trees, Knuth and divide-and-conquer optimization, the Aliens trick, and SMAWK.

0 / 8 solved

Question Tags Difficulty Success

li-chao-treeconvex-hull-trick +2

Hard —

li-chao-treecomplexity +1

Hard —

quadrangle-inequalityknuth-optimization +2

Hard —

divide-and-conquer-dpdecision-monotonicity +1

Hard —

aliens-tricklagrangian-relaxation +2

Insane —

convex-hull-trickdp-optimization +2

Insane —

aliens-trickcollinear-hull-points +2

Insane —

smawktotally-monotone-matrix +2

Insane —

8 of 8 questions here are still unsolved.