You are given an array of positive integers of size N. You can choose any positive number x such that x<=max(Array) and subtract it from all elements of the array greater than and equal to x. This operation has a cost A[i]-x for A[i]>=x. The total cost for a particular step is the sum(A[i]-x). A step is only valid if the sum(A[i]-x) is less than or equal to a given number K. For all the valid steps find the minimum number of steps to make all elements of the array zero.

0<=i<10^5
0<=x<=10^5
0<k<10^5

Can anybody help me with any approach? DP will not work due to high constraints.

CodePudding user response：

Just some general exploratory thoughts.

First, there should be a constraint on N. If N is 3, this is much easier than if it is 100. The naive brute force approach is going to be O(k^N)

Next, you are right that DP will not work with these constraints.

For a greedy approach, I would want to minimize the number of distinct non-zero values, and not maximize how much I took. Our worst case approach is take out the largest each time, for N steps. If you can get 2 pairs of entries to both match, then that shortened our approach.

The obvious thing to try if you can is an A* search. However that requires a LOWER bound (not upper). The best naive lower bound that I can see is ceil(log_2(count_distinct_values)). Unless you're incredibly lucky and the problem can be solved that quickly, this is unlikely to narrow your search enough to be helpful.

I'm curious what trick makes this problem actually doable.

I do have an idea. But it is going to take some thought to make it work. Naively we want to take each choice for x and explore the paths that way. And this is a problem because there are 10^5 choices for x. After 2 choices we have a problem, and after 3 we are definitely not going to be able to do it.

BUT instead consider the possible orders of the array elements (with ties both possible and encouraged) and the resulting inequalities on the range of choices that could have been made. And now instead of having to store a 10^5 choices of x we only need store the distinct orderings we get, and what inequalities there are on the range of choices that get us there. As long as N < 10, the number of weak orderings is something that we can deal with if we're clever.

It would take a bunch of work to flesh out this idea though.

CodePudding user response：

I may be totally wrong, and if so, please tell me and I'm going to delete my thoughts: maybe there is an opportunity if we translate the problem into another form?

You are given an array A of positive integers of size N.

Calculate the histogram H of this array.

The highest populated slot of this histogram has index m ( == max(A)).

Find the shortest sequence of selections of x for:

• Select an index x <= m which satisfies sum(H[i]*(i-x)) <= K for i = x 1 .. m (search for suitable x starts from m down)

• Add H[x .. m] to H[0 .. m-x]

• Set the new m as the highest populated index in H[0 .. x-1] (we ignore everything from H[x] up)

• Repeat until m == 0

If there is only a "good" but not optimal solution sought for, I could imagine that some kind of spectral analysis of H could hint towards favorable x selections so that maxima in the histogram pile upon other maxima in the reduction step.