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
Handsome boy, your greedy way is not feasible. Try this.
4 3
5 2 1 1
The correct answer is 6.
but your is 7.
1 Like
you are saying you are newbie… nice joke:joy:
you just literally raped (looted the honor) Editorialist and Setter by saying CIRMERGE can be solve in O(nlogn) and they are proposing the idea in O(n^3)…
1 Like
Nope, I don’t think that problem can be solved in O (nlogn), but the linear version can.
I think Editorialist is just misguided by the data range, which is not an uncommon optimization strategy.
I only won the silver medal in the China ACM-ICPC Regional Championships, which means that most people are better than me.
1 Like
Smart people never admit they are smart… 
3 Likes
I don’t think so since I was defeated by a lot of middle school students. 
1 Like
You lucky. China has a great education system.
When I was in middle school I used to eat dirt…
6 Likes
You guys are missing the point. Codechef is filled with 95% of beginners and intermediates. It was very necessary for them to solve it in O(n^3) so they can learn actual dynamic programming which most of them are not good at if we look at the statistics.
Many variations of this problem can’t be solved in O(n^2) or O(nlogn) for that matter.
But that was not the intended solution. No matter what platform it is, and no matter what is the motive of Codechef (whether to educate children), the first thing that a setter + tester for any CP problem has to do is make sure that intended complexity solution will only pass!
My solution here passes with O(n^3) complexity which I feel is the failure of the tester. CodeChef: Practical coding for everyone
In case the intended solution of this problem was not using a convex hull trick to optimise then the contraints must have been put up rightly.
I feel that a lot of people would not have submitted n^3 solution even after knowing it well, for the simple reason that the judge is not supposed to accept them for such constraints.
1 Like
I am extremely disappointed by Codechef, once again.
The dp is not very difficult to come up with, of course the CHT part is which means the n^3 solutions should be rejected, all of them.
Weak test cases though, once again.
1 Like