Daily bit(e) of C++ | Splitting marbles

Daily bit(e) of C++ #205, Common interview problem: Splitting marbles.

Today we will look at a common C++ interview problem: Splitting marbles.

Given a row of marbles with different values represented as std::vector<int64_t>, divide these marbles into k contiguous sections.

Return the difference between the maximum and minimum achievable total values of divisions, given that a section i..j has value values[i]+values[j].

With O(n) achievable, provide a solution with at least O(n*logn).

For example, for the marble values {1,2,3,4,5} and three sections, the minimum value we can achieve is 14 with sections {1}, {2}, {3,4,5}, the maximum value we can achieve is 22 with sections {1,2,3}, {4}, {5}.

Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/a8s6YPh7M.

Solution

This problem requires reframing. What are we asked to do?

Let’s consider the overall sum we are trying to minimize and maximize. It will be sequences of values which will always contain values[0] and values[values.size()-1], with the rest of the elements forming adjacent pairs.

Because we are tasked with returning the difference, we can safely ignore the boundary values and concentrate on the adjacent pairs. We will have k-1 such pairs, and for the minimum, these will be the k-1 pairs with minimum sums, and for the maximum, these will be the k-1 pairs with the maximum sums.

With that, we can reformulate the problem: return the difference between the sum of the k-1 lowest adjacent sums and the sum of the k-1 largest adjacent sums. This is achievable in O(n).

Click to open in Compiler Explorer.

---