Min Plus Convolution (Convex and Arbitrary)

Forum

Problem

Tutorials #

• 🇯🇵 (suisen) 下に凸な数列同士の (min, +) convolution - suisen のブログ
• 🇯🇵 (tatyam) Monge の手引書
• 🇯🇵 (kimiyuki) Monotone minima | Kyopro Encyclopedia of Algorithms
• 🇯🇵 (tmaehara) Totally Monotone Matrix Searching (SMAWK algorithm) - 週刊 spaghetti_source - TopCoder部
• 🇯🇵 (kimiyuki) SMAWK algorithm | Kyopro Encyclopedia of Algorithms
• 🇬🇧 (ko_osaga) SMAWK algorithm as an alternative for D&C optimization

Other Resources #

• 🇯🇵 (ngtkana) ngtkana/bench_minplus_convolutions: Benchmarks of algorithms for convex min-plus convolutions