The problem required us to find the expected saving chef can make considering the average of all the discounts over all the combinations Chief might select.

A novice approach of trying all combinations will TLE.

Dynamic programming might be of help here. As the chief would like to maximize the discount he may get over a combination he would use lower discounts for lower costs articles.

My Approach -

1. Sort all costs in ascending order.

2. Sort all discounts in ascending order.

We have N articles and K discounts to use.

expected(n,k)= (expected(n+1,k+1)+cost(n)*discount(k))*((K-k)/(N-n))+expected(n+1,k)*(1-(K-k)/(N-n))

Here n and k denote the number of articles considered and the number of discounts used till now. We have to find expected(0,0) and the multiplication of (K-k)/(N-n) is done to one side and (1-(K-k)/(N-n)) to the to the other because when while calculating expected(n,k) (N-n) articles remain to be considered and (K-k) discounts remain. The probability of getting the article is (K-k)/(N-n) and not getting is (1-(K-k)/(N-n)).

Using this approach we find the expected discount that chef can achieve.

I used this code during the contest which had memoization and i got TLE.

I used this code after the contest which avoided recursion and used straight forward DP and got WA.

Can anyone help me here. 

EDIT: Got AC... Used sliding window DP by minimizing the memory table to 2 rows. As only 2 are required.

Here is the Code