7
\$\begingroup\$

I have encountered the following problem that I found very interesting to solve:

Given an array of positive integers {a1, a2, ..., an} you are required to partition the array into 3 blocks/partitions such that the maximum of sums of integers in each partition is the minimum it can be. Restriction: you cannot alter the turn in which the numbers appear (example: if you have {2, 5, 80, 1, 200, 80, 8000, 90} one partition CANNOT be the {2, 80, 1, 90}). The program must output ONLY the maximum sum, not the partitions.

So, for example let's have the array:

{2, 80, 50, 42, 1, 1, 1, 2}

The best partitioning according to the problem is:

{ {2, 80}, {50}, {42, 1, 1, 1, 2} }

so the output of the program in this case would be 82.

I have already thought of a \$O(n^2)\$ algorithm, but isn't there any better (e.g. \$O(n)\$ or \$O(n\log n)\$) algorithm?

My \$O(n^2)\$ algorithm:

#include <stdio.h>  
#include <iostream>  

using namespace std;  

int main() {  

    int n, *arr, onee = 0, twoo, threee, total = 0, maxx = -1, temp_maxx;

    cin >> n;
    arr = new int[n];

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        total += arr[i];
    }

    // O(n^2) is the following

    for (int i = 1; i < n - 1; i++) {
        onee += arr[i - 1];
        twoo = 0;
        for (int j = i + 1; j < n; j++) {
            twoo += arr[j - 1];
            threee = total - twoo - onee;
            temp_maxx = max(max(onee, twoo), threee);
            if ((temp_maxx < maxx) || (maxx == -1))
                maxx = temp_maxx;
        }
    }

    cout << maxx;

    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Which version of C++ are you using? \$\endgroup\$ – Pimgd Feb 13 '15 at 14:55
  • 3
    \$\begingroup\$ CROSS POST: cs.stackexchange.com/questions/38330/a-partition-algorithm \$\endgroup\$ – Pimgd Feb 13 '15 at 14:56
  • 2
    \$\begingroup\$ I don't see how the algorithm qualifies as dynamic-programming, so I've removed the tag. \$\endgroup\$ – 200_success Feb 13 '15 at 18:13
  • 6
    \$\begingroup\$ Deleting a question after you have received an answer would be the worst possible insult to those who have volunteered the time to read, answer, and vote on your question. That is absolutely not allowed. \$\endgroup\$ – 200_success Feb 13 '15 at 22:53
  • 2
    \$\begingroup\$ @D.W. But every question on CR also allows answers that criticize other aspects of the code, so the questions are not redundant. \$\endgroup\$ – Gilles Feb 13 '15 at 23:54
2
\$\begingroup\$

Edit:Previous algorithm failed, redo the algorithm completely.

Start with a full mid part, and distribute its values to its best neighbor until it is not the greatest part:

unsigned int get_min_partition3_value(const std::vector<unsigned int>& v)
{
    const unsigned int total_sum = std::accumulate(v.begin(), v.end(), 0u);
    auto it1 = v.begin();
    auto it2 = v.end();
    unsigned int part1 = 0;
    unsigned int part2 = total_sum;
    unsigned int part3 = 0;
    unsigned int res = part2;

    while (part1 < part2 && part3 < part2) {
        res = part2; // part2 is greater than part1 and part3
        if (part1 + *it1 < part3 + *(it2 - 1)) {
            part1 += *it1;
            part2 -= *it1;
            ++it1;
        } else {
            --it2;
            part3 += *it2;
            part2 -= *it2;
        }
    }
    res = std::min(res, std::max(part1, part3));
    return res;
}

Live demo. (For C++03, replace auto by std::vector<unsigned int>::const_iterator)

Complexity is O(n).

Previous not working live example.

\$\endgroup\$
  • \$\begingroup\$ Can you rewrite it for older C++ versions (no auto variables, etc.)? It seems quite a bit complicated and arrays are better in time complexity than vectors, I think... \$\endgroup\$ – Jason Feb 27 '15 at 15:40
  • \$\begingroup\$ Great! Thank you very much!!! However, the algorithm looks quite simple... Are you sure it doesn't miss any case? Do you have any "hints" of a possible proof? \$\endgroup\$ – Jason Feb 27 '15 at 16:37
  • \$\begingroup\$ Something is wrong: in {5, 6, 1, 4, 9, 3, 1, 2} it outputs 14, whereas the correct is 13: { {5, 6, 1}, {4, 9}, {3, 1, 2} }... \$\endgroup\$ – Jason Feb 27 '15 at 17:17
  • 1
    \$\begingroup\$ @Jason: You have right, my algorithm is wrong :-( I will think if there is a fix which is still in O(n), else there is a solution in O(n log(n))... \$\endgroup\$ – Jarod42 Feb 27 '15 at 18:01
  • \$\begingroup\$ Any update yet? \$\endgroup\$ – Jason Mar 3 '15 at 20:39
4
\$\begingroup\$

Code organization

main() does everything. It would be a good idea to separate the concerns, such that main() is responsible for I/O and for calling a function that determines the optimal partition.

Variables

int n, *arr, onee = 0, twoo, threee, total = 0, maxx = -1, temp_maxx;

Those are some weird variable names! If you have some sticky keys on your keyboard, you should clean out the residue.

new int[n];

If you call new, there should be a corresponding delete[]. Better, you could use a variable-length array or a std::vector<int>.

Data representation

A useful observation to make is that you don't need to store the individual numbers. Rather, the running total is more useful. The benefit is that you can find the sum of any subarray in constant time. That is, instead of storing

2, 80, 50, 42, 1, 1, 1, 2

you should store

2, 82, 132, 174, 175, 176, 177, 179

You could always reconstruct the original list from the running totals (not that you need to do so to solve this problem).

The only concern would be overflow. You didn't specify any length or size constraints on your problem, though, so I'm not going to worry about it.

Algorithm

I suggest the following strategy:

  1. Tentatively place the right split past the end of the array, and find the optimal left split. (Given the cumulative representation, partitioning an array optimally into two is easy — O(log n) using a binary search for half of the total.)
  2. Move the right split to the left, and adjust the left split as necessary. (The optimal left split can only ever move left, if at all.)

The complexity of the algorithm is O(n).

#include <algorithm>
#include <iostream>
#include <iterator>

template <typename T>
T max(const T a, const T b, const T c) {
    return std::max(a, std::max(b, c));
}

/**
 * Given an array represented as cumulative sums, find a split
 * that produces the most equal left and right sums.
 */
template <typename ConstIter>
ConstIter minimaxPartition2(ConstIter begin, ConstIter end) {
    typedef typename std::iterator_traits<ConstIter>::value_type T;
    if (end - begin <= 1) {
        return end;
    }
    T total = *(end - 1);
    T ideal = total / 2;
    ConstIter split = std::upper_bound(begin, end, ideal);

    T aSum = std::max(*(split - 1), total - *(split - 1));
    T bSum = std::max(*split, total - *split);
    return aSum < bSum ? split - 1 : split;
}

/**
 * Given an array represented as cumulative sums, find a split
 * that produces the most equal left and right sums by considering
 * small leftward movements of the upperEstimate split point.
 */
template <typename ConstIter>
ConstIter minimaxPartition2(ConstIter begin, ConstIter end, ConstIter upperEstimate) {
    typedef typename std::iterator_traits<ConstIter>::value_type T;
    const T total = *(end - 1);

    ConstIter bestSplit = upperEstimate;
    T bestSum = std::max(*(bestSplit - 1), total - *(bestSplit - 1));

    for (ConstIter split = bestSplit - 1; split >= begin; --split) {
        T sum = std::max(*(split - 1), total - *(split - 1));
        if (sum < bestSum) {
            bestSum = sum;
            bestSplit = split;
        } else {
            break;
        }
    }
    return bestSplit;
}

template <typename ConstIter>
typename std::iterator_traits<ConstIter>::value_type
minimaxPartition3(ConstIter begin, ConstIter end) {
    typedef typename std::iterator_traits<ConstIter>::value_type T;
    const T total = *(end - 1);

    ConstIter split2 = end,
              split1 = minimaxPartition2(begin, split2);
    T leftSum = *split1,
      rightSum = 0,
      best = max(leftSum, total - leftSum - rightSum, rightSum);

    while (--split2 > split1 && rightSum < best) {
        rightSum = total - *split2;
        split1 = minimaxPartition2(begin, split2, split1);
        leftSum = *split1;
        best = std::min(best, max(leftSum, total - leftSum - rightSum, rightSum));
    }
    return best;
}

int main() {
    size_t len;
    std::cin >> len;

    long cumulative[len];
    for (int sum = 0, i = 0; i < len; sum = cumulative[i++]) {
        long n;
        std::cin >> n;
        if (n <= 0) {
            return 1;
        }
        cumulative[i] = sum + n;
    }
    std::cout << minimaxPartition3(cumulative, cumulative + len) << std::endl;
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ std::max(a, std::max(b, c)); may be replaced by std::max({a, b, c}); in C++11. \$\endgroup\$ – Jarod42 Feb 16 '15 at 18:38
3
\$\begingroup\$

Yes, more efficient algorithms do exist.

\$O(n*\log(n))\$:

  1. Let's fix the end of the first part. Now we are interested in finding the end of the second one. I claim that we need to check only two candidates: the last index such that the sum of the second part is not greater then the sum of the third part and the one immediately after it (I will not post a formal proof here, but intuitively it is clear that we want keep these two sums as close to each other as possible.

  2. To do it in efficient manner, we can use a binary search and prefix sums:

    // Returns the sum of the [left, right] subarray in O(1) time.
    int getSum(int left, int right)
        // Prefix sums are used here.
        ...
    
    // Checks if the current answer is better than the current best
    // and makes appropriate updates. 
    void updateAnswer(int firstEnd, int secondEnd)
        ...
    
    // Corner cases are ignored here.
    // This piece of code just represents an idea of the algorithm, it can 
    // contain bugs.
    for (int first <- 0 ... n - 1)
        int low = first
        int high = n - 1
        while (high - low > 1)
            int mid = (low + high) / 2
            if (getSum(first + 1, mid) <= getSum(mid + 1, n - 1))
                low = mid
            else
                high = mid
        updateAnswer(first, low)
        updateAnswer(first, low + 1)
    

Now we can use the following observation: when the first variable increases in the code above, the low value either increases or stays the same, too. That's why we can apply two pointers technique and get an \$O(n)\$ time complexity.

\$\endgroup\$
  • \$\begingroup\$ I suggest the following: copy-paste your answer to this thread so that I can erase this thread and we have all the answers gathered there. (Note: there are 3 totally different techniques of solution until now) \$\endgroup\$ – Jason Feb 13 '15 at 18:50
  • 3
    \$\begingroup\$ @Jason You created this mess by cross-posting the question. Please don't trouble users further by asking answers to be duplicated as well. \$\endgroup\$ – 200_success Feb 13 '15 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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