PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Practice
Setter : Abhinav Jain
Tester : Alipasha Montaseri / Kasra Mazaheri
Editorialist : Anand Jaisingh
DIFFICULTY :
Medium
PREREQUISITES :
Dynamic Programming, Basic Geometry, Convex Hull Trick
PROBLEM :
You are given N labels A_1,A_2...A_N, and there exist N coconuts associated with them. For each i, there exists a coconut that requires exactly A_i hits to break open. You don’t know which coconut requires how many hits to op…
In the post author says that we need to use convex hull trick to solve the problem efficiently.I read the trick but i am unable to apply it to given problem .
Please look at this and love me.
I’m not going to introduce the knowledge before we get the DP equation, which is well illustrated in the official editorial.
First, the array should be sorted in descending order, and then we will get a DP equation.
dp[i][j] = min(dp[i-1][k] + (j - k)*val_j),(k < j)
Obviously, the time complexity is O(n^2z)
Let’s see what’s hidden in this formula.
Suppose we have two unknowns m_1 and m_2, they satisfy m_1 < m_2 < j
Their contributions to the formula are as follows:
S_1=dp[i-1][m_1]+(j-m_1…
6 Likes