3

Given an integer k and a sorted histogram with n bars with heights a1, a2, a3,..., an(this sequence is non-decreasing since histogram is sorted). We have to pick k bars(1 <= k <= n) out of these n bars such that the area enclosed between chosen bars and the right wall of the histogram is minimum possible.

For example, for the sequence of heights {1, 3, 5, 9}, if we chose bars with heights 1, 5; the area enclosed with right wall will be 12 units and will look something like in the image (Assume the width of bars to be 1 unit.)

Example Histogram

After trying a few greedy approaches (which were wrong) I moved to following Dynamic Programming solution:

Define dp[i][j][last] as the minimum area when picking j bars out of first i bars from the histogram such that previous bar we took to our right had an index last.

dp[i][j][last] = min(dp[i - 1][j][last], dp[i - 1][j - 1][i] + a[i] * (last - i));

But the problem is that it's too slow, its O(n2k), so I am hoping that somebody can help me optimize it to something like O(nk) or maybe suggest some faster greedy solution.

4
  • 1
    Re: "its O(n³)": If I'm understanding your approach correctly, it's actually O(n²k).
    – ruakh
    Jul 7, 2019 at 20:26
  • I must be misunderstanding. Say, k = 2. If I choose bars n and n-1, then the area enclosed between chosen bars and the right wall of the histogram is 0, and so is minimum. Same thing with k = 3, if I choose bars n, n-1, and n-2. Jul 7, 2019 at 20:37
  • @RobertBaron It is like the area under shadow if we throw light from left to right but also including the bars themselves. Note that the bars have width 1 unit. Jul 8, 2019 at 4:22
  • Can we assume that the bar hights must belong to the natural numbers?
    – Ninetails
    Jul 11, 2019 at 15:54

2 Answers 2

1

In the following I am going to assume that k >= 2, as the problem is trivial to solve otherwise.

Here is a partial solution, in the sense that it can solve some of the problem in O(n) time if the shape of the bars has some specific properties. Specifically we can infer the following:

If the volume covered by all the bars is convex, then the optimal solution has contains only bars at the beginning and the end.

Proof:

Assume there are any split in the solution, then we can move the group that is away from one of the edges toward one of the edges. This is done by deselecting a bar on one side and selecting a new on the other side. Since the shape is convex the curvature must be non-positive, then when we move in a non-increasing direction the reduction on further movement in that direction must be at least as big (the curvature ensures this). We can therefore move the split in the solution to one of the edges with no increase (and likely a decrease) in area covered.

We can check in O(n) time if the shape is convex (a non-increasing difference between the bars), and we can solve the problem with a sliding window optimization, which is simple to do in O(n). We can therefore preprocess any other solution with this to reduce the problem set to a problem containing at least one concave region. If we can find subproblems for other algorithms that also contain this property, then we can also solve those seperately in this sense.

For concave regions they may have a stable inner region (where new splits may be attracted to), in addition to the outer possible stable regions (where other splits may still be attracted to, because even though the difference in area on such a move is positive, the move might still be negative). Using this we can describe a fully concave region by the subsections where splits would move toward the edges or the stable midpoint.

Note that much of the above falls when concave and convex regions are connected, as the stability criteria depends on there being a border at the beginning and end that we measure from. While it might be possible to solve the full problem by building on this approach, I am not sure how much it would help on arbitarily complex shapes.

The requirement for a concave region to have an inner stable area tend to be quite harsh though (on a global scale), and I am not sure you can get very many of them on a global scale at all, so here is an algorithm that make use of this to solve the problem in either O(n), O(kn) or O(kn^2), depending on the complexity of the problem, by seiving through different heuristics and passing to a more expensive one if we are not sure we have found the optimal solution.

First we compute the base result, in the sliding window fashion (O(n)) and save that result. We then look for regions of stability for a single point (those outer regions are already considered in the by the sliding window) that points away from the edges, and have an area smaller than the solution found. If there are more than 1 of such points (requires a special shape) then default back to a base algorithm like Manish Chandra Joshi's. If a single such point is found we move on to the O(nk) solution, if none, the the current solution is accepted. Note that we could extend the version below to more than 1 of such points of global stability, but it would in practice require that they are fairly close, since they will tend to come up as failures later on otherwise.

In the 'O(kn)' solution we solve the sliding window seperately on both side of the global point of stability in the middle, for each of the kpossible amounts of assignments of bars to either side, and the select the best of these solutions. We then again look for regions of stability inside each of the regions (remember, this means a split wouldn't be moving toward an edge), and check whether the area of the the optimal of these points together with the central point we are computing for has a lower area than the lower of the 'O(kn)' and 'O(n)' solutions. If such a point is found we have to resolve to a full solution (like Manish Chandra Joshi's), otherwise we can accept the best of the 2 soluctions we have calculated.

Note that it should be possible include a larger border region as safe or easily derivable from a safe solution in the above algorithm, and thereby increase the amount of cases where we do not fall back to a slower algorithm. Particularly the area roughly 'k' away from from an edge may have simple solutions or in practise already be covored by earlier solutions. Note that computing the sliding windows as windows of non-covered area, we should be able to generate some simple solutions for such cases when combined with the data from the dynamic programming solutions in the 'O(kn)` case.

2
  • It is probably going to be a while before I have the time to really sit down and write out the full code for this, and I didn't plan on doing so initially, since no language tag was included with the question. I can understand that especially the last algorithm may be a bit too hairy in its explaination to stand on its own.
    – Ninetails
    Jul 8, 2019 at 0:52
  • @גלעדברקן I have a solution and wrote an answer. Jul 8, 2019 at 19:30
1

Ninetails's partial solution covers some part of the answer and I figured out other few cases that I will share.

I don't have a proof of it but the optimal bars we take always form runs of the forms 1010 or 10 or 01 or 010 or 101 or the trivial 1. (Here 1 means a series of bars we took and 0 means a series of bars we didn't take)

What this means is that the optimal bars always are in either one continuous group or in two contiguous groups with one group touching the very left. I have verified this fact using a random test generator with a O(2nn2) brute-force and the O(n2k) dynamic programming solution by running it for a few thousand cases.

So with this insight, we can easily find the answer in O(n * k) using prefix sum array for finding range sums efficiently. Here's the final code in C++(with few comments)

using ll = long long;
    ll n, z;
    cin >> n >> z;
    vector<ll> a(n);
    for (auto &e : a) {
        cin >> e;
    }
    assert(is_sorted(a.begin(), a.end()));

    ll stratAns, ans = INF;

    // prefix sum array
    vector<ll> pref(n + 1);
    for (int i = 1; i <= n; ++i) {
        pref[i] = pref[i - 1] + a[i - 1];
    }

    stratAns = INF;

    /// strategy 1 : handles cases where runs like 10, 01, 010, 1 are optimal to choose

    for (int starting = 0; starting + z - 1 < n; ++starting) {
        int ending = starting + z - 1;
        ll curAns = 0;

        //~ for (int i = starting; i <= ending; ++i) {
            //~ curAns += a[i];
        //~ }
        // doing the same with prefix sums instead
        curAns += pref[ending + 1] - pref[starting];

        curAns += a[ending] * (n - ending - 1);
        stratAns = min(stratAns, curAns);
    }
    ans = min(ans, stratAns);

    stratAns = INF;

    /// strategy 2 : handle cases when runs 1010 and 101 are optimal

    for (int last = z - 1; last < n; ++last) {
        for (int x = 1, y = z - 1; y > 0 && x < z; x++, y--) {
            assert(x + y == z);
            ll curAns = 0;

            //~ for (int i = 0; i < x; ++i) {
                //~ curAns += a[i];
            //~ }
            // performing the same with prefix sums instead
            curAns += pref[x];

            curAns += a[x - 1] * (last - y + 1 - x);

            //~ for (int i = last - y + 1; i <= last; ++i) {
                //~ curAns += a[i];
            //~ }
            // performing the same with prefix sums instead
            curAns += pref[last + 1] - pref[last - y + 1];


            curAns += a[last] * (n - last - 1);
            stratAns = min(curAns, stratAns);
        }
    }
    ans = min(ans, stratAns);
    cout << ans << endl;
7
  • It should be possible to have more complicated sequences, but they can be quite hard to hit in random data. The sequence [21,22,24,25,2000,3000] should have the form 01010 if you need to select 2 bars. I did have to write out the set of formula for the conditions to actually generate it: (y+2)b < a-1 and (1-y)a < b-1, where the first target has hight a, the second a+b and there are y+1 bars after the second target. Having more than one bar between the targets just makes it harder. As you can see, these are kind of hard to find with random generated tests.
    – Ninetails
    Jul 9, 2019 at 13:26
  • The optimal area for the case you gave is 99 units and the only way to obtain it is by choosing bars with 24 and 25 unit height. So they are of the form 001100 or in a compressed way just 010(one continuous block). Can you get even better area? EDIT: I used exhaustive 2^n brute-force to find this optimal answer. Jul 9, 2019 at 17:33
  • 1
    (You might want to mention @Ninetails, if you'd like them to be notified.) Jul 10, 2019 at 2:41
  • 1
    Let me try to go over the formulas again: There should be 3 relevant choices (with y =0), 11000, 00110, and 01010. Letting the first hight be a, the second be a+b, the extra number between the two steps xand the extra after the 2 step y. We require that the cost of 01010 in some configuration for it to be choosable. The cost of 01010 is 4a+2b +(ax+(a+b)y). The cost of 11000 is 5a-1+(ax+ay), and the cost of 00110 is 3a+3b-1+(ay+by). This gives us the inequalites: 4a+2b +(ax+(a+b)y)<5a-1+(ax+ay) and 4a+2b +(ax+(a+b)y)<3a+3b-1+(ay+by). Continued in next comment...
    – Ninetails
    Jul 10, 2019 at 14:49
  • 1
    Let us now simplify the inequalities: 4a+2b +(ax+(a+b)y)<5a-1+(ax+ay) => 2b +by<a-1 and 4a+2b +(ax+(a+b)y)<3a+3b-1+(ay+by) => a +ax< b-1. I can here see that I made a mistake in the x and y parts earlier, and any setting of x>0 and y>0 just make it worse, so we set them to 0 and get the simple set of inequalities: 2b < a-1 and a > b-1,which obviously cannot be satisfied, so we have just proven that 01010 can never happen, which also include all deriviatives, such as 101010, 0101010 and so on. With this knowledge I wonder whether we can find a O(n) solution.
    – Ninetails
    Jul 10, 2019 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.