PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
This problem is a bit tricky problem with using dynamic programming and meet-in-the-middle methods.
First of all we should calculate DP with states R[pos][count][d_count] - the minimal possible number of dollars required to buy exactly choose things and spend at most d_cound diamonds for that, if we are using only things with indices from 0 to pos, inclusive. The transitions of such DP are obvious - we can buy pos-th thing (and go to R[pos+1][choose+1][d_count+d], where d is the number of diamonds for pos-th thing) or not (and go to R[pos+1][choose][d_count]). Such DP can be calculated in O(m^2*n), and it is very fast.
Now the main idea is to divide all boxes in two equal part (or a + (a+1) = n in case if n is odd). What it gives to as? We can use brute-force to iterate through all possible subsets of things in the first half that have contained money (it will be about 2^15 subsets in worst case), the rest will contain single diamond (let the number of diamonds be d). What is the probability that such subset will occur? It is, of course, the product of all Pi for all boxes with money multiplied by the product of all 100-Pi for the rest of boxes. Now we should keep some array of vectors Q[d_count] - the list of pairs (money; probability) for all subsets that have contained exactly d_count of diamonds (here money is the total number of money in such subset and probability is the probability that such subset will occur). After that you should sort all that lists of pairs for all Q[d_cound] comparing as pairs (i. e. at first you sort by money, after that by probability). This all was for the first half.
Now what to do with the second half? You need to iterate through all subsets the same way as in first half. For each subset you also will know the probability, the number of diamonds and the number of money. Now you should “match” all subsets of first half with current subset, but, of course, iterating through all subsets in first half will give you O(2^n*n) which is very bad. Instead of doing that you can iterate through all possible numbers of diamonds in the first half (it is from 0 to 15, let it be integer d), this means that now you should “match” all subsets from the first half with current in second, but only such that have exactly d diamonds. But you should notice that Little Elephant always buys the greatest number of things he can afford. So now you should iterate through all possible number of things he will buy (it is from m downto 1, let it be integer c). At this moment you can notice that all subsets from the first half with d diamonds that contains enough money two but exactly c things can be represented as subarray of Q[d]. (Note that it is important to iterate c from m downto 1, not from 1 to m.). But what subarray? You can know it from our DP. Let money to be the number of dollars in current subset in the second half. In order to buy exactly m things you should have at least R[m][m][d]-money money, to buy m-1 things you should have from R[m][m-1][d]-money to R[m][m][d]-money-1 of money (no more because you should use your money optimally), to but m-2 things - from R[m][m-2][d]-money to R[m][m-1][d]-money-1 and so on. Since Q[d] is sorted, you can use binary search to know the intervals of all subarrays (let it be [l; r]). In this moment you should add to the answer number p(S[d][r]-S[d][l-1])c, where S[d][i] = Q[d][0].probability + Qd.probability + … + Q[d][i].probability and p is the probability of current subset in the second half.
So the total complexity is O(2^a * n + 2^b * a * m * n) (a - the size of first part, b = n-a - the size of second part). Here you can notice that it is good to divide not in the equal parts. It is better to make the first part bigger than second, like 18 and 12 for n=30. After that algorithm will be fast enough to get green Accepted
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.