Shouldn’t this be O(N)
Could you describe your solution in brief? @anand20 mentioned you’re using convex hull trick without binary search. Could you shed some light on that. Thanks!
Maybe it’s a dumb question, but I couldn’t understand why this problem cannot be solved with Divide and Conquer Optimization.
Someone? 
Is your scan function faster than fastIO generally used by c++ programmers?
No, we have to sort the given array right ?
1 Like
Many solutions have passed with simple greedy approaches and most of them don’t seem to have used cht… Maybe this editorial could be much more easy in term of advanced concepts? Nice editorial btw 
I believe it can be solved using divide and conquer optimization
1 Like
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)