I believe the same. I even used it. But WA as implementing it resulted into a mess for me… Especially, when you select a part of array which has impure hits…
Okay, I think I understand @loopfree’s code (CodeChef: Practical coding for everyone). I will try to explain it in brief, although it seems hard explaining someone else’s code. I will assume you’ve read the Convex Hull Trick link as I might use terminology from it. @loopfree
Here goes:
Keep in mind that the array is sorted in decreasing fashion. I think the only ‘tough’ part is inside the for loop with a lot of while loops; so I’ll try to explain that part.
Let’s say you want to find dp[i][j]. You need to minimize the function for all x = dp[i-1][k] where k = 1 to j-1
You assume the stack already contains all the ‘relevant x’ among all those x values. Now if you read that CHT link above, you can see that as x increases, the slope of the minimum line keeps decreasing. Also interestingly in the code, the loop for j increases from i to n, and thus a[j] (which is x here) keeps decreasing. So once you find what is the minimum function value for a particular x, you can remove all intervals after this x. Also the stack has elements ordered according to slope, hence stack[top] has the least slope line. So the while loop at line 41 does exactly that. It safely removes elements from the stack until you get the answer for the current j. And the whole point of this paragraph is to show that you CAN safely remove all the elements up to the answer for j, removing the need for a binary search.
Line 42 simply calculates the value of dp[i][j]
Lines 43-45, now completes the CHT adding a[j] to the stack
I reckon it’s too messy, and someone can clean and correct my comment as he/she wishes.
2 Likes
Oh okay, right! (XXXXXXXXXXXXX)
Is cht necessary for this problem?
Well, my solution which gave AC was an O(N^2 Z) solution with constant optimization. So probably cht wasn’t ‘necessary’ for the given test cases. But with stronger test cases, I’m not sure of any other method which works. Can you describe the divide and conquer that you mention?
2 Likes
I think there is a solution easier than the convex hull thoughts.
We sort the powers A_i of the coconuts into increasing (non decreasing) order.
To open Z coconuts, we form a plan to hit the coconuts H_1, H_2, ... H_n times, with H_1 \le H_2 \le ... \le H_n, the sum of H_i as small as possible, and exactly Z of the H_i = A_i. (There are some details about how to execute on the plan, which I will ignore.) The problem is to choose which H_i = A_i, and which H_i to set just to satisfy the inequalities and minimize the sum of the H_i.
It happens that the optimal arrangement always has just one or two continuous blocks of H_i=A_i. And if there are two blocks, then one starts with i=1. In symbols, the optimal arrangement has the form H_1 = A_1, H_2 = A_2, ... H_i = A_i, then a gap, then H_j=A_j, H_{j+1}=A_{j+1}, ... H_k = A_k. The first sequence might have zero length, which could be viewed as i=0. After filling in the other H_i values, the H_i sequence becomes
A_1, A_2, ..., A_i, A_i, A_i, ..., A_i, A_j, A_{j+1}, ... A_{k-1}, A_k, A_k, A_k, ... A_k
With pre-calculating partial sums of A_i, for each possible i,j,k combination the sum of the H_i can be computed in constant time.
The number of H_i equal to A_i is i+(k-j+1) = Z. So given j,k, then i is fixed.
So the solution becomes iterating over all permitted values of j,k, calculating i, calculating the sum of the H_i, and minimising.
Time complexity O(N \cdot Z).
Space complexity O(N) to store the partial sums.
How do we prove the assertion that there are only two blocks? If there are two left hand edges with H_{i-1} \ne A_{i-1} and H_i = A_i, and H_{j-1} \ne A_{j-1} and H_j = A_j, then I think you can show that there is a better arrangement filling up the gap before H_i or the gap before H_j. The details of the argument would be a bit messy, but a picture or graph of the H_i and A_i may help.
3 Likes
nope, I use only the most common ones.
Thank you for your analysis of my code. 
In fact, I don’t know what CHT is. I just simplified the DP equation a little and found that the solution will certainly satisfy some properties, but finally I came to a conclusion similar to cht.
If someone wants to know what I think, I can write an article about the general strategy of this approach to similar problems.
7 Likes
yes plzzzz… i just want to know what u exactly think when u see this question…
and ur whole strategy…
It is same as N, the number of coconuts
plz see it
2 Likes
@loopfree you have pretty much knowledge, could u suggest can we solve it using simplex (linear inequalities).someone suggested me,we can solve it using simplex, is it possible. Simplex is not so well known topic in CP community.
can anyone help me out here, i am using divide and conquer optimization here but it is giving me WA link
the code commented is the base used which gave me AC (nearly) earlier in the contest ( gave tle in 1 case)
I don’t think it should be possible to use the simplex method. I haven’t found some suitable inequalities to transform this problem into a linear programming problem. 
You can solve it using the simplex method if you assume that the A_i are sorted. But I’m not sure how you would implement this as a CP solution. If I find out how to properly write using the math mode, I will give you an LP formulation.
Basically, your objective function is just over an indicator variable z that shows if you have solved the task or not. Assume that the A_i are sorted in decreasing order, and x_i is the number of hits on the i-th nut, then you need x_i >= x_(i+1) for i in [1, N-1]. For each nut, you have an indicator y_i variable that can be set to 1 if you can open the nut (so you have x_i - y_i >= A_i - 1 and 0 <= y_i <= 1). Finally, you need something like sum (y_i) - z >= Z - 1. And the objective is max z.
How did you came to conclusion similar to cht , is it through practice or did you spend lot of time observing ? i read your post and your explanation is nice.
I just want to optimize this DP formula very well. When I can’t think of any data structure and methods I’ve learned, I’m going to try a new strategy. Unexpectedly, this strategy is very effective. I don’t know what CHT is in advance, but it seems to come to the same conclusion.
1 Like
thanx a lot… it means a lot to me… i m just a newbie… who start cp… and there is lot of thing to learn…
You’re welcome. I’m a newbie too. We can make progress together. 
1 Like
i am unable to solve this even after reading editorial because i know only basic dp and dont know too much dynamic programming .i came to a solution without dp which is giving WA can you please figure out whats wrong in my approach or for which test case it is failing
following is my approach
1.find min and max in the list
2.find no of cocounts with power greater than min,let it be n
3.if (n+1)*min is samller than max then hits all coconuts with power greater than min and
make hits=(n+1)*min and remove a coconut with power min
else
hit coconut with max power and remove it from list
4.reduce the size of list by 1