PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The intended solution to this problem is of complexity O(N * K).
The time limits proved to be tight.
The key observation in this problem is that, once Chief selects the items she wants to buy, the discounts are applied on them such that the largest discount is used on the item with the highest cost, the second largest discount is used on the item with the second highest cost and so on…
So first, we sort all the prices and discounts.
There are two solutions to this problem now.
Method 1.
Find the probability that we apply discount j on item i. Let this be p(i,j). Both i and j are 1-based.
- p(i,j) = c(i-1,j-1) * c(N-i,K-j)/c(N,K)
Explanation: if discount j is being used on item i, means there are j-1 items selected from i-1 items. Further, there are K-j items selected from the remaining N-i items. This is true, because we know that j’th smallest discount will only be used on item i; if the order of item i is ‘j’, in the sorted order of purchases made.
The expected discount is
- summation(1<=i<=N, 1<=j<=K, p(i,j) * price[i] * discount[j]/100)
Explanation: If we see the expected discount as small contributions from each item, we see that each item contributes to the expected discount whenever it is picked in a combination. And its contribution to the expected discount is the order index in which this item is picked. By linearity of expectation, we can consider the tuple of: each item (i), and the order index at which it is picked (j) - as the random variable. We know the probability of this variable, and its contribution to expected discount too. Hence this formula is valid.
Implementation of this algorithm had to be done carefully to avoid overflowing doubles. The time limits were quite tight if this approach was used. But since p(i,j) would be 0 for a large number of j - if K is almost equal to N - the optimization: iterate for only those j for which p(i,j) is non-zero - was enough.
Method 2. (Thank you Anton for pointing out this approach!)
Let, dp[i][j] = expected maximal discount that we can obtain if we consider only first ‘i’ items and first ‘j’ discounts.
Consider the following two cases:
- i-th item is chosen
We apply j-th discount to i-th item and get discount price[i] * discount[j] and turn to situation with (i-1) items and (j-1) discounts. So in this case, expected discount is equal to a[i] * b[j]+dp[i-1][j-1].
The probability of this happening is p = j/i. Since we must choose j items from i, and probability that i’th item will be chosen is equal to j/i.
- i-th item is not chosen
The answer is dp[i-1][j].
The probability of this happening is 1-p.
Thus we obtain the formula
dp[i][j] = (a[i] * b[j] + dp[i-1][j-1]) * p + dp[i-1][j]*(1-p)
Then dp[n][k] is the answer.
SETTER’S SOLUTION
Can be found here.