Partition an array in order

Question

This is an interview question that a friend of mine got and I'm unable to come up with how to solve it.

Question:

You are given a array of n buttons that are either red or blue. There are k containers present. The value of a container is given by the product of red buttons and blue buttons present in it. The problem is to put the buttons into the containers such that the sum of all values of the containers is minimal. Additionally, all containers must contain the buttons and they must be put in order they are given. For example, the very first button can only go to the first container, the second one can go to either the first or the second but not the third (otherwise the second container won't have any buttons). k will be less than or equal to n.

I think there must be a dynamic programming solution for this.

How do you solve this ? So far, I've only got the trivial cases where

• if (n==k), the answer would be zero because you could just put one in each container making the value of each container zero, therefore the sum would be zero.
• if (k==1), you just dump all of them and calculate the product.
• if only one color is present, the answer would be zero.

Edit:

I'll give an example.

n = 4 and k = 2

Input: R B R R

The first container gets the first two (R and B) making its value 1 (1R X 1B) The second container gets the remaining (R and R) making its value 0 (2R x 0B) The answer is 1 + 0 = 1

if k=3, the first container would have only the first button (R) the second container would have only the second one (B) the third one would have the last two buttons (R and R) Each of the containers would have value 0 and hence sum and answer would be 0.

Hope this clears up the doubts.

Answer 1

Possible DP solution:

Let dp[i, j] = minimum number possible if we put the first i numbers into j containers.

dp[i, j] = min{dp[p, j - 1] + numRed[p+1, i]*numBlues[p+1, i]}, p = 1 to i - 1

Answer will be in dp[n, k].

int blue = 0, red = 0;
for (int i = 1; i <= n; ++i)
{
    if (buttons[i] == 1)
        ++red;
    else
        ++blue;

    dp[i][1] = red * blue;
}

for (int i = 2; i <= n; ++i)
    for (int j = 2; j <= k; ++j)
    {
        dp[i][j] = inf;

        for (int p = 1; p <= i; ++p)
            dp[i][j] = min(dp[p][j - 1] + getProd(p + 1, i), dp[i][j]);
    }

return dp[n][k];

Complexity will be O(n^3*k), but it's possible to reduce to O(n^2*k) by making getProd run in O(1) with the help of certain precomputations (hint: use dp[i][1]). I'll post it tomorrow if no one figures out this is actually wrong until then.

It might also be possible to reduce to O(n*k), but that will probably require a different approach...

Answer 2

If I understand the question correctly, as long as every container has at least one button in it, you can choose any container to put the remaining buttons in. Given that, put one button in every container, making sure that there is at least one container with a red button and at least one with a blue button. Then with the remaining buttons, put all the red buttons in a container with a red button and put all the blue buttons in a container with blue buttons in it. This will make it so every container has at least one button and every container has only one color of buttons. Then every container's score is 0. Thus the sum is 0 and you have minimized the combined score.