The Trick From Aliens

Abstract:

There are many different problems where you are to maximize/minimize some quantity, given that you are allowed to perform up to K "actions". One example of this type of problem is where you have an array containing N integers (positive and negative), and you want to choose at most K disjoint subarrays such that the sum of the elements included in the subarrays is maximized. These problems can often be solved with dynamic programming yielding a time complexity of O(K * something). However if K is large, this extra factor is troublesome. The trick from aliens is a way of replacing the K factor with log(something else), massively improving the time complexity.

Some trivia: The name of the trick comes from a problem called Aliens at the International Olympiads in Informatics 2016. There you needed to use this trick which at the time was very obscure, and so since then the trick is commonly known as The Trick From Aliens. In academia it is commonly known as Lagrangian Relaxation.

Speaker: Gustav Nilsson Gisleskog