CLDSIN - Editorial



Author: Nibir Pal
Tester: Soumyadeep Roy
Editorialist: Soumik Sarkar




Dynamic programming, Convex hull trick


The problem is to find the minimum cost that Superman has to pay his disciples in order to disable all the installations according to the rules provided in the problem statement.


The problem can be solved using a dynamic programming approach of complexity O(n^2). However, this will result in TLE. The code can be optimized to linear time complexity using what is known as the Convex Hull Trick


We try to construct a recurrence relation from the provided problem statement.
Let f(i) be the minimum cost for the first i installations. Then we can deduce the following recurrence relation
f[i]$=R+min{(f[i]-f[j])^2} for all 1<=j<=$i
However this is too slow the to pass all test cases. We’re checking all f[j] for each f[i], but that is quite unnecessary.

Using the convex hull trick, we can solve the problem in linear time. The reader is advised to refer to the provided article for information about the principle and its working.

We can model our lines added to the data structure in the form of:
y$=mx+c**, where **m=-2*P[j]** and **c= dp[j]+P[j]^2**. At the **i**th installation, we put **x=$P[i] and the value of y added to R becomes our cost. We observe that we do not need to sort these lines by slope, because the input in provided in sorted order. Adding of lines can be done as described in the PEGWiki article.

Now let there be a line l1 and a line l2 added after it. So, l1 has higher slope than l2. Now if for any P[i1], the cost using l2 is less than that using l1, then for no P[i2] such that P[i2]$>$P[i1] will the cost using l1 be less than that using l2. Therefore, if we cover all P[i] in increasing order, we can remove all lines satisfying this criteria without hesitation. Once again, because the values are already sorted, simply traversing P from P[1] to P[N] fulfils this condition.


Author’s solution can be found here.