### PROBLEM LINK:

**Author:** Nibir Pal

**Tester:** Soumyadeep Roy

**Editorialist:** Soumik Sarkar

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

Dynamic programming, Convex hull trick

### PROBLEM:

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.

### QUICK EXPLANATION

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

### EXPLANATION:

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 AND TESTER’S SOLUTIONS:

Author’s solution can be found here.