Partition array in at most k subarrays that minimize a function

Question

I have 2 values \$N\$ and \$K\$ (\$1 \le K \lt N \le 1.000\$), where \$N\$ indicates a number of values (\$0 \le \text{value}2 \le ... \le \text{value}N \le 1,000,000\$) to be read from input. The first value isn't on the input and will always be 0.

All \$N\$ values need to be organized on at most \$K\$ groups where the sum of the groups size is minimized.

The size of a group is defined by the distance between the two most distant values in the group (MAX_VALUE - MIN_VALUE). If the group consists of only one value, its size is zero.

What is the minimum total value for the sum of the groups size if the values are organized optimally?

Here is an input sample:

5 2
1 2 5 6

Output sample:

3

My solution is a brute force search. This is a known problem. How can I do better than this solution?

#include <cstdio>
#include <queue>
#include <vector>
#include <limits>
#include <algorithm>

using groups = std::vector< std::vector<int> >;

int getTotalGroupsSize(groups &g){
    unsigned long k = g.size();

    int total = 0;

    for (unsigned long i = 0; i < k; ++i) {
        int max = std::numeric_limits<int>::min();
        int min = std::numeric_limits<int>::max();

        std::vector<int> &subGroup = g[i];

        for (int j = 0; j < subGroup.size(); ++j) {
            max = std::max(max, subGroup[j]);
            min = std::min(min, subGroup[j]);
        }

        total += (max - min);

    }


    return total;
}

int getOptimallSum(std::queue<int> &q, groups &g){

    if(q.empty())
        return getTotalGroupsSize(g);


    int front = q.front();
    q.pop();

    int minDiff = std::numeric_limits<int>::max();
    for (int i = 0; i < g.size(); ++i) {
        g[i].push_back(front);
        minDiff = std::min(minDiff,getOptimallSum(q, g));
        g[i].pop_back();
    }

    q.push(front);
    return minDiff;
}


int main(void){
    int n,k;

    while (scanf("%d",&n) != EOF) {
        scanf("%d",&k);

        std::queue<int> q;
        q.push(0);
        for (int i = 1; i < n; ++i) {
            int value;
            scanf("%d",&value);
            q.push(value);
        }

        if(k >= n){
            puts("0");
            continue;
        }

        groups g(k);
        printf("%d\n",getOptimallSum(q,g));

    }
    return 0;
}

Answer 1

Yes there is a better way.

The key observation is that since the array is sorted, the size of partition [p,q] is \$a_q - a_p\$, and the sum of sizes is almost \$a_N - a_1\$. Missing are gaps between right end of one partition and left end of the next one.

So the solution is to compute the set of sequential differences, and select \$K-1\$ largest. These are optimal partition points.

Otherwise, the code is clean and understandable.

Answer 2

Just going to address the code, not the algorithm, as an optimal solution to this problem ends up being pretty boring but the brute force solution gives me something to talk about.

C++ is not C

You're using scanf and puts. While those work, you should prefer to use std::cin and std::cout.

getTotalGroupsSize()

Whenever your code adds to a Group, it always adds the next element to the back. And we always go in order. So your structure actually guarantees that each group is always sorted. Thus:

int getTotalGroupsSize(groups const& g) {
    int size = 0;
    for (auto& group : g) {
        if (!group.empty()) {
            size += group.back() - group.front();
        }
    }
    return size;
}

Also take the argument by reference-to-const, you're not modifying it.

getOptimallSum()

You misspelled optimal. Also, this whole loop could use some work. You made a queue that you're constantly popping and pushing. This is unnecessary extra work. The recursive approach makes sense, but rather than use a container to recurse, let's use iterators:

template <typename Iter>
int getOptimalSum(Iter begin, Iter end, groups& g)
{
    if (begin == end) {
        return getTotalGroupsSize(g);
    }

    // ...
}

So what one iteration will do is try to add *begin to each of the groups in g (which is a terrible name), and recurse on the next iterator. Just directly that's:

for (auto& group : g) {
    group.push_back(*begin);
    minDiff = std::min(minDiff, getOptimalSum(std::next(begin), end,  g));
    group.pop_back();
}

return minDiff;

And now we don't need a queue anymore. We just use another vector:

std::vector<int> values;
// populate values
Groups groups(k);

std::cout << getOptimalSum(values.begin(), values.end(), groups) << '\n';