CCC-Editorial

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. :kissing:
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…:smiley:
and ur whole strategy…:sweat_smile:

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. :grimacing::grimacing:

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…:sweat_smile::smile:

You’re welcome. I’m a newbie too. We can make progress together. :yum::yum:

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

my solution

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::joy::joy::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)…:joy::joy::rofl:

1 Like

Nope, I don’t think that problem can be solved in O (nlogn), but the linear version can.
:relaxed:
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… :stuck_out_tongue:

3 Likes

I don’t think so since I was defeated by a lot of middle school students. :sleepy:

1 Like