PROBLEM LINKS
DIFFICULTY
medium
PREREQUISITES
dp, observation
PROBLEM
There are n boxes and m stones. You want to distribute the stones into boxes. Let c_i denote the count of boxes which have strictly more stones than those in box i. You are also given an array E of size n consisting of positive integers. Your aim is to distribute the stones into boxes in such a way that the function \sum_{i=1}^{i=n} E_i c_i is minimized.
QUICK EXPLANATION
Write a dp solution of higher complexity.
Observe that there won’t be a new group created whose index is > 11 or < n - 11. So, there can be total 22 groups at max.
After this observation, the time complexity of solution will become good enough to pass.
EXPLANATION
Without loss of generality, we can arrange the boxes in such a way their corresponding E values are sorted in non-decreasing order. Thus from now on we assume that E array is sorted.
The very first thought that you might ponder over is whether it is possible to make the value of \sum_{i=1}^{i=n} E_i c_i zero or not. If m is divisible by n, then you can distribute the stones in such a way that each box has \frac{m}{n} stones. As all the boxes have equal number of stones, c_i value for each of them will be zero. So, the expression will evaluate to zero.
The above idea immediately gives us an upper bound on the answer, we can always put all the stones into last box. We will have value of c_i = 1 for all the boxes except the last one, which will have its value zero. So, the value of expression will become E_1 + E_2 + \dots + E_{n - 1}.
(Note: Here upper bound doesn’t mean the maximum value of the expression \sum_{i=1}^{i=n} E_i c_i we can get, it means the upper bound on the minimum value we can get, as we have always a option of distributing all the stones in any 1 box only.)
Let s_i denote the number of stones into box i after the distribution.
We can prove that the s array will always be sorted in non-decreasing order. This is due to the fact that for larger values of E_i, we want corresponding value of c_i to be smaller in order to minimize the expression. Hence, the s array should be sorted. You can prove it more formally by applying exchange argument.
A dp solution
Let us visualize the processing of adding stones into the boxes from right to left. We want to add the stones in non-increasing order. In our dynamic programming state, we should the index of the current position, total number of stones added till now, number of stones added in the last box so as to ensure the non-increasing order of number of stones.
We define dp(i, s, last) as the minimum value we can get when we are at position i, total number of stones distributed are s, and the number of stones in box i + 1 = last
This dynamic programming can be calculated by considering the group of boxes which have same number of stones. At each state of dp, we consider all possible lengths len of the block of boxes containing same number of stones. Increment in the cost due to this can be found as follows. We see that all the boxes from i + 1 to n, will have more number of stones than the current block. So, c_i value of current block will be n - i. So, the total cost will be E([i - len + 1] + \dots + E[i]) * (n - i).
dp(n, s, s): will denote our answer.
dp(i, s, last):
if s % i == 0:
// distribute equally
return 0;
ans = inf;
for len = 1 to i:
for stones = last - 1 to 0:
if stones * len >= s:
break;
ans = min(ans, dp(i - len, s - stones * len, stones)
+ (E[i - len + 1] + .. + E[i]) * (n - i)).
return ans;
If implemented naively, this solution will take time n * s * s * log(s).
We can notice that a lot of states of this dp solution will be not useful. As we already know the upper bound on the cost to be E_1 + E_2 + E_3 + \dots + E_n. There will be a lot of states for which the expression (E[i - len + 1] + … + E[i]) * (n - i) will exceed this upper bound. We claim that there will be considerably less states if you don’t add the blocks for which you know that by adding it we are surely going to add the upper bound on cost.
Assume you want to create a block from E[12] to E[12]. This means that the stones added in the boxes from 13 to n are greater than the stones added in this block. So, the contribution of this block in the cost will be E[12] * (n - 12). We can say that the first 12 block will contribute at least 12 * 7 * (n - 12) in the cost, which becomes 84n - 1008.
Assuming that this was the best split we could have obtained, we see that we should have three groups, the first from 1 to 11, the second at 12, and the third at 13 to n. Now, the minimum possible cost for this will be 12 * 7 * (n - 12) = 84n - 1008
We already know that the upper bound on minimum cost is E_1 + E_2 + \dots + E_{n - 1}. Let us take its highest possible value, i.e. 77 * (n - 1) = 77 * n - 77.
As 84n - 1008 > 77n - 77 for n >= 133. We see that creating a block at position 12 is not useful for large value of n.
Infact, for any n, you can prove that creating a block which does not have its starting or ending index in the first 11 or last 11 boxes, will be having strictly more cost than the upper bound.
So, using this observation leads us to the final solution. We can optimize the above dp to break as soon as we are sure that the cost has exceeded the upper bound.
upperBound = E[1] + E[2] + ... + E[n - 1]
dp(i, s, last):
if s % i == 0:
// distribute equally
return 0;
ans = inf;
for len = 1 to i:
minCostRequired = (E[i - len + 1] + .. + E[i]) * (n - i)
if (minCostRequired >= upperBound):
break;
for stones = last - 1 to 0:
if stones * len >= s:
break;
ans = min(ans, dp(i - len, s - stones * len, stones)
+ (E[i - len + 1] + .. + E[i]) * (n - i)).
return ans;
So, as we noticed earlier that for only first 11 and last 11 boxes, we will be doing groups of blocks, rest will have a single group. Hence, time complexity of the overall algorithm will be bounded by \mathcal{O}(22^2 * max(n, s) * log(s)) in the worst case. Infact, number of reachable states will be even lesser.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.