THE TRICK FROM ALIENS IN COMPETITIVE PROGRAMMING

Abstract

The scope of this article is presenting a very useful DP optimization technique, introduced in the competitive programming community with the problem Aliens at IOI 2016. The technique is used to reduce dimensions in particular DP configurations, by exploiting the convex nature of some cost functions. We will introduce the technique by starting with a simpler DP problem, show the optimization from