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 O(N²) to  O(Nlog VAL) then reveal the full solution of the original problem. Apparently, the official name of this optimization technique is “parameter search” and the Chinese community calls it “wqs binary search”.

Scopul acestui articol reprezintă ilustrarea unei tehnici de optimizare a DP foarte utilă, introdusă în comunitatea de programare competitivă odată cu problema Aliens la Olimpiada Internațională de Informatică din 2016. Tehnica este utilizată pentru a reduce dimensiunile în anumite configurații DP, prin exploatarea caracterului convex al unor funcții de cost. Vom introduce această tehnică începând cu o problemă DP mai simplă, vom arăta optimizarea de la O(N²) la  O(Nlog VAL) , apoi vom dezvălui soluția completă a problemei originale. Aparent, denumirea oficială a acestei tehnici de optimizare este „căutare de parametri”, iar comunitatea chineză o numește „căutare binară wqs”.